Learn

Lists are O(n) for lookup. Hash tables are O(1) — Common Lisp's built-in dict type.

Creating

(defparameter *ages* (make-hash-table :test 'equal))

The :test is the equality predicate:

• 'eq — pointer identity (fastest)
• 'eql — eq + same-value numbers/chars (default)
• 'equal — recursive structural equality (use this for strings, lists)
• 'equalp — case-insensitive strings, etc.

For strings, ALWAYS use 'equal. Otherwise lookups by string fail mysteriously.

Operations

(setf (gethash "alice" *ages*) 30)
(setf (gethash "bob" *ages*) 25)

(gethash "alice" *ages*)            ; 30, t
(gethash "missing" *ages*)          ; nil, nil
(gethash "missing" *ages* 0)        ; 0, nil — default

(remhash "alice" *ages*)            ; remove
(hash-table-count *ages*)            ; size

gethash returns TWO values: the value, and a boolean whether the key was present. Use multiple-value-bind:

(multiple-value-bind (val present-p) (gethash key table)
    (if present-p val :default))

Iterating

(maphash (lambda (k v)
             (format t "~a -> ~a~%" k v))
         *ages*)

;; Or with loop:
(loop for k being the hash-keys of *ages* using (hash-value v)
      do (format t "~a -> ~a~%" k v))

Use cases

Word frequency:

(defun count-words (text)
    (let ((counts (make-hash-table :test 'equal)))
        (dolist (word (split-into-words text))
            (incf (gethash word counts 0)))
        counts))

incf increments in place. With gethash word counts 0 returning 0 for missing keys, the math works on first occurrence.

Memoization:

(let ((cache (make-hash-table)))
    (defun memoized-fib (n)
        (or (gethash n cache)
            (setf (gethash n cache)
                  (if (< n 2) n
                      (+ (memoized-fib (- n 1))
                         (memoized-fib (- n 2))))))))

Performance

• O(1) lookup, insert, delete on average
• O(n) worst case (rare with good hashing)
• Small overhead — use lists for tiny collections
• For ordered maps: use cl-containers library

Hash tables are why you don't usually need explicit dicts via lists in modern Common Lisp.