Comment on page

# (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.**(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.**(alist->equal-hashtable**

*alist***)**

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

**(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.**(hashtable-empty-copy**

*hashtable***)**

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

*hashtable*.**(hashtable?**

*obj***)**

Returns

`#t`

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

.**(eq-hashtable?**

*obj***)**

Returns

`#t`

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

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

.**(eqv-hashtable?**

*obj***)**

Returns

`#t`

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

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

.**(equal-hashtable?**

*obj***)**

Returns

`#t`

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

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

.**(hashtable-equivalence-function**

*hashtable***)**

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

**(hashtable-hash-function**

*hashtable force?***)**

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.**(hashtable-mutable?**

*hashtable***)**

Returns

`#t`

if hashtable is mutable, otherwise `#f`

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

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

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

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

*b***)**

Returns an integer hash value for boolean

*b*.**(char-hash**

*ch***)**

Returns an integer hash value for character

*ch*. This hash function is suitable for use with`char=?`

as an equivalence function.**(char-ci-hash**

*ch***)**

Returns an integer hash value for character

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

as an equivalence function.**(string-hash**

*str***)**

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.**(string-ci-hash**

*str***)**

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

*sym***)**

Returns an integer hash value for symbol

*sym*.**(number-hash**

*x***)**

Returns an integer hash value for numeric value

*x*.**(combine-hash**

*h ...***)**

Combines the integer hash values

*h ...*into a single hash value.**(hashtable-size**

*hashtable***)**

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

**(hashtable-load**

*hashtable***)**

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

Returns the value in

*hashtable*associated with*key*. If*hashtable*does not contain an association for*key*,*default*is returned.**(hashtable-get**

*hashtable key***)**

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

Changes

*hashtable*to associate*key*with*obj*, adding a new association or replacing any existing association for*key*.**(hashtable-delete!**

*hashtable key***)**

Removes any association for

*key*within*hashtable*.**(hashtable-add!**

*hashtable key obj***)**

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

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

Adds all the associations from

*alist*to*hashtable*using`hashtable-add!`

.**(hashtable-contains?**

*hashtable key***)**

Returns

`#t`

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

otherwise.**(hashtable-update!**

*hashtable key proc default***)**

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

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

Returns an immutable vector of all keys in

*hashtable*.**(hashtable-values**

*hashtable***)**

Returns an immutable vector of all values in

*hashtable*.**(hashtable-entries**

*hashtable***)**

Returns two values, an immutable vector of the keys in

*hashtable*, and an immutable vector of the corresponding values.**(hashtable-key-list**

*hashtable***)**

Returns a list of all keys in

*hashtable*.**(hashtable-value-list**

*hashtable***)**

Returns a list of all values in

*hashtable*.**(hashtable->alist**

*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.**(hashtable-for-each**

*proc hashtable***)**

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

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.**(hashtable-union!**

*hashtable1 hashtable2***)**

Includes all associations from

*hashtable2*in*hashtable1*if the key of the association is not already contained in*hashtable1*.**(hashtable-intersection!**

*hashtable1 hashtable2***)**

Removes all associations from

*hashtable1*for which the key of the association is not contained in*hashtable2*.**(hashtable-difference!**

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

Last modified 1yr ago