Hashes¶

Overview¶

A hash is a collection of key–value associations. Each key in a hash is associated with exactly one value, and no duplicate keys are permitted. Conceptually, a hash allows you to “look up” a value by providing its corresponding key. Hashes are sometimes referred to as dictionaries, hashmaps, tables, or associative arrays in other languages. In this implementation, hashes are constructed using the hash procedure and manipulated with procedures such as hash-get, hash-add!, and hash-remove!.

In mathematical terms, a hash represents a function from a set of keys to a set of values. Each key uniquely determines its associated value. Unlike lists, where values are accessed by numeric position, hashes are accessed by key. For example, instead of asking “what is the third element?”, you ask “what value is associated with this key?” This makes hashes especially useful when data is naturally described by named or symbolic attributes, such as configuration settings, record fields, caches, lookup tables, frequency counters, or indexing structures.

Internally, hashes are implemented using a hash table. A hash table stores key–value pairs in an array and uses a hash function to convert each key into a numeric index. When a key is inserted or looked up, the hash function determines where it should be stored or searched for. Because this computation is fast and avoids scanning the entire collection, hash tables typically provide very efficient average-case performance for insertion, deletion, and lookup operations. In practice, these operations are close to constant time for well-distributed hash functions. This makes hashes far more efficient than linear data structures such as lists when frequent lookups are required.

In order for a key to be stored in a hash, it must be hashable. Hashable objects are those whose value can be converted into a stable hash code suitable for indexing. The following types are hashable:

string
symbol
integer
rational
real
complex
boolean
char

Keys must be one of these types. Attempting to use a non-hashable object as a key will raise a type error. In contrast, hash values may be any first-class object, including lists, vectors, sets, hashes, procedures, numbers, strings, or user-defined types. Only keys are restricted; values are unrestricted.

Hashes should be distinguished from association lists (alists). An association list is simply a list of dotted pairs, where each pair contains a key in its car and a value in its cdr. For example:

--> '((name . "Alice")
...    (age . 30)
...    (city . "Toronto"))
((name . "Alice") (age . 30) (city . "Toronto"))

Alists are simple, portable, and easy to manipulate using standard list procedures. However, alist lookups require scanning the list sequentially, which becomes slower as the list grows. Hashes, by contrast, use hashing to provide significantly faster lookups for larger collections. As a rule of thumb:

Use an alist for small collections or when preserving insertion order is important.
Use a hash when you expect many lookups, larger data sets, or performance-sensitive operations.

Hashes do not guarantee any ordering of keys or values. When retrieving keys or values using hash-keys or hash-values, the order is indeterminate and should not be relied upon. If a specific ordering is required, convert the result to a list and sort it explicitly.

As with sets, procedures ending in ! mutate the original hash, while procedures without ! return newly allocated objects. Understanding this distinction is important when writing programs that rely on persistent data structures versus in-place modification.

Hash Procedures¶

hash¶

(hash key value ...)

Returns a newly allocated hash containing the key–value pairs supplied as alternating arguments. Keys must be hashable types; values may be any object. If no arguments are supplied, an empty hash is returned. It is an error if an odd number of arguments is supplied, or if any key is not a hashable type.

Parameters:

key – A hashable key.
value – The value to associate with the preceding key.

Returns:

A newly allocated hash.

Return type:

hash

Example:

--> (hash 'name "Alice" 'age 30 'city "Toronto")
#[name "Alice" age 30 city "Toronto"]
--> (hash)
#[]
--> (hash-get (hash 'x 42) 'x)
42

hash-copy¶

(hash-copy hash)

Returns a newly allocated copy of hash. The copy is shallow — the keys and values themselves are not copied, only the references to them. It is an error if hash is not a hash.

Parameters:: hash (hash) – The hash to copy.
Returns:: A newly allocated copy of hash.
Return type:: hash

Example:

--> (define h (hash 'a 1 'b 2))
--> (define h2 (hash-copy h))
--> (hash-add! h2 'c 3)
--> (hash-keys h2)
(a b c)
--> (hash-keys h)
(a b)

hash-clear!¶

(hash-clear! hash)

Removes all key–value pairs from hash, mutating it in place. Returns the same hash object, now empty. It is an error if hash is not a hash.

Parameters:: hash (hash) – The hash to clear.
Returns:: The mutated hash, now empty.
Return type:: hash

Example:

--> (define h (hash 'a 1 'b 2 'c 3))
--> (hash-clear! h)
#[]
--> h
#[]

hash-get¶

(hash-get hash key [default])

Returns the value associated with key in hash. If key is not found and a default value is supplied, default is returned. If key is not found and no default is supplied, an index error is signalled. It is an error if hash is not a hash, or if key is not a hashable type.

Parameters:

hash (hash) – The hash to look up.
key – The key to look up.
default – A value to return if key is not found. Optional.

Returns:

The value associated with key, or default if not found.

Example:

--> (define h (hash 'a 1 'b 2 'c 3))
--> (hash-get h 'b)
2
--> (hash-get h 'z)
Index error:  hash-get: object not found in hash
--> (hash-get h 'z 'not-found)
not-found

hash-add!¶

(hash-add! hash key value)

Adds key with associated value to hash, mutating it in place, and returns the mutated hash. If key already exists in hash, its value is updated. It is an error if hash is not a hash, or if key is not a hashable type.

Parameters:

hash (hash) – The hash to add to.
key – The key to add.
value – The value to associate with key.

Returns:

The mutated hash.

Return type:

hash

Example:

--> (define h (hash 'a 1))
--> (hash-add! h 'b 2)
--> h
#[a 1 b 2]
--> (hash-add! h 'a 99)
--> (hash-get h 'a)
99

hash-remove!¶

(hash-remove! hash key [sym])

Removes key and its associated value from hash, mutating it in place, and returns the mutated hash. Signals an index error if key is not found in hash. If an optional symbol is supplied as a third argument, the error is suppressed and the procedure returns silently instead. It is an error if hash is not a hash.

Parameters:

hash (hash) – The hash to remove from.
key – The key to remove.
sym (symbol) – An optional symbol. If provided, suppresses the error when key is not found.

Returns:

The mutated hash.

Return type:

hash

Example:

--> (define h (hash 'a 1 'b 2 'c 3))
--> (hash-remove! h 'b)
--> h
#[a 1 c 3]
--> (hash-remove! h 'z)
error: index-error
--> (hash-remove! h 'z 'ok)
--> h
#[a 1 c 3]

hash-keys¶

(hash-keys hash)

Returns a newly allocated list containing all keys in hash. The order of keys in the returned list is indeterminate, as hashes are unordered. It is an error if hash is not a hash.

Parameters:: hash (hash) – The hash to retrieve keys from.
Returns:: A list of all keys in hash.
Return type:: list

Example:

--> (define h (hash 'a 1 'b 2 'c 3))
--> (hash-keys h)
(a b c)
--> (hash-keys (hash))
()

hash-values¶

(hash-values hash)

Returns a newly allocated list containing all values in hash. The order of values in the returned list is indeterminate, as hashes are unordered. It is an error if hash is not a hash.

Parameters:: hash (hash) – The hash to retrieve values from.
Returns:: A list of all values in hash.
Return type:: list

Example:

--> (define h (hash 'a 1 'b 2 'c 3))
--> (hash-values h)
(1 2 3)
--> (hash-values (hash))
()

hash->alist¶

(hash->alist hash)

Returns a newly allocated association list (alist) containing all key–value pairs in hash. Each element of the returned list is a dotted pair of the form (key . value). The order of pairs in the returned list is indeterminate. It is an error if hash is not a hash.

Parameters:: hash (hash) – The hash to convert.
Returns:: An alist of (key . value) pairs.
Return type:: list

Example:

--> (define h (hash 'a 1 'b 2))
--> (hash->alist h)
((a . 1) (b . 2))

alist->hash¶

(alist->hash alist)

Returns a newly allocated hash constructed from the key–value pairs in alist. Each element of alist must be a dotted pair of the form (key . value); the car becomes the key and the cdr becomes the value. It is an error if alist is not a proper list, or if any element is not a dotted pair.

Parameters:: alist (list) – An association list of (key . value) dotted pairs.
Returns:: A newly allocated hash.
Return type:: hash

Example:

--> (define al '((a . 1) (b . 2) (c . 3)))
--> (define h (alist->hash al))
--> h
#[a 1 b 2 c 3]
--> (hash-get h 'b)
2

hash-keys-map¶

(hash-keys-map proc hash)

Applies proc to each key in hash and returns a list of the results. The order in which proc is applied is indeterminate, as hashes are unordered. proc must accept exactly one argument. It is an error if proc is not a procedure or hash is not a hash.

Parameters:

proc (procedure) – A procedure of one argument.
hash (hash) – The hash whose keys to map over.

Returns:

A list of results of applying proc to each key.

Return type:

list

Example:

--> (define h (hash 'a 1 'b 2 'c 3))
--> (hash-keys-map symbol->string h)
("a" "b" "c")

hash-keys-foreach¶

(hash-keys-foreach proc hash)

Applies proc to each key in hash for the purpose of side effects. The return values of proc are discarded. The order of applications is indeterminate. Returns an unspecified value. proc must accept exactly one argument. It is an error if proc is not a procedure or hash is not a hash.

Parameters:

proc (procedure) – A procedure of one argument.
hash (hash) – The hash whose keys to iterate over.

Returns:

Unspecified.

Example:

--> (define h (hash 'a 1 'b 2 'c 3))
--> (hash-keys-foreach display h)
abc

hash-values-map¶

(hash-values-map proc hash)

Applies proc to each value in hash and returns a list of the results. The order in which proc is applied is indeterminate, as hashes are unordered. proc must accept exactly one argument. It is an error if proc is not a procedure or hash is not a hash.

Parameters:

proc (procedure) – A procedure of one argument.
hash (hash) – The hash whose values to map over.

Returns:

A list of results of applying proc to each value.

Return type:

list

Example:

--> (define h (hash 'a 1 'b 2 'c 3))
--> (hash-values-map (lambda (x) (* x 10)) h)
(10 20 30)

hash-values-foreach¶

(hash-values-foreach proc hash)

Applies proc to each value in hash for the purpose of side effects. The return values of proc are discarded. The order of applications is indeterminate. Returns an unspecified value. proc must accept exactly one argument. It is an error if proc is not a procedure or hash is not a hash.

Parameters:

proc (procedure) – A procedure of one argument.
hash (hash) – The hash whose values to iterate over.

Returns:

Unspecified.

Example:

--> (define h (hash 'a 1 'b 2 'c 3))
--> (hash-values-foreach display h)
123

hash-items-map¶

(hash-items-map proc hash)

Applies proc to each key–value pair in hash and returns a list of the results. proc is called with two arguments for each entry: first the key, then the value. The order of applications is indeterminate. It is an error if proc is not a procedure or hash is not a hash.

Parameters:

proc (procedure) – A procedure of two arguments.
hash (hash) – The hash whose items to map over.

Returns:

A list of results of applying proc to each key–value pair.

Return type:

list

Example:

--> (define h (hash 'a 1 'b 2 'c 3))
--> (hash-items-map
...   (lambda (k v) (cons k (* v 10)))
...   h)
((a . 10) (b . 20) (c . 30))

hash-items-foreach¶

(hash-items-foreach proc hash)

Applies proc to each key–value pair in hash for the purpose of side effects. proc is called with two arguments for each entry: first the key, then the value. The return values of proc are discarded. The order of applications is indeterminate. Returns an unspecified value. It is an error if proc is not a procedure or hash is not a hash.

Parameters:

proc (procedure) – A procedure of two arguments.
hash (hash) – The hash whose items to iterate over.

Returns:

Unspecified.

Example:

--> (define h (hash 'a 1 'b 2 'c 3))
--> (hash-items-foreach
...   (lambda (k v)
...     (display k) (display ":") (display v) (display " "))
...   h)
a:1 b:2 c:3