4.14 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. Use immutable? to check whether a hash table is immutable.

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.

For equal?-based hashing, the built-in hash functions on strings, pairs, lists, vectors, prefab or transparent structures, etc., take time proportional to the size of the value. The hash code for a compound data structure, such as a list or vector, depends on hashing each item of the container, but the depth of such recursive hashing is limited (to avoid potential problems with cyclic data). For a non-list pair, both car and cdr hashing is treated as a deeper hash, but the cdr of a list is treated as having the same hashing depth as the list.

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. Empty immutable hash tables are eq? when they are equal?.

Changed in version 7.2.0.9 of package base: Made empty immutable hash tables eq? when they are equal?.

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-ref-key, 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, hash-for-each, and hash-clear! 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.

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.

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.

Beware that values in the table are retained normally. If a value in the table refers back to its key, then the table will retain the value and therefore the key; the mapping will never be removed from the table even if the key becomes otherwise inaccessible. To avoid that problem, instead of mapping the key to the value, map the key to an ephemeron that pairs the key and value. Beware further, however, that an ephemeron’s value might be cleared between retrieving an ephemeron and extracting its value, depending on whether the key is otherwise reachable. For eq?-based mappings, consider using the pattern (ephemeron-value ephemeron #f key) to extract the value of ephemeron while ensuring that key is retained until the value is extracted.

See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.

See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.

See also the caveat concerning mutable keys above.

See also the caveat concerning mutable keys above.

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

If hash is not an impersonator, then the returned key, assuming it is found, will be eq?-equivalent to the one actually retained by hash:

If a mutable hash is updated multiple times using keys that are not eq?-equivalent but are equivalent according to the hash’s key-comparison procedure, the hash retains the first one:

If hash is an impersonator, then the returned key will be determined as described in the documentation to impersonate-hash.

See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.

Added in version 7.4.0.3 of package base.

See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.

See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.

See also the caveat concerning mutable keys above.

See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.

See also the caveat concerning mutable keys above.

If hash is not an impersonator, then all mappings are removed in constant time. If hash is an impersonator, then each key is removed one-by-one using hash-remove!.

See also the caveats concerning concurrent modification and the caveat concerning mutable keys above.

If hash is not a chaperone, then clearing is equivalent to creating a new hash table, and the operation is performed in constant time. If hash is a chaperone, then each key is removed one-by-one using hash-remove.

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.

If try-order? is true, then the order of keys and values passed to proc is normalized under certain circumstances—including when every key is one of the following and with the following order (earlier bullets before later):

• booleans sorted #f before #t;

• characters sorted by char<?;

• real numbers sorted by <;

• symbols sorted with uninterned symbols before unreadable symbols before interned symbols, then sorted by symbol<?;

• keywords sorted by keyword<?;

• strings sorted by string<?;

• byte strings sorted by bytes<?;

• null;

• #<void>; and

• eof.

Changed in version 6.3 of package base: Added the try-order? argument.
Changed in version 7.1.0.7: Added guarantees for try-order?.

Using hash-keys-subset? on immutable hash tables can be much faster than iterating through the keys of hash1 to make sure that each is in hash2.

Added in version 6.5.0.8 of package base.

Changed in version 6.3 of package base: Added the try-order? argument.
Changed in version 7.1.0.7: Added guarantees for try-order?.

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. More generally, an index is guaranteed to be a valid hash index for a given hash table only as long it comes from hash-iterate-first or hash-iterate-next, and only as long as the hash table is not modified. In the case of a hash table with weakly held keys, the hash table can be implicitly modified by the garbage collector (see Garbage Collection) when it discovers that the key is not reachable.

If pos is not a valid hash index of hash, then the result may be #f or it may be the next later index that remains valid. The latter result is guaranteed if a hash table has been modified only by the removal of keys.

Changed in version 7.0.0.10 of package base: Handle an invalid index by returning #f instead of raising exn:fail:contract.

If pos is not a valid hash index for hash, the result is bad-index-v if provided, otherwise the exn:fail:contract exception is raised.

Changed in version 7.0.0.10 of package base: Added the optional bad-index-v argument.

If pos is not a valid hash index for hash, the result is bad-index-v if provided, otherwise the exn:fail:contract exception is raised.

Changed in version 7.0.0.10 of package base: Added the optional bad-index-v argument.

If pos is not a valid hash index for hash, the result is (cons bad-index-v bad-index-v) if bad-index-v is provided, otherwise the exn:fail:contract exception is raised.

Added in version 6.4.0.5 of package base.
Changed in version 7.0.0.10: Added the optional bad-index-v argument.

If pos is not a valid hash index for hash, the result is (values bad-index-v bad-index-v) if bad-index-v is provided, otherwise the exn:fail:contract exception is raised.

Added in version 6.4.0.5 of package base.
Changed in version 7.0.0.10: Added the optional bad-index-v argument.

4.14.1 Additional Hash Table Functions

Added in version 7.8.0.11 of package base.