3.10 Hash Tables
A hash table implements a maping from keys to values, where both keys can values can be arbitrary Scheme values, and access and update to the tabel are normally constant-time operations. Keys are compared using equal? or eq?, depending on whether the hash table is created with the 'equal flag.
Examples: |
> (define ht (make-hash-table 'equal)) |
> (hash-table-put! ht "apple" '(red round)) |
> (hash-table-put! ht "banana" '(yellow long)) |
> (hash-table-get ht "apple") |
(red round) |
> (hash-table-get ht "coconut") |
hash-table-get: no value found for key: "coconut" |
> (hash-table-get ht "coconut" "not there") |
"not there" |
A literal hash table can be written as an expression by using #hash (for an equal?-based table) or #hasheq (for an eq?-based table). A parenthesized sequence must immediately follow #hash or #hasheq, where each element is a sequence is a dotted key–value pair. Literal hash tables are immutable.
Examples: |
> (define ht #hash(("banana" yellow long) ("apple" red round))) |
> (hash-table-get ht "apple") |
(red round) |
Reading Hash Tables in PLT Scheme Reference documents the fine points of the syntax of hash table literals.
A hash table can optionally retain its keys weakly, so each mapping is retained only so long as the key is retained elsewhere.
Examples: |
> (define ht (make-hash-table 'weak)) |
> (hash-table-put! ht (gensym) "can you see me?") |
> (collect-garbage) |
> (hash-table-count ht) |
0 |
Beware that even a weak hash table retains its values strongly, as long as the corresponding key is accessible. This creates a catch-22 dependency when a value refers back to its key, so that the mapping is retained permanently. To break the cycle, map the key to an ephemeron that pairs the value with its key (in addition to the implicit pairing of the hash table).
Examples: | ||
> (define ht (make-hash-table 'weak)) | ||
| ||
> (collect-garbage) | ||
> (hash-table-count ht) | ||
1 |
> (define ht (make-hash-table 'weak)) | ||
| ||
> (collect-garbage) | ||
> (hash-table-count ht) | ||
0 |
Hash Tables in PLT Scheme Reference provides more on hash tables and hash-table procedures.