Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 38 ยท Lists and Data Structures

Hash Tables

Store and look up data by key in Common Lisp with hash tables: make-hash-table, gethash and its second value, remhash, maphash, loop over keys, and choosing eql or equal.

When you have many keys and need fast lookup, the hash table is the tool. It maps keys to values with average constant-time access, whatever the size. This lesson shows how to create tables, read and write entries (including the surprising second return value of gethash), iterate, count words, and avoid the most common trap: choosing the wrong key test.

Creating a table

LISP
(defparameter *h* (make-hash-table))                       ; keys compared with EQL
(defparameter *names* (make-hash-table :test 'equal))      ; strings and lists work
(defparameter *small* (make-hash-table :test 'equalp :size 100))

:test can be eq, eql (default), equal or equalp. Write it as a quoted symbol ('equal) or a function (#'equal); both work. The :size is only a hint.

Reading and writing

LISP
(setf (gethash 'apple *h*) 3)
(setf (gethash 'pear *h*) 5)
(gethash 'apple *h*)       ; => 3, T
(gethash 'grape *h*)       ; => NIL, NIL
(gethash 'grape *h* 0)     ; => 0, NIL   third argument is a default

gethash returns two values: the value (or default) and a flag telling whether the key was present. The flag matters when NIL is a legitimate stored value, because the first value alone cannot distinguish "missing" from "stored NIL":

LISP
(setf (gethash 'flag *h*) nil)
(gethash 'flag *h*)        ; => NIL, T    present, value NIL
(gethash 'nothing *h*)     ; => NIL, NIL  absent

Capture both with multiple-value-bind:

LISP
(multiple-value-bind (value present-p) (gethash 'flag *h*)
  (if present-p
      (format t "found ~a~%" value)
      (format t "missing~%")))

Other operations:

LISP
(hash-table-count *h*)     ; => number of entries
(remhash 'apple *h*)       ; => T if it was removed
(clrhash *h*)              ; remove everything
(incf (gethash 'pear *h* 0))   ; update in place: gethash is a place, 0 = default

The last idiom, (incf (gethash key table 0)), is how you count things.

Iterating

LISP
(maphash (lambda (key value)
           (format t "~a => ~a~%" key value))
         *h*)

(loop for k being the hash-keys of *h* collect k)
(loop for v being the hash-values of *h* sum v)
(loop for k being the hash-keys of *h* using (hash-value v)
      collect (list k v))

Order is not specified. In practice SBCL iterates in insertion order for tables where nothing was removed, but you must not rely on that. If you need sorted output, collect the keys and sort them.

You may add or change entries while iterating with maphash, but you may only remove or change the current entry. Adding others during iteration is undefined.

Counting words

The classic example:

LISP
(defun word-frequencies (words)
  (let ((table (make-hash-table :test 'equal)))
    (dolist (w words table)
      (incf (gethash w table 0)))))

(let ((freq (word-frequencies '("a" "b" "a" "c" "a" "b"))))
  (sort (loop for k being the hash-keys of freq using (hash-value v)
              collect (cons k v))
        #'> :key #'cdr))
;; => (("a" . 3) ("b" . 2) ("c" . 1))

Note :test 'equal: strings need it, as the next section explains.

Choosing the test

The test decides when two keys count as the same key.

Test Good for Notes
eq Symbols, objects by identity Fastest; unreliable for numbers and characters
eql (default) Symbols, numbers, characters Strings are different keys unless the same object
equal Strings, lists, conses Case-sensitive
equalp Strings ignoring case, numbers by value Slowest, loosest

The most common mistake is forgetting :test 'equal when keys are strings:

LISP
(let ((h (make-hash-table)))               ; eql table
  (setf (gethash "one" h) 1)
  (gethash "one" h))                       ; => NIL, NIL   a different string object!

(let ((h (make-hash-table :test 'equal)))
  (setf (gethash "one" h) 1)
  (gethash "one" h))                       ; => 1, T

If lookups mysteriously fail, check the test first.

Keys that are lists

With :test 'equal you can use lists as compound keys, such as coordinates:

LISP
(let ((grid (make-hash-table :test 'equal)))
  (setf (gethash '(2 3) grid) :wall)
  (gethash (list 2 3) grid))     ; => :WALL, T

Do not mutate a key after storing it; the table would no longer find it.

A stand-in for gethash

JavaScript's Map is close to an eql hash table for numbers and symbols, but compares objects by identity, which makes the string-key trap visible if you use arrays as keys. This stand-in (not Lisp) shows the two-value gethash, the default argument, counting, and the identity problem solved by an equal-style key.

JS Stand-in: gethash, counting and key equality

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Hash tables in practice

  • Printing: a hash table prints as #<HASH-TABLE :TEST EQL :COUNT 2 {...}>, not its contents. Write a small function that dumps the pairs, or use a library like alexandria (hash-table-alist).
  • Copying: there is no standard copy-hash-table; use alexandria:copy-hash-table or loop and re-insert.
  • Thread safety: SBCL tables are not synchronized unless you pass :synchronized t.
  • Weakness: SBCL supports :weakness :key for caches that should not keep keys alive.
  • Sets: use a table with t as every value and gethash as the membership test.
LISP
(defparameter *seen* (make-hash-table :test 'equal))
(defun first-visit-p (item)
  (unless (gethash item *seen*)
    (setf (gethash item *seen*) t)))

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does (gethash 'x table) return?

    The second value tells you whether the key exists, which matters when NIL is a valid stored value.
  2. 2. You store (setf (gethash "one" h) 1) in a default table and then (gethash "one" h) returns NIL. Why?

    Use (make-hash-table :test 'equal) for string keys.
  3. 3. Which idiom counts occurrences?

    gethash is a place; the default 0 makes missing keys start at zero.
  4. 4. In what order does maphash visit entries?

    The standard does not specify order; sort the keys if you need a particular order.

Summary

  • make-hash-table with :test chooses key equality: eql by default, equal for strings and lists.
  • (gethash key table default) returns the value and a presence flag; (setf gethash) writes; remhash, clrhash, hash-table-count manage entries.
  • Count with (incf (gethash k table 0)).
  • Iterate with maphash or loop ... being the hash-keys; order is unspecified.
  • Wrong :test is the usual cause of failed lookups.

Next: Functions and Parameters