3.10 Hash Tables

A hash table implements a mapping from keys to values, where both keys and values can be arbitrary Scheme values, and access and update to the table are normally constant-time operations. Keys are compared using equal? or eq?, depending on whether the hash table is created with make-hash or make-hasheq.

Examples:

> (define ht (make-hash))

> (hash-set! ht "apple" '(red round))

> (hash-set! ht "banana" '(yellow long))

> (hash-ref ht "apple")

(red round)

> (hash-ref ht "coconut")

hash-ref: no value found for key: "coconut"

> (hash-ref 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, but they can be extended functionally (producing a new hash table without changing the old one) using hash-set.

Examples:

> (define ht #hash(("apple" . red) ("banana" . yellow)))

> (hash-ref ht "apple")

red

> (define ht2 (hash-set ht "coconut" 'brown))

> (hash-ref ht "coconut")

hash-ref: no value found for key: "coconut"

> (hash-ref ht2 "coconut")

brown

> ht2

#hash(("apple" . red) ("banana" . yellow) ("coconut" . brown))

Reading Hash Tables in Reference: PLT Scheme 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-weak-hasheq))

> (hash-set! ht (gensym) "can you see me?")

> (collect-garbage)

> (hash-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-weak-hasheq))

> (let ([g (gensym)])       (hash-set! ht g (list g)))

> (collect-garbage)

> (hash-count ht)

1

> (define ht (make-weak-hasheq))

> (let ([g (gensym)])       (hash-set! ht g (make-ephemeron g (list g))))

> (collect-garbage)

> (hash-count ht)

0

Hash Tables in Reference: PLT Scheme provides more on hash tables and hash-table procedures.