# (lispkit hashtable)

Last updated

Last updated

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

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.

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

Returns a new mutable hashtable that uses the same hash and equivalence functions like *hashtable*.

Type tests

Returns `#t`

if *obj* is a hashtable. Otherwise, it returns `#f`

.

Returns `#t`

if *obj* is a hashtable which uses `eq?`

for comparing keys. Otherwise, it returns `#f`

.

Returns `#t`

if *obj* is a hashtable which uses `eqv?`

for comparing keys. Otherwise, it returns `#f`

.

Returns `#t`

if *obj* is a hashtable which uses `equal?`

for comparing keys. Otherwise, it returns `#f`

.

Inspection

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.

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

and `make-eqv-hashtable`

, `#f`

is returned. This behavior can be disabled if boolean parameter *force?* is being provided and set to `#t`

. In this case, `hashtable-hash-function`

will also return hash functions for `eq`

and `eqv`

-based hashtables.

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.

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.

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.

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.

Returns an integer hash value for boolean *b*.

Returns an integer hash value for character *ch*. This hash function is suitable for use with `char=?`

as an equivalence function.

Returns an integer hash value for character *ch*, ignoring case. This hash function is suitable for use with `char-ci=?`

as an equivalence function.

Returns an integer hash value for string *str*, based on its current characters. This hash function is suitable for use with `string=?`

as an equivalence function.

Returns an integer hash value for string *str* based on its current characters, ignoring case. This hash function is suitable for use with `string-ci=?`

as an equivalence function.

Returns an integer hash value for symbol *sym*.

Returns an integer hash value for numeric value *x*.

Combines the integer hash values *h ...* into a single hash value.

Procedures

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

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

Returns the value in *hashtable* associated with *key*. If *hashtable* does not contain an association for *key*, *default* is returned.

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

.

Changes *hashtable* to associate *key* with *obj*, adding a new association or replacing any existing association for *key*.

Removes any association for *key* within *hashtable*.

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

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`

.

Adds all the associations from *alist* to *hashtable* using `hashtable-add!`

.

Returns `#t`

if *hashtable* contains an association for *key*, `#f`

otherwise.

`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:

Removes all associations from *hashtable*. If a second argument *k* is given, the current capacity of the hashtable is reset to approximately *k* elements.

Returns an immutable vector of all keys in *hashtable*.

Returns an immutable vector of all values in *hashtable*.

Returns two values, an immutable vector of the keys in *hashtable*, and an immutable vector of the corresponding values.

Returns a list of all keys in *hashtable*.

Returns a list of all values in *hashtable*.

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.

Applies *proc* to every association in *hashtable*. *proc* should be a procedure accepting two values, a key and a corresponding value.

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

Includes all associations from *hashtable2* in *hashtable1* if the key of the association is not already contained in *hashtable1*.

Removes all associations from *hashtable1* for which the key of the association is not contained in *hashtable2*.

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.

**(alist->equal-hashtable ****alist****)**
**(alist->equal-hashtable ****alist k****)**

**(hashtable-copy ****hashtable****)**
**(hashtable-copy ****hashtable mutable****)**

**(hashtable-empty-copy ****hashtable****)**

**(hashtable? ****obj****)**

**(eq-hashtable? ****obj****)**

**(eqv-hashtable? ****obj****)**

**(equal-hashtable? ****obj****)**

**(hashtable-equivalence-function ****hashtable****)**

**(hashtable-hash-function ****hashtable****)**
**(hashtable-hash-function ****hashtable force?****)**

**(hashtable-mutable? ****hashtable****)**

**(equal-hash ****obj****)**

**(eqv-hash ****obj****)**

**(eq-hash ****obj****)**

**(boolean-hash ****b****)**

**(char-hash ****ch****)**

**(char-ci-hash ****ch****)**

**(string-hash ****str****)**

**(string-ci-hash ****str****)**

**(symbol-hash ****sym****)**

**(number-hash ****x****)**

**(combine-hash ****h ...****)**

**(hashtable-size ****hashtable****)**

**(hashtable-load ****hashtable****)**

**(hashtable-ref ****hashtable key default****)**

**(hashtable-get ****hashtable key****)**

**(hashtable-set! ****hashtable key obj****)**

**(hashtable-delete! ****hashtable key****)**

**(hashtable-add! ****hashtable key obj****)**

**(hashtable-remove! ****hashtable key****)**

**(alist->hashtable! ****hashtable alist****)**

**(hashtable-contains? ****hashtable key****)**

**(hashtable-update! ****hashtable key proc default****)**

**(hashtable-clear! ****hashtable****)**
**(hashtable-clear! ****hashtable k****)**

**(hashtable-keys ****hashtable****)**

**(hashtable-values ****hashtable****)**

**(hashtable-entries ****hashtable****)**

**(hashtable-key-list ****hashtable****)**

**(hashtable-value-list ****hashtable****)**

**(hashtable->alist ****hashtable****)**

**(hashtable-for-each ****proc hashtable****)**

**(hashtable-map! ****proc hashtable****)**

**(hashtable-union! ****hashtable1 hashtable2****)**

**(hashtable-intersection! ****hashtable1 hashtable2****)**

**(hashtable-difference! ****hashtable1 hashtable2****)**