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

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

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.

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

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.

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

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.

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

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