► |  | Reference: PLT Scheme

1 | Language Model
2 | Syntactic Forms
3 | Datatypes
4 | Structures
5 | Classes and Objects
6 | Units
7 | Contracts
8 | Pattern Matching
9 | Control Flow
10 | Concurrency
11 | Macros
12 | Input and Output
13 | Reflection and Security
14 | Operating System
15 | Memory Management
16 | Running PLT Scheme
| Bibliography
| Index

▼ | 3 | Datatypes

3.1 | Booleans and Equality
3.2 | Numbers
3.3 | Strings
3.4 | Byte Strings
3.5 | Characters
3.6 | Symbols
3.7 | Regular Expressions
3.8 | Keywords
3.9 | Pairs and Lists
3.10 | Mutable Pairs and Lists
3.11 | Vectors
3.12 | Boxes
3.13 | Hash Tables
3.14 | Sequences
3.15 | Dictionaries
3.16 | Procedures
3.17 | Void and Undefined

On this page:

hash?
hash-eqv?
hash-eq?
hash-weak?
make-hash
make-hasheqv
make-hasheq
make-weak-hash
make-weak-hasheqv
make-weak-hasheq
make-immutable-hash
make-immutable-hasheqv
make-immutable-hasheq
hash-set!
hash-set
hash-ref
hash-update!
hash-update
hash-remove!
hash-remove
hash-map
hash-for-each
hash-count
hash-iterate-first
hash-iterate-next
hash-iterate-key
hash-iterate-value
hash-copy
eq-hash-code
eqv-hash-code
equal-hash-code
equal-secondary-hash-code

Version: 4.1.4
top← prev up next →

#### 3.13`` Hash Tables

Hash Tables in Guide: PLT Scheme 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 tables support constant-time functional update.

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!, or hash-remove! to a hash table that uses equal? key comparisons, all current and future operations on the hash table block indefinitely.

- The hash-map and hash-for-each procedures do not use the table’s semaphore. Consequently, if a hash table is extended with new keys by another thread while a map or for-each traversal is in process, arbitrary key–value pairs can be dropped or duplicated in the traversal. Similarly, if a map or for-each procedure itself extends the table, arbitrary key–value pairs can be dropped or duplicated. However, key mappings can be deleted or remapped by any thread with no adverse affects (i.e., 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).

- The hash-update! function uses a table’s semaphore independently for the hash-ref and hash-set! parts of its functionality, which means that the update as a whole is not “atomic.”

Caveat concerning mutable keys: If a key into 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.

(hash? v) → boolean?
v : any/c

Returns #t if v is a hash table, #f otherwise.

(hash-eqv? hash) → boolean?
hash : hash?

Returns #t if hash compares keys with eqv?, #f if it compares with equal? or eq?.

(hash-eq? hash) → boolean?
hash : hash?

Returns #t if hash compares keys with eq?, #f if it compares with equal? or eqv?.

(hash-weak? hash) → boolean?
hash : hash?

Returns #t if hash retains its keys weakly, #f if it retains keys strongly.

(make-hash) → hash?

Creates an empty mutable hash table that holds keys strongly and that uses equal? to compare keys. See also make-custom-hash.

(make-hasheqv) → (and/c hash? hash-eqv?)

Creates an empty mutable hash table that holds keys strongly and that uses eqv? to compare keys.

(make-hasheq) → (and/c hash? hash-eq?)

Creates an empty mutable hash table that holds keys strongly and that uses eq? to compare keys.

(make-weak-hash) → (and/c hash? hash-weak?)

Creates an empty mutable hash table that holds keys weakly and that uses equal? to compare keys. See also make-weak-custom-hash.

(make-weak-hasheqv) → (and/c hash? hash-eqv? hash-weak?)

Creates an empty mutable hash table that holds keys weakly and that uses eqv? to compare keys.

(make-weak-hasheq) → (and/c hash? hash-eq? hash-weak?)

Creates an empty mutable hash table that holds keys weakly and that uses eq? to compare keys.

(make-immutable-hash assocs) → (and/c hash? immutable?)
assocs : (listof pair?)

Creates an immutable hash table that compares keys with equal?. In each element of assocs, the car of each pair 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.

(make-immutable-hasheqv assocs)
→ (and/c hash? hash-eqv? immutable?)
assocs : (listof pair?)

Like make-immutable-hash, but the resulting hash table compares keys with eqv?.

(make-immutable-hasheq assocs)
→ (and/c hash? hash-eq? immutable?)
assocs : (listof pair?)

Like make-immutable-hash, but the resulting hash table compares keys with eq?.

(hash-set! hash key v) → void?
hash : (and/c hash? (not/c immutable?))
key : any/c
v : any/c

Maps key to v in hash, overwriting any existing mapping for key.

(hash-set hash key v) → (and/c hash? immutable?)
hash : (and/c hash? immutable?)
key : any/c
v : any/c

Functionally extends hash by mapping key to v, overwriting any existing mapping for key, and returning the extended hash table.

(hash-ref hash key [failure-result]) → any
hash : hash?
key : any/c

| failure-result |  | : |  | any/c

=

(lambda ()
(raise (make-exn:fail:contract ....)))

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.

(hash-update! |  | hash |  |  |  |
|  | key |  |  |  |
|  | updater |  |  |  |
| [ | failure-result]) |  | → |  | void?

hash : (and/c hash? (not/c immutable?))
key : any/c
updater : (any/c . -> . any/c)

| failure-result |  | : |  | any/c

=

(lambda ()
(raise (make-exn:fail:contract ....)))

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.

(hash-update hash key updater [failure-result])
→ (and/c hash? immutable?)
hash : (and/c hash? immutable?)
key : any/c
updater : (any/c . -> . any/c)

| failure-result |  | : |  | any/c

=

(lambda ()
(raise (make-exn:fail:contract ....)))

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.

(hash-remove! hash key) → void?
hash : (and/c hash? (not/c immutable?))
key : any/c

Removes any existing mapping for key in hash.

(hash-remove hash key) → (and/c hash? immutable?)
hash : (and/c hash? immutable?)
key : any/c

Functionally removes any existing mapping for key in hash, returning the fresh hash table.

(hash-map hash proc) → (listof any/c)
hash : hash?
proc : (any/c any/c . -> . any/c)

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. See the caveat above about concurrent modification.

(hash-for-each hash proc) → void?
hash : hash?
proc : (any/c any/c . -> . any)

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 the caveat above about concurrent modification.

(hash-count hash) → exact-nonnegative-integer?
hash : hash?

Returns the number of keys mapped by hash. If hash is not created with 'weak, then the result is computed in constant time and atomically. If hash is created with 'weak, see the caveat above about concurrent modification.

(hash-iterate-first hash)
→ (or/c #f exact-nonnegative-integer?)
hash : hash?

Returns #f if hash contains no elements, otherwise it returns an integer that is a 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.

(hash-iterate-next hash pos)
→ (or/c #f exact-nonnegative-integer?)
hash : hash?
pos : exact-nonnegative-integer?

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.

(hash-iterate-key hash pos) → any
hash : hash?
pos : exact-nonnegative-integer?

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.

(hash-iterate-value hash pos) → any
hash : hash?
pos : exact-nonnegative-integer?

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.

(hash-copy hash) → (and/c hash? (not/c immutable?))
hash : hash?

Returns a mutable hash table with the same mappings, same key-comparison mode, and same key-holding strength as hash.

(eq-hash-code v) → exact-integer?
v : any/c

Returns an exact integer; for any two eq? values, the returned integer is the same. Furthermore, for the result integer k and any other exact integer j, (= k j) implies (eq? k j).

(eqv-hash-code v) → exact-integer?
v : any/c

Returns an exact integer; for any two eqv? values, the returned integer is the same. Furthermore, for the result integer k and any other exact integer j, (= k j) implies (eq? k j).

(equal-hash-code v) → exact-integer?
v : any/c

Returns an exact integer; for any two equal? values, the returned integer is the same. Furthermore, for the result integer k and any other exact integer j, (= k j) implies (eq? k j). A has code is computed even when v contains a cycle through pairs, vectors, boxes, and/or inspectable structure fields. See also prop:equal+hash.

(equal-secondary-hash-code v) → exact-integer?
v : any/c

Like equal-hash-code, but computes a secondary value suitable for use in double hashing.

top← prev up next →