Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 38 ยท Lists and Recursion

Association Lists and Hash Tables

Store key-value data in Racket and Scheme with association lists and hash tables: assoc, hash, make-hash, hash-ref, hash-set, counting words and choosing between them.

Programs constantly need to look something up by name: a score for each player, a price for each product, a count for each word. Racket offers two standard answers: association lists (lists of pairs, the classic Lisp approach) and hash tables (the fast, modern choice). This lesson shows both and how to pick.

The Run examples use the stand-in's assoc and its mutable hash table (make-hash). Racket's immutable hash and functional update hash-set are shown read-only.

Association lists

An association list (alist) is a list of pairs. Each pair is (key . value) or (key value):

RACKET
(define ages '((ada 36) (alan 41) (grace 85)))
(assoc 'alan ages)      ; '(alan 41)   the whole entry, or #f if missing
(cadr (assoc 'alan ages)) ; 41
(assoc 'bob ages)       ; #f

assoc walks the list comparing keys with equal?, so it works for strings, numbers and symbols. assq uses eq? (symbols only) and assv uses eqv?.

The key is not copied or ordered: just a list. To "update" an alist, you build a new one, typically by consing a new entry on the front (which shadows older entries with the same key):

RACKET
(define ages2 (cons '(bob 29) ages))
(assoc 'bob ages2)      ; '(bob 29)
Association lists

Alists are great for small tables, for building results during a recursive algorithm, and for code that is readable as data. Lookup is linear time, so they slow down with hundreds of entries.

Hash tables

A hash table gives near-constant lookup time regardless of size. Racket has two families:

Kind Create Update Notes
Mutable (make-hash) (hash-set! h k v) Changes in place
Immutable (hash 'a 1 'b 2) (hash-set h k v) returns a new table Safe to share, functional style

Both use equal? for keys by default. The core operations:

RACKET
(define h (make-hash))
(hash-set! h 'apples 3)
(hash-set! h 'pears 5)
(hash-ref h 'apples)           ; 3
(hash-ref h 'plums 0)          ; 0    default when missing
(hash-ref h 'plums #f)         ; #f
(hash-has-key? h 'pears)       ; #t
(hash-count h)                 ; 2
(hash-remove! h 'pears)

(hash-ref h key) with no default raises an error when the key is missing, so give a default value (or a function that produces one) whenever the key may be absent.

A mutable hash table

The last line is deliberately an error: asking for a missing key with no default fails, in Racket as in the stand-in.

The immutable style

The immutable hash fits Racket's functional spirit. hash-set does not change its argument; it returns a new table that shares most of its structure with the old one:

RACKET
(define h1 (hash 'a 1 'b 2))
(define h2 (hash-set h1 'c 3))
(hash-ref h1 'c #f)    ; #f      the original is untouched
(hash-ref h2 'c #f)    ; 3
(hash-update h1 'a add1)   ; a new table with a = 2

Use the immutable version when you pass tables between functions or want to keep old versions around; use the mutable one for a table that a single function fills while it loops.

Iterating

Racket's for loops iterate directly over tables:

RACKET
(for ([(k v) (in-hash h)])
  (printf "~a -> ~a\n" k v))
(hash-keys h)      ; a list of keys, in no guaranteed order
(hash-values h)

Hash tables do not promise an order, so sort the keys when you need stable output, as the example below does.

Example: counting words

Counting how often each item appears is the classic hash table job:

Word counter

The key step is (hash-ref counts w 0): use 0 when the word has not been seen, then add one and store it back.

Which should I use?

Situation Choose
Few entries, readable as data, shows in the REPL association list
Many entries, fast lookup needed hash table
Keep old versions, pass between functions immutable hash
Fill in a loop, then read mutable make-hash
Keys are fixed field names with fixed meaning a struct (next lesson)

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does (assoc 'bob '((ada 1) (bob 2))) return?

    assoc returns the whole matching entry (or #f), so you use cadr to get the value.
  2. 2. What happens with (hash-ref h 'missing) when the key is absent and there is no default?

    Without a default, a missing key is an error; pass a default value or procedure.
  3. 3. Which operation changes an immutable hash in place?

    Immutable hashes never change. hash-set builds and returns a new one.
  4. 4. Why is assoc slow for very large tables?

    An association list is a plain list, so lookup is linear in its length.

Summary

  • An association list is a list of (key value) entries searched with assoc/assq; simple, readable, linear time.
  • Hash tables give fast lookup: make-hash with hash-set!, or immutable hash with hash-set.
  • Give hash-ref a default value when the key may be missing.
  • Hash tables are unordered; sort keys for deterministic output.
  • Counting and grouping are the classic hash table jobs.

Next: Vectors and Structs