3.13 Hash Tables
Hash Tables in The Racket Guide introduces hash tables.
A hash table (or simply hash) maps each of its
keys to a single value. For a given hash table, keys are equivalent
via equal?, eqv?, or eq?, and keys are
retained either strongly or weakly (see Weak Boxes). A hash
table is also either mutable or immutable. Immutable hash tables
support effectively constant-time access and update, just like mutable
hash tables; the constant on immutable operations is usually larger,
but the functional nature of immutable hash tables can pay off in
certain algorithms.
Immutable hash tables actually provide O(log N)
access and update. Since N is limited by the address space so
that log N is limited to less than 30 or 62 (depending on the
platform), log N can be treated reasonably as a constant.
A hash table can be used as a two-valued sequence (see
Sequences). The keys and values of the hash table serve as
elements of the sequence (i.e., each element is a key and its
associated value). If a mapping is added to or removed from the hash
table during iteration, then an iteration step may fail with
exn:fail:contract, or the iteration may skip or duplicate
keys and values. See also in-hash, in-hash-keys,
in-hash-values, and in-hash-pairs.
Two hash tables cannot be equal? unless they use the same
key-comparison procedure (equal?, eqv?, or
eq?), both hold keys strongly or weakly, and have the same
mutability.
Caveats concerning concurrent
modification: A mutable hash table can be manipulated with
hash-ref, hash-set!, and hash-remove!
concurrently by multiple threads, and the operations are protected by
a table-specific semaphore as needed. Three caveats apply, however:
If a thread is terminated while applying hash-ref,
hash-set!, hash-remove!, hash-ref!,
or hash-update! to a hash table that
uses equal? or eqv? key comparisons, all current
and future operations on the hash table may block indefinitely.
The hash-map and hash-for-each procedures do
not use the table’s semaphore to guard the traversal as a whole.
Changes by one thread to a hash table can affect the keys and values
seen by another thread part-way through its traversal of the same
hash table.
The hash-update! and hash-ref! functions
use a table’s semaphore
independently for the hash-ref and hash-set! parts
of their functionality, which means that the update as a whole is not
“atomic.”
Caveat concerning mutable
keys: If a key in an equal?-based hash table is mutated
(e.g., a key string is modified with string-set!), then the
hash table’s behavior for insertion and lookup operations becomes
unpredictable.
A literal or printed hash table starts with #hash,
#hasheqv, or
#hasheq. See Reading Hash Tables
for information on reading
hash tables and Printing Hash Tables
for information on printing hash tables.
Returns
#t if
hash compares keys with
equal?,
#f if it compares with
eq? or
eqv?.
Returns
#t if
hash compares keys with
eqv?,
#f if it compares with
equal? or
eq?.
Returns
#t if
hash compares keys with
eq?,
#f if it compares with
equal? or
eqv?.
Returns #t if hash retains its keys weakly,
#f if it retains keys strongly.
Creates an immutable hash table with each given
key mapped to
the following
val; each
key must have a
val,
so the total number of arguments to
hash must be even.
The hash procedure creates a table where keys are compared
with equal?, hasheq procedure creates a table where
keys are compared with eq?, and hasheqv procedure
creates a table where keys are compared with eqv?.
The key to val mappings are added to the table in
the order that they appear in the argument list, so later mappings can
hide earlier mappings if the keys are equal.
Creates a mutable hash table that holds keys strongly.
The make-hash procedure creates a table where keys are
compared with equal?, make-hasheq procedure creates
a table where keys are compared with eq?, and
make-hasheqv procedure creates a table where keys are
compared with eqv?.
The table is initialized with the content of assocs. In each
element of assocs, the car is a key, and the
cdr is the corresponding value. The mappings are added to the
table in the order that they appear in assocs, so later
mappings can hide earlier mappings.
See also make-custom-hash.
Maps key to v in hash, overwriting
any existing mapping for key.
See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.
Maps each key to each v in hash, overwriting
any existing mapping for each key. Mappings are added from the left, so
later mappings overwrite earlier mappings.
See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.
Functionally extends hash by mapping key to
v, overwriting any existing mapping for key, and
returning the extended hash table.
See also the caveat concerning mutable keys above.
Functionally extends hash by mapping each key to
v, overwriting any existing mapping for each key, and
returning the extended hash table. Mappings are added from the left, so
later mappings overwrite earlier mappings.
See also the caveat concerning mutable keys above.
Returns the value for key in hash. If no value
is found for key, then failure-result determines the
result:
If failure-result is a procedure, it is called
(through a tail call) with no arguments to produce the result.
Otherwise, failure-result is returned as the result.
See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.
Returns the value for
key in
hash. If no value is
found for
key, then
to-set determines the result as
in
hash-ref (i.e., it is either a thunk that computes a value
or a plain value), and this result is stored in
hash for the
key. (Note that if
to-set is a thunk, it is not
invoked in tail position.)
See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.
Returns #t if hash contains a value for the given
key, #f otherwise.
Composes
hash-ref and
hash-set! to update an
existing mapping in
hash, where the optional
failure-result argument is used as in
hash-ref when
no mapping exists for
key already. See the caveat above about
concurrent updates.
See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.
Composes
hash-ref and
hash-set to functionally
update an existing mapping in
hash, where the optional
failure-result argument is used as in
hash-ref when
no mapping exists for
key already.
See also the caveat concerning mutable keys above.
Removes any existing mapping for key in hash.
See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.
Functionally removes any existing mapping for key in
hash, returning the fresh hash table.
See also the caveat concerning mutable keys above.
Applies the procedure proc to each element in
hash in an unspecified order, accumulating the results
into a list. The procedure proc is called each time with a
key and its value.
If a hash table is extended with new keys (either through
proc or by another thread) while a hash-map or
hash-for-each traversal is in process, arbitrary key–value
pairs can be dropped or duplicated in the traversal. Key mappings can
be deleted or remapped (by any thread) with no adverse affects; the
change does not affect a traversal if the key has been seen already,
otherwise the traversal skips a deleted key or uses the remapped key’s
new value.
See also the caveats concerning concurrent modification above.
Returns a list of the keys of hash in an unspecified order.
Returns a list of the values of hash in an unspecified order.
Returns a list of the key–value pairs of hash in an unspecified order.
Applies proc to each element in hash (for the
side-effects of proc) in an unspecified order. The procedure
proc is called each time with a key and its value.
See
hash-map for information about modifying
hash
within
proc.
Returns the number of keys mapped by hash. Unless hash
retains keys weakly, the result is computed in
constant time and atomically. If hash retains it keys weakly, a
traversal is required to count the keys.
Returns #f if hash contains no elements, otherwise
it returns an integer that is an index to the first element in the hash
table; “first” refers to an unspecified ordering of the table
elements, and the index values are not necessarily consecutive
integers. For a mutable hash, this index is guaranteed to
refer to the first item only as long as no items are added to or
removed from hash.
Returns either an integer that is an index to the element in
hash after the element indexed by
pos (which is not
necessarily one more than
pos) or
#f if
pos
refers to the last element in
hash. If
pos is not a
valid index, then the
exn:fail:contract exception is raised. For a mutable
hash, the result index is guaranteed to refer to its item
only as long as no items are added to or removed from
hash.
Returns the key for the element in
hash at index
pos. If
pos is not a valid index for
hash, the
exn:fail:contract exception is raised.
Returns the value for the element in
hash at index
pos. If
pos is not a valid index for
hash, the
exn:fail:contract exception is raised.
Returns a mutable hash table with the same mappings, same
key-comparison mode, and same key-holding strength as hash.
Returns a
fixnum; for any two calls with
eq? values,
the returned number is the same.
Equal fixnums are always eq?.
Returns a
fixnum; for any two calls with
eqv? values,
the returned number is the same.
Returns a
fixnum; for any two calls with
equal? values,
the returned number is the same. A hash code is computed even when
v contains a cycle through pairs, vectors, boxes, and/or
inspectable structure fields. See also
prop:equal+hash.
Like
equal-hash-code, but computes a secondary value suitable
for use in double hashing.