(lispkit hashtable)
Last updated
Last updated
Library (lispkit hashtable) provides a native implementation of hashtables based on the API defined by R6RS.
A hashtable is a data structure that associates keys with values. Any object can be used as a key, provided a hash function and a suitable equivalence function is available. A hash function is a procedure that maps keys to exact integer objects. It is the programmer’s responsibility to ensure that the hash function is compatible with the equivalence function, which is a procedure that accepts two keys and returns true if they are equivalent and #f otherwise. Standard hashtables for arbitrary objects based on the eq?, eqv?, and equal? predicates are provided. Also, hash functions for arbitrary objects, strings, and symbols are included.
The specification below uses the hashtable parameter name for arguments that must be hashtables, and the key parameter name for arguments that must be hashtable keys.
(make-eq-hashtable) (make-eq-hashtable k)
Returns a newly allocated mutable hashtable that accepts arbitrary objects as keys and compares those keys with eq?. If an argument is given, the initial capacity of the hashtable is set to approximately k elements.
(make-eqv-hashtable) (make-eqv-hashtable k)
Returns a newly allocated mutable hashtable that accepts arbitrary objects as keys and compares those keys with eqv?. If an argument is given, the initial capacity of the hashtable is set to approximately k elements.
(make-equal-hashtable) (make-equal-hashtable k)
Returns a newly allocated mutable hashtable that accepts arbitrary objects as keys and compares those keys with equal?. If an argument is given, the initial capacity of the hashtable is set to approximately k elements.
(make-hashtable hash equiv) (make-hashtable hash equiv k)
Returns a newly allocated mutable hashtable using hash as the hash function and equiv as the equivalence function for comparing keys. If a third argument k is given, the initial capacity of the hashtable is set to approximately k elements.
hash and equiv must be procedures. hash should accept a key as an argument and should return a non-negative exact integer object. equiv should accept two keys as arguments and return a single boolean value. Neither procedure should mutate the hashtable returned by make-hashtable. Both hash and equiv should behave like pure functions on the domain of keys. For example, the string-hash and string=? procedures are permissible only if all keys are strings and the contents of those strings are never changed so long as any of them continues to serve as a key in the hashtable. Furthermore, any pair of keys for which equiv returns true should be hashed to the same exact integer objects by hash.
(alist->eq-hashtable alist) (alist->eq-hashtable alist k)
Returns a newly allocated mutable hashtable consisting of the mappings contained in the association list alist. Keys are compared with eq?. If argument k is given, the capacity of the returned hashtable is set to at least k elements.
(alist->eqv-hashtable alist) (alist->eqv-hashtable alist k)
Returns a newly allocated mutable hashtable consisting of the mappings contained in the association list alist. Keys are compared with eqv?. If argument k is given, the capacity of the returned hashtable is set to at least k elements.
Returns a newly allocated mutable hashtable consisting of the mappings contained in the association list alist. Keys are compared with equal?. If argument k is given, the capacity of the returned hashtable is set to at least k elements.
Returns a copy of hashtable. If the mutable argument is provided and is true, the returned hashtable is mutable; otherwise it is immutable.
Returns a new mutable hashtable that uses the same hash and equivalence functions like hashtable.
Returns #t if obj is a hashtable. Otherwise, it returns #f.
Returns #t if obj is a hashtable which uses eq? for comparing keys. Otherwise, it returns #f.
Returns #t if obj is a hashtable which uses eqv? for comparing keys. Otherwise, it returns #f.
Returns #t if obj is a hashtable which uses equal? for comparing keys. Otherwise, it returns #f.
Returns the equivalence function used by hashtable to compare keys. For hashtables created with make-eq-hashtable, make-eqv-hashtable, and make-equal-hashtable, returns eq?, eqv?, and equal? respectively.
Returns the hash function used by hashtable. For hashtables created by make-eq-hashtable and make-eqv-hashtable, #f is returned. This behavior can be disabled if boolean parameter force? is being provided and set to #t. In this case, hashtable-hash-function will also return hash functions for eq and eqv-based hashtables.
Returns #t if hashtable is mutable, otherwise #f.
The equal-hash, string-hash, and string-ci-hash procedures are acceptable as the hash functions of a hashtable only, if the keys on which they are called are not mutated while they remain in use as keys in the hashtable.
Returns an integer hash value for obj, based on its structure and current contents. This hash function is suitable for use with equal? as an equivalence function. Like equal?, the equal-hash procedure must always terminate, even if its arguments contain cycles.
Returns an integer hash value for obj, based on obj's identity. This hash function is suitable for use with eqv? as an equivalence function.
Returns an integer hash value for obj, based on obj's identity. This hash function is suitable for use with eq? as an equivalence function.
Returns an integer hash value for boolean b.
Returns an integer hash value for character ch. This hash function is suitable for use with char=? as an equivalence function.
Returns an integer hash value for character ch, ignoring case. This hash function is suitable for use with char-ci=? as an equivalence function.
Returns an integer hash value for string str, based on its current characters. This hash function is suitable for use with string=? as an equivalence function.
Returns an integer hash value for string str based on its current characters, ignoring case. This hash function is suitable for use with string-ci=? as an equivalence function.
Returns an integer hash value for symbol sym.
Returns an integer hash value for numeric value x.
Combines the integer hash values h ... into a single hash value.
Returns the number of keys contained in hashtable as an exact integer object.
Returns the load factor of the hashtable. The load factor is defined as the ratio between the number of keys and the number of hash buckets of hashtable.
Returns the value in hashtable associated with key. If hashtable does not contain an association for key, default is returned.
Returns a pair consisting of a key matching key and associated value from hashtable. If hashtable does not contain an association for key, hashtable-get returns #f.
For example, for a hashtable ht containing the mapping 3 to "three", (hashtable-get ht 3) will return (3 . "three").
Changes hashtable to associate key with obj, adding a new association or replacing any existing association for key.
Removes any association for key within hashtable.
Changes hashtable to associate key with obj, adding a new association for key. The difference to hashtable-set! is that existing associations of key will remain in hashtable, whereas hashtable-set! replaces an existing association for key.
Removes the association for key within hashtable which was added last, and returns it as a pair consisting of the key matching key and its associated value. If there is no association of key in hashtable, hashtable-remove! will return #f.
Adds all the associations from alist to hashtable using hashtable-add!.
Returns #t if hashtable contains an association for key, #f otherwise.
hashtable-update! applies proc to the value in hashtable associated with key, or to default if hashtable does not contain an association for key. The hashtable is then changed to associate key with the value returned by proc. proc is a procedure which should accept one argument, it should return a single value, and should not mutate hashtable. The behavior of hashtable-update! is equivalent to the following code:
Removes all associations from hashtable. If a second argument k is given, the current capacity of the hashtable is reset to approximately k elements.
Returns an immutable vector of all keys in hashtable.
Returns an immutable vector of all values in hashtable.
Returns two values, an immutable vector of the keys in hashtable, and an immutable vector of the corresponding values.
Returns a list of all keys in hashtable.
Returns a list of all values in hashtable.
Returns a list of all associations in hashtable as an association list. Each association is represented as a pair consisting of the key and the corresponding value.
Applies proc to every association in hashtable. proc should be a procedure accepting two values, a key and a corresponding value.
Applies proc to every association in hashtable. proc should be a procedure accepting two values, a key and a corresponding value, and returning one value. This value and the key will replace the existing binding.
Includes all associations from hashtable2 in hashtable1 if the key of the association is not already contained in hashtable1.
Removes all associations from hashtable1 for which the key of the association is not contained in hashtable2.
Removes all associations from hashtable1 for which the key of the association is contained in hashtable2.
(alist->equal-hashtable alist) (alist->equal-hashtable alist k)
(hashtable-copy hashtable) (hashtable-copy hashtable mutable)
(hashtable-empty-copy hashtable)
(hashtable? obj)
(eq-hashtable? obj)
(eqv-hashtable? obj)
(equal-hashtable? obj)
(hashtable-equivalence-function hashtable)
(hashtable-hash-function hashtable) (hashtable-hash-function hashtable force?)
(hashtable-mutable? hashtable)
(equal-hash obj)
(eqv-hash obj)
(eq-hash obj)
(boolean-hash b)
(char-hash ch)
(char-ci-hash ch)
(string-hash str)
(string-ci-hash str)
(symbol-hash sym)
(number-hash x)
(combine-hash h ...)
(hashtable-size hashtable)
(hashtable-load hashtable)
(hashtable-ref hashtable key default)
(hashtable-get hashtable key)
(hashtable-set! hashtable key obj)
(hashtable-delete! hashtable key)
(hashtable-add! hashtable key obj)
(hashtable-remove! hashtable key)
(alist->hashtable! hashtable alist)
(hashtable-contains? hashtable key)
(hashtable-update! hashtable key proc default)
(hashtable-clear! hashtable) (hashtable-clear! hashtable k)
(hashtable-keys hashtable)
(hashtable-values hashtable)
(hashtable-entries hashtable)
(hashtable-key-list hashtable)
(hashtable-value-list hashtable)
(hashtable->alist hashtable)
(hashtable-for-each proc hashtable)
(hashtable-map! proc hashtable)
(hashtable-union! hashtable1 hashtable2)
(hashtable-intersection! hashtable1 hashtable2)
(hashtable-difference! hashtable1 hashtable2)
Some of this documentation is derived from the by Michael Sperber, Kent Dybvig, Matthew Flatt, Anton van Straaten, Richard Kelsey, William Clinger, and Jonathan Rees.
