The (rnrs hashtables (6))library provides a set of operations on hashtables. 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 integers. 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? and eqv? predicates (see report section on “Equivalence predicates”) are provided. Also, hash functions for arbitrary objects, strings, and symbols are provided.
This section uses the hashtable parameter name for arguments that must be hashtables, and the key parameter name for arguments that must be hashtable keys.
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.
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.
Hash-function and equiv must be procedures. Hash-function should accept a key as an argument and should return a non-negative exact integer. Equiv should accept two keys as arguments and return a single value. Neither procedure should mutate the hashtable returned by make-hashtable. The make-hashtable procedure returns a newly allocated mutable hashtable using hash-function as the hash function and equiv as the equivalence function used to compare keys. If a third argument is given, the initial capacity of the hashtable is set to approximately k elements.
Both hash-function 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 integers by hash-function.
Implementation responsibilities: The implementation must check the restrictions on hash-function and equiv to the extent performed by applying them as described.
Note: Hashtables are allowed to cache the results of calling the hash function and equivalence function, so programs cannot rely on the hash function being called for every lookup or update. Furthermore any hashtable operation may call the hash function more than once.
Rationale: Hashtable lookups are often followed by updates, so caching may improve performance. Hashtables are free to change their internal representation at any time, which may result in many calls to the hash function.
Returns #t if hashtable is a hashtable, #f otherwise.
Returns the number of keys contained in hashtable as an exact integer.
Returns the value in hashtable associated with key. If hashtable does not contain an association for key, default is returned.
Changes hashtable to associate key with obj, adding a new association or replacing any existing association for key, and returns unspecified values.
Removes any association for key within hashtable and returns unspecified values.
Returns #t if hashtable contains an association for key, #f otherwise.
Proc should accept one argument, should return a single value, and should not mutate hashtable. The hashtable-update! procedure 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.
The behavior of hashtable-update! is equivalent to the following code, but may be implemented more efficiently in cases where the implementation can avoid multiple lookups of the same key:
(hashtable-set!
Returns a copy of hashtable. If the mutable argument is provided and is true, the returned hashtable is mutable; otherwise it is immutable.
Rationale: Hashtable references may be less expensive with immutable hashtables. Also, the creator of a hashtable may wish to prevent modifications, particularly by code outside of the creator’s control.
Removes all associations from hashtable and returns unspecified values.
If a second argument is given, the current capacity of the hashtable is reset to approximately k elements.
Returns a vector of all keys in hashtable. The order of the vector is unspecified.
Returns two values, a vector of the keys in hashtable, and a vector of the corresponding values.
(let ((h (make-eqv-hashtable)))
Returns the equivalence function used by hashtable to compare keys. For hashtables created with make-eq-hashtable and make-eqv-hashtable, returns eq? and eqv? respectively.
Returns the hash function used by hashtable. For hashtables created by make-eq-hashtable or make-eqv-hashtable, #f is returned.
Rationale: The make-eq-hashtable and make-eqv-hashtable constructors are designed to hide their hash function. This allows implementations to use the machine address of an object as its hash value, rehashing parts of the table as necessary if a garbage collector moves objects to different addresses.
Returns #t if hashtable is mutable, otherwise #f.
The equal-hash, string-hash, and string-ci-hash procedures of this section 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.
Returns an integer hash value for string, based on its current contents. This hash function is suitable for use with string=? as an equivalence function.
Returns an integer hash value for string based on its current contents, ignoring case. This hash function is suitable for use with string-ci=? as an equivalence function.
Returns an integer hash value for symbol.