Hash Tables (SRFI-69)¶

Hash tables provide efficient key-value storage with average O(1) lookup. Import with (import (srfi 69)).

SRFI-69 tables iterate in no particular order. When iteration, folding, or conversion must follow first-insertion order, use the portable SRFI 250 (insertion-ordered hash tables) instead — (import (srfi 250)); see SRFI Support.

Performance characteristics¶

Operation	Average	Worst case
`hash-table-ref`	O(1)	O(n)
`hash-table-set!`	O(1)	O(n)
`hash-table-delete!`	O(1)	O(n)
`hash-table-size`	O(1)	O(1)
`hash-table->alist`	O(n)	O(n)
`hash-table-keys`	O(n)	O(n)

Kaappi uses open-addressing with linear probing. The table resizes automatically when the load factor exceeds a threshold.

When to use hash tables vs. alists:

Use hash tables when you have more than ~10 key-value pairs or when lookup performance matters — hash-table-ref is O(1) vs. assoc O(n)
Use alists for small, short-lived mappings or when you need the data as a list (e.g., JSON serialization)
Hash tables are mutable; alists are persistent (the original is unchanged when you cons a new pair onto the front)

Construction¶

`make-hash-table`¶

Syntax: (make-hash-table) | (make-hash-table equal-proc) | (make-hash-table equal-proc hash-proc)

Returns a newly allocated empty hash table. The optional equal-proc specifies the equality predicate used to compare keys (default is equal?). The optional hash-proc specifies the hash function used to compute bucket indices; it must be consistent with the equality predicate. When using eq? or eqv? as the equality predicate, provide a matching hash function for correct behavior.

kaappi> (define ht (make-hash-table))
kaappi> (hash-table? ht)
;=> #t
kaappi> (hash-table-size ht)
;=> 0
kaappi> (define ht2 (make-hash-table string=? string-hash))
kaappi> (hash-table-set! ht2 "key" 42)
kaappi> (hash-table-ref ht2 "key")
;=> 42

See also: hash-table?, alist->hash-table

`alist->hash-table`¶

Syntax: (alist->hash-table alist) | (alist->hash-table alist equal-proc) | (alist->hash-table alist equal-proc hash-proc)

Creates a new hash table and populates it from the association list alist. Each element of alist should be a pair (key . value). If alist contains duplicate keys, the first occurrence takes precedence. The optional equal-proc and hash-proc arguments work as in make-hash-table.

kaappi> (define ht (alist->hash-table '((a . 1) (b . 2) (c . 3))))
kaappi> (hash-table-ref ht 'a)
;=> 1
kaappi> (hash-table-ref ht 'c)
;=> 3
kaappi> (hash-table-size ht)
;=> 3
kaappi> (alist->hash-table '((x . 10) (x . 20)))
kaappi> (hash-table-ref (alist->hash-table '((x . 10) (x . 20))) 'x)
;=> 10

See also: hash-table->alist, make-hash-table

`hash-table-copy`¶

Syntax: (hash-table-copy ht)

Returns a shallow copy of hash table ht. The new table has the same equality and hash procedures, and contains the same key-value associations. Mutating the copy does not affect the original, and vice versa. Values are not recursively copied -- the copy shares the same value objects.

kaappi> (define ht (alist->hash-table '((a . 1) (b . 2))))
kaappi> (define ht2 (hash-table-copy ht))
kaappi> (hash-table-set! ht2 'a 99)
kaappi> (hash-table-ref ht 'a)
;=> 1
kaappi> (hash-table-ref ht2 'a)
;=> 99

See also: make-hash-table, hash-table->alist

Type Predicate¶

`hash-table?`¶

Syntax: (hash-table? obj)

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

kaappi> (hash-table? (make-hash-table))
;=> #t
kaappi> (hash-table? '((a . 1) (b . 2)))
;=> #f
kaappi> (hash-table? '#(1 2 3))
;=> #f
kaappi> (hash-table? "hello")
;=> #f

See also: make-hash-table, hash-table?

Lookup and Mutation¶

`hash-table-ref`¶

Syntax: (hash-table-ref ht key) | (hash-table-ref ht key failure-thunk)

Returns the value associated with key in hash table ht. O(1) average.

If key is not found and a failure-thunk is provided, the thunk is called with no arguments and its result is returned. If key is not found and no thunk is provided, an error is raised. Keys are compared using the hash table's equality predicate (equal? by default).

Errors: Raises an error if key is not found and no failure thunk is provided. The optional third argument is a thunk that is called on a miss — for a plain default value, use hash-table-ref/default.

kaappi> (define ht (alist->hash-table '((a . 1) (b . 2) (c . 3))))
kaappi> (hash-table-ref ht 'a)
;=> 1
kaappi> (hash-table-ref ht 'b)
;=> 2
kaappi> (hash-table-ref ht 'z (lambda () #f))
;=> #f
kaappi> (hash-table-ref/default ht 'z 0)
;=> 0

Common pattern — safe lookup with default:

(define (get-config key)
  (hash-table-ref/default config-ht key #f))

See also: hash-table-exists?, hash-table-set!

`hash-table-ref/default`¶

Syntax: (hash-table-ref/default ht key default)

Like hash-table-ref, but default is a plain value (not a thunk) returned when key is not present.

kaappi> (define ht (alist->hash-table '((a . 1) (b . 2))))
kaappi> (hash-table-ref/default ht 'a 0)
;=> 1
kaappi> (hash-table-ref/default ht 'z 0)
;=> 0

`hash-table-set!`¶

Syntax: (hash-table-set! ht key value)

Associates key with value in hash table ht. If key already exists, its value is replaced. O(1) average. Returns void. The table resizes automatically when needed.

kaappi> (define ht (make-hash-table))
kaappi> (hash-table-set! ht 'x 10)
kaappi> (hash-table-set! ht 'y 20)
kaappi> (hash-table-ref ht 'x)
;=> 10
kaappi> (hash-table-set! ht 'x 99)
kaappi> (hash-table-ref ht 'x)
;=> 99
kaappi> (hash-table-size ht)
;=> 2

`hash-table-delete!`¶

Syntax: (hash-table-delete! ht key)

Removes the association for key from hash table ht. If key is not present, the table is unchanged. Returns void.

kaappi> (define ht (alist->hash-table '((a . 1) (b . 2) (c . 3))))
kaappi> (hash-table-size ht)
;=> 3
kaappi> (hash-table-delete! ht 'b)
kaappi> (hash-table-size ht)
;=> 2
kaappi> (hash-table-exists? ht 'b)
;=> #f
kaappi> (hash-table-delete! ht 'z)
kaappi> (hash-table-size ht)
;=> 2

See also: hash-table-set!, hash-table-exists?

`hash-table-exists?`¶

Syntax: (hash-table-exists? ht key)

Returns #t if key is associated with a value in hash table ht, #f otherwise.

kaappi> (define ht (alist->hash-table '((a . 1) (b . 2))))
kaappi> (hash-table-exists? ht 'a)
;=> #t
kaappi> (hash-table-exists? ht 'z)
;=> #f
kaappi> (hash-table-delete! ht 'a)
kaappi> (hash-table-exists? ht 'a)
;=> #f

See also: hash-table-ref, hash-table-size

`hash-table-update!/default`¶

Syntax: (hash-table-update!/default ht key proc default)

Updates the value associated with key in ht by applying proc to the current value. If key does not exist, proc is applied to default and the result is stored. This is equivalent to:

(hash-table-set! ht key (proc (hash-table-ref ht key default)))

but may be implemented more efficiently.

kaappi> (define ht (make-hash-table))
kaappi> (hash-table-update!/default ht 'count (lambda (n) (+ n 1)) 0)
kaappi> (hash-table-ref ht 'count)
;=> 1
kaappi> (hash-table-update!/default ht 'count (lambda (n) (+ n 1)) 0)
kaappi> (hash-table-ref ht 'count)
;=> 2
kaappi> (define counts (make-hash-table))
kaappi> (for-each (lambda (word)
                    (hash-table-update!/default counts word
                                                (lambda (n) (+ n 1)) 0))
                  '(the cat sat on the mat))
kaappi> (hash-table-ref counts 'the)
;=> 2
kaappi> (hash-table-ref counts 'cat)
;=> 1

See also: hash-table-set!, hash-table-ref

Size and Inspection¶

`hash-table-size`¶

Syntax: (hash-table-size ht)

Returns the number of key-value associations in hash table ht.

kaappi> (hash-table-size (make-hash-table))
;=> 0
kaappi> (hash-table-size (alist->hash-table '((a . 1) (b . 2) (c . 3))))
;=> 3

See also: hash-table-keys, hash-table-exists?

`hash-table-keys`¶

Syntax: (hash-table-keys ht)

Returns a list of all keys in hash table ht. The order of keys is unspecified.

kaappi> (define ht (alist->hash-table '((a . 1) (b . 2) (c . 3))))
kaappi> (hash-table-keys ht)
;=> (b a c)
kaappi> (hash-table-keys (make-hash-table))
;=> ()

See also: hash-table-values, hash-table-size

`hash-table-values`¶

Syntax: (hash-table-values ht)

Returns a list of all values in hash table ht. The order of values is unspecified but corresponds to the order of hash-table-keys.

kaappi> (define ht (alist->hash-table '((a . 1) (b . 2) (c . 3))))
kaappi> (hash-table-values ht)
;=> (2 1 3)
kaappi> (hash-table-values (make-hash-table))
;=> ()

See also: hash-table-keys, hash-table->alist

Iteration and Conversion¶

`hash-table-walk`¶

Syntax: (hash-table-walk ht proc)

Calls (proc key value) for each key-value association in hash table ht. The order of iteration is unspecified. The return value is void. It is an error to mutate ht during the walk (add or remove keys).

kaappi> (define ht (alist->hash-table '((a . 1) (b . 2) (c . 3))))
kaappi> (define sum 0)
kaappi> (hash-table-walk ht (lambda (k v) (set! sum (+ sum v))))
kaappi> sum
;=> 6
kaappi> (hash-table-walk ht
         (lambda (k v) (display k) (display ": ") (display v) (newline)))
c: 3
a: 1
b: 2

Note

The output order above is illustrative. Hash table iteration order is not guaranteed and may differ between runs.

`hash-table->alist`¶

Syntax: (hash-table->alist ht)

Returns an association list containing the key-value pairs of hash table ht. Each element is a pair (key . value). The order of elements is unspecified.

kaappi> (define ht (make-hash-table))
kaappi> (hash-table-set! ht 'x 10)
kaappi> (hash-table-set! ht 'y 20)
kaappi> (hash-table->alist ht)
;=> ((y . 20) (x . 10))
kaappi> (hash-table->alist (make-hash-table))
;=> ()

hash-table-equivalence-function¶

(hash-table-equivalence-function ht) → procedure

Returns the equivalence function used by the hash table. Kaappi hash tables always use equal?.

kaappi> (hash-table-equivalence-function (make-hash-table))
;=> #<builtin equal?>

hash-table-hash-function¶

(hash-table-hash-function ht) → procedure

Returns the hash function used by the hash table.

kaappi> (hash-table-hash-function (make-hash-table))
;=> #<builtin hash>

Hash Tables (SRFI-69)¶

Performance characteristics¶

Construction¶

make-hash-table¶

alist->hash-table¶

hash-table-copy¶

Type Predicate¶

hash-table?¶

Lookup and Mutation¶

hash-table-ref¶

hash-table-ref/default¶

hash-table-set!¶

hash-table-delete!¶

hash-table-exists?¶

hash-table-update!/default¶