-
Notifications
You must be signed in to change notification settings - Fork 16
LispKit Hashtable
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) [procedure]
(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) [procedure]
(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) [procedure]
(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) [procedure]
(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) [procedure]
(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) [procedure]
(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.
(alist->equal-hashtable alist) [procedure]
(alist->equal-hashtable alist k)
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.
(hashtable-copy hashtable) [procedure]
(hashtable-copy hashtable mutable)
Returns a copy of hashtable. If the mutable argument is provided and is true, the returned hashtable is mutable; otherwise it is immutable.
(hashtable-empty-copy hashtable) [procedure]
Returns a new mutable hashtable that uses the same hash and equivalence functions like hashtable.
(hashtable? obj) [procedure]
Returns #t if obj is a hashtable. Otherwise, it returns #f.
(eq-hashtable? obj) [procedure]
Returns #t if obj is a hashtable which uses eq? for comparing keys. Otherwise, it returns #f.
(eqv-hashtable? obj) [procedure]
Returns #t if obj is a hashtable which uses eqv? for comparing keys. Otherwise, it returns #f.
(equal-hashtable? obj) [procedure]
Returns #t if obj is a hashtable which uses equal? for comparing keys. Otherwise, it returns #f.
(hashtable-equivalence-function hashtable) [procedure]
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.
(hashtable-hash-function hashtable) [procedure]
(hashtable-hash-function hashtable force?)
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.
(hashtable-mutable? hashtable) [procedure]
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.
(equal-hash obj) [procedure]
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.
(eqv-hash obj) [procedure]
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.
(eq-hash obj) [procedure]
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.
(string-hash str) [procedure]
Returns an integer hash value for str, based on its current characters. This hash function is suitable for use with string=? as an equivalence function.
(string-ci-hash str) [procedure]
Returns an integer hash value for str based on its current characters, ignoring case. This hash function is suitable for use with string-ci=? as an equivalence function.
(symbol-hash sym) [procedure]
Returns an integer hash value for symbol sym.
(hashtable-size hashtable) [procedure]
Returns the number of keys contained in hashtable as an exact integer object.
(hashtable-load hashtable) [procedure]
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.
(hashtable-ref hashtable key default) [procedure]
Returns the value in hashtable associated with key. If hashtable does not contain an association for key, default is returned.
(hashtable-get hashtable key) [procedure]
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").
(hashtable-set! hashtable key obj) [procedure]
Changes hashtable to associate key with obj, adding a new association or replacing any existing association for key.
(hashtable-delete! hashtable key) [procedure]
Removes any association for key within hashtable.
(hashtable-add! hashtable key obj) [procedure]
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.
(hashtable-remove! hashtable key) [procedure]
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.
(alist->hashtable! hashtable alist) [procedure]
Adds all the associations from alist to hashtable using hashtable-add!.
(hashtable-contains? hashtable key) [procedure]
Returns #t if hashtable contains an association for key, #f otherwise.
(hashtable-update! hashtable key proc default) [procedure]
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:
(hashtable-set! hashtable
key
(proc (hashtable-ref hashtable key default)))
(hashtable-clear! hashtable) [procedure]
(hashtable-clear! hashtable k)
Removes all associations from hashtable. If a second argument k is given, the current capacity of the hashtable is reset to approximately k elements.
(hashtable-keys hashtable) [procedure]
Returns an immutable vector of all keys in hashtable.
(hashtable-values hashtable) [procedure]
Returns an immutable vector of all values in hashtable.
(hashtable-entries hashtable) [procedure]
Returns two values, an immutable vector of the keys in hashtable, and an immutable vector of the corresponding values.
(hashtable-key-list hashtable) [procedure]
Returns a list of all keys in hashtable.
(hashtable-value-list hashtable) [procedure]
Returns a list of all values in hashtable.
(hashtable->alist hashtable) [procedure]
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.
(hashtable-for-each proc hashtable) [procedure]
Applies proc to every association in hashtable. proc should be a procedure accepting two values, a key and a corresponding value.
(hashtable-map! proc hashtable) [procedure]
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.
(hashtable-union! hashtable1 hashtable2) [procedure]
Includes all associations from hashtable2 in hashtable1 if the key of the association is not already contained in hashtable1.
(hashtable-intersection! hashtable1 hashtable2) [procedure]
Removes all associations from hashtable1 for which the key of the association is not contained in hashtable2.
(hashtable-difference! hashtable1 hashtable2) [procedure]
Removes all associations from hashtable1 for which the key of the association is contained in hashtable2.
Some of this documentation is derived from the R6RS specification of hash tables by Michael Sperber, Kent Dybvig, Matthew Flatt, Anton van Straaten, Richard Kelsey, William Clinger, and Jonathan Rees.