Previous: Hash Table Examples, Up: Hash Tables [Contents][Index]
Like the association list functions, the hash table functions come in
several varieties, according to the equality test used for the keys.
Plain hash- functions use equal?, hashq-
functions use eq?, hashv- functions use eqv?, and
the hashx- functions use an application supplied test.
A single make-hash-table creates a hash table suitable for use
with any set of functions, but it’s imperative that just one set is
then used consistently, or results will be unpredictable.
Hash tables are implemented as a vector indexed by a hash value formed
from the key, with an association list of key/value pairs for each
bucket in case distinct keys hash together. Direct access to the
pairs in those lists is provided by the -handle- functions.
When the number of entries in a hash table goes above a threshold, the vector is made larger and the entries are rehashed, to prevent the bucket lists from becoming too long and slowing down accesses. When the number of entries goes below a threshold, the vector is shrunk to save space.
For the hashx- “extended” routines, an application supplies a
hash function producing an integer index like hashq etc
below, and an assoc alist search function like assq etc
(see Retrieving Alist Entries). Here’s an example of such
functions implementing case-insensitive hashing of string keys,
(use-modules (srfi srfi-1)
(srfi srfi-13))
(define (my-hash str size)
(remainder (string-hash-ci str) size))
(define (my-assoc str alist)
(find (lambda (pair) (string-ci=? str (car pair))) alist))
(define my-table (make-hash-table))
(hashx-set! my-hash my-assoc my-table "foo" 123)
(hashx-ref my-hash my-assoc my-table "FOO")
⇒ 123
In a hashx- hash function the aim is to spread keys
across the vector, so bucket lists don’t become long. But the actual
values are arbitrary as long as they’re in the range 0 to
size-1. Helpful functions for forming a hash value, in
addition to hashq etc below, include symbol-hash
(see Symbol Keys), string-hash and string-hash-ci
(see String Comparison), and char-set-hash
(see Character Set Predicates/Comparison).
Create a new hash table object, with an optional minimum vector size.
When size is given, the table vector will still grow and shrink automatically, as described above, but with size as a minimum. If an application knows roughly how many entries the table will hold then it can use size to avoid rehashing when initial entries are added.
Convert alist into a hash table. When keys are repeated in alist, the leftmost association takes precedence.
(use-modules (ice-9 hash-table)) (alist->hash-table '((foo . 1) (bar . 2)))
When converting to an extended hash table, custom hash and assoc procedures must be provided.
(alist->hashx-table hash assoc '((foo . 1) (bar . 2)))
Return #t if obj is a abstract hash table object.
Remove all items from table (without triggering a resize).
Lookup key in the given hash table, and return the
associated value. If key is not found, return dflt, or
#f if dflt is not given.
Associate val with key in the given hash table. If key is already present then it’s associated value is changed. If it’s not present then a new entry is created.
Remove any association for key in the given hash table. If key is not in table then nothing is done.
Return a hash value for key. This is a number in the range 0 to size-1, which is suitable for use in a hash table of the given size.
Note that hashq and hashv may use internal addresses of
objects, so if an object is garbage collected and re-created it can
have a different hash value, even when the two are notionally
eq?. For instance with symbols,
(hashq 'something 123) ⇒ 19 (gc) (hashq 'something 123) ⇒ 62
In normal use this is not a problem, since an object entered into a hash table won’t be garbage collected until removed. It’s only if hashing calculations are somehow separated from normal references that its lifetime needs to be considered.
Return the (key . value) pair for key in the
given hash table, or #f if key is not in
table.
Return the (key . value) pair for key in the
given hash table. If key is not in table then
create an entry for it with init as the value, and return that
pair.
Apply proc to the entries in the given hash table. Each
call is (proc key value). hash-map->list
returns a list of the results from these calls, hash-for-each
discards the results and returns an unspecified value.
Calls are made over the table entries in an unspecified order, and for
hash-map->list the order of the values in the returned list is
unspecified. Results will be unpredictable if table is modified
while iterating.
For example the following returns a new alist comprising all the
entries from mytable, in no particular order.
(hash-map->list cons mytable)
Apply proc to the entries in the given hash table. Each
call is (proc handle), where handle is a
(key . value) pair. Return an unspecified value.
hash-for-each-handle differs from hash-for-each only in
the argument list of proc.
Accumulate a result by applying proc to the elements of the
given hash table. Each call is (proc key
value prior-result), where key and value are
from the table and prior-result is the return from the
previous proc call. For the first call, prior-result is
the given init value.
Calls are made over the table entries in an unspecified order.
Results will be unpredictable if table is modified while
hash-fold is running.
For example, the following returns a count of how many keys in
mytable are strings.
(hash-fold (lambda (key value prior)
(if (string? key) (1+ prior) prior))
0 mytable)
Return the number of elements in the given hash table that cause
(pred key value) to return true. To quickly
determine the total number of elements, use (const #t) for
pred.
Previous: Hash Table Examples, Up: Hash Tables [Contents][Index]