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

### Constructors

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

### Type tests

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

.

### Inspection

**(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]

Returns the hash function used by *hashtable*. For hashtables created by `make-eq-hashtable`

and `make-eqv-hashtable`

, `#f`

is returned.

**(hashtable-mutable? hashtable)** [procedure]

Returns `#t`

if hashtable is mutable, otherwise `#f`

.

### Hash functions

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

### Procedures

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

### Composition

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