# (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)** \ \&#xNAN;**(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)** \ \&#xNAN;**(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)** \ \&#xNAN;**(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*****)** \ \&#xNAN;**(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*****)** \ \&#xNAN;**(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*****)** \ \&#xNAN;**(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*****)** \ \&#xNAN;**(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*****)** \ \&#xNAN;**(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*. ## Type tests **(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`. ## Inspection **(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*****)** \ \&#xNAN;**(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`. ## 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*****)** 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. ## Procedures **(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: ```scheme (hashtable-set! hashtable key (proc (hashtable-ref hashtable key default))) ``` **(hashtable-clear! *****hashtable*****)** \ \&#xNAN;**(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. ## Composition **(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](http://www.r6rs.org/final/html/r6rs-lib/r6rs-lib-Z-H-14.html#node_chap_13) by Michael Sperber, Kent Dybvig, Matthew Flatt, Anton van Straaten, Richard Kelsey, William Clinger, and Jonathan Rees.