#
Chapter 13
Hashtables

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 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?` 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.

## 13.1 Constructors

`(make-eq-hashtable)` procedure
`(make-eq-hashtable k)` procedure

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)` procedure

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-hashtable hash-function equiv)` procedure
`(make-hashtable hash-function equiv k)` procedure

Hash-function and equiv must be procedures. Hash-function 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 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 integer objects 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.

## 13.2 Procedures

`(hashtable? hashtable)` procedure

Returns `#t` if hashtable is a hashtable, `#f` otherwise.

`(hashtable-size hashtable)` procedure

Returns the number of keys contained in hashtable as an exact integer object.

`(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-set! hashtable key obj)` procedure

Changes hashtable to associate key with obj, adding a new association or replacing any existing association for key, and returns unspecified values.

`(hashtable-delete! hashtable key)` procedure

Removes any association for key within hashtable and returns unspecified values.

`(hashtable-contains? hashtable key)` procedure

Returns `#t` if hashtable contains an association for key, `#f` otherwise.

`(hashtable-update! hashtable key proc default)` procedure

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!
hashtable key
(proc (hashtable-ref
hashtable key default)))

`

`(hashtable-copy hashtable)` procedure
`(hashtable-copy hashtable mutable)` procedure

Returns a copy of hashtable. If the mutable argument is provided and is true, the returned hashtable is mutable; otherwise it is immutable.

`(hashtable-clear! hashtable)` procedure
`(hashtable-clear! hashtable k)` procedure

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.

`(hashtable-keys hashtable)` procedure

Returns a vector of all keys in hashtable. The order of the vector is unspecified.

`(hashtable-entries hashtable)` procedure

Returns two values, a vector of the keys in hashtable, and a vector of the corresponding values.

`(let ((h (make-eqv-hashtable)))
(hashtable-set! h 1 ’one)
(hashtable-set! h 2 ’two)
(hashtable-set! h 3 ’three)
(hashtable-entries h))
⇒ `#`(1 2 3) `#`(one two three)
; two return values

`

## 13.3 Inspection

`(hashtable-equivalence-function hashtable)` procedure

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.

`(hashtable-hash-function hashtable)` procedure

Returns the hash function used by hashtable. For hashtables created by `make-eq-hashtable` or `make-eqv-hashtable`, `#f` is returned.

`(hashtable-mutable? hashtable)` procedure

Returns `#t` if hashtable is mutable, otherwise `#f`.

## 13.4 Hash functions

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.

`(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.

> Note: Like `equal?`, the `equal-hash` procedure must always terminate, even if its arguments contain cycles.

`(string-hash string)` procedure

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.

`(string-ci-hash string)` procedure

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.

`(symbol-hash symbol)` procedure

Returns an integer hash value for symbol.