The (r6rs hash-tables)library provides hash tables. A hash table 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, and must be compatible with the equivalence function, which is a procedure that accepts two keys and returns true if they are equivalent, otherwise returns #f. Standard hash tables for arbitrary objects based on the eq? and eqv? predicates (see report section on “Equivalence predicates”) are provided. Also, standard hash functions for several types are provided.
This section uses the hash-table parameter name for arguments that must be hash tables, and the key parameter name for arguments that must be hash-table keys.
Returns a newly allocated mutable hash table that accepts arbitrary objects as keys, and compares those keys with eq?. If an argument is given, the initial capacity of the hash table is set to approximately k elements.
Returns a newly allocated mutable hash table that accepts arbitrary objects as keys, and compares those keys with eqv?. If an argument is given, the initial capacity of the hash table is set to approximately k elements.
Hash-function and equiv must be procedures. Hash-function will be called by other procedures described in this chapter with a key as argument, and must return a non-negative exact integer. Equiv will be called by other procedures described in this chapter with two keys as arguments. The make-hash-table procedure returns a newly allocated mutable hash table 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 hash table is set to approximately k elements.
Both the hash function hash-function and the equivalence function 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 hash table. Furthermore, any pair of values for which the equivalence function equiv returns true should be hashed to the same exact integers by hash-function.
Note: Hash tables 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 hash-table operation may call the hash function more than once.
Rationale: Hash-table lookups are often followed by updates, so caching may improve performance. Hash tables are free to change their internal representation at any time, which may result in many calls to the hash function.
Returns #t if hash-table is a hash table. Otherwise, returns #f.
Returns the number of keys contained in hash-table as an exact integer.
Returns the value in hash-table associated with key. If hash-table does not contain an association for key, then default is returned.
Changes hash-table to associate key with obj, adding a new association or replacing any existing association for key, and returns the unspecified value.
Removes any association for key within hash-table, and returns the unspecified value.
Returns #t if hash-table contains an association for key. Otherwise, returns #f.
Proc must be a procedure that takes a single argument. The hash-table-update! procedure applies proc to the value in hash-table associated with key, or to default if hash-table does not contain an association for key. The hash-table is then changed to associate key with the result of proc.
The behavior of hash-table-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:
(hash-table-set!
Returns a copy of hash-table. If the immutable argument is provided and is true, the returned hash table is immutable; otherwise it is mutable.
Rationale: Hash table references may be less expensive with immutable hash tables. Also, the creator of a hash table may wish to prevent modifications, particularly by code outside of the creator’s control.
Removes all associations from hash-table and returns the unspecified value.
If a second argument is given, the current capacity of the hash table is reset to approximately k elements.
Returns a vector of all keys in hash-table. The order of the vector is unspecified.
Returns two values, a vector of the keys in hash-table, and a vector of the corresponding values.
(let ((h (make-eqv-hash-table)))
Returns the equivalence function used by hash-table to compare keys. For hash tables created with make-eq-hash-table and make-eqv-hash-table, returns eq? and eqv? respectively.
Returns the hash function used by hash-table. For hash tables created by make-eq-hash-table or make-eqv-hash-table, #f is returned.
Rationale: The make-eq-hash-table and make-eqv-hash-table 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 whenever the garbage collector moves objects to a different address.
Returns #t if hash-table is mutable, otherwise returns #f.
The equal-hash, string-hash, and string-ci-hash procedures of this section are acceptable as hash functions only if the keys on which they are called do not suffer side effects while the hash table remains in use.
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.