LISP - Hash Table

Lisp - Hash Tables

A hash table is a fundamental data structure that stores a collection of key-value pairs. It provides highly efficient (amortized O(1) time) lookups, insertions, and deletions. It is the Lisp equivalent of a Dictionary in Python, a Map in Java/JavaScript, or a hash in Ruby/Perl.

Creating Hash Tables

You create a hash table using make-hash-table. Its most important argument is :test, which specifies how keys are compared.

(make-hash-table :test #'eql :size 100)

The choice of :test is crucial and determines the table’s behavior:

• #'eq: Compares keys by object identity (memory location). Fast, but only works if you use the exact same object as the key for storing and retrieving. Good for symbols.
• #'eql (the default): Compares by eq, but also considers two numbers of the same type and value, or two characters that are the same, as identical. This is a safe and general-purpose default.
• #'equal: Compares by structure. It will treat two different lists or strings with the same content as the same key. This is more flexible but slower.
• #'equalp: A case-insensitive and number-type-insensitive version of equal.

Common Error: Choosing the Wrong Test

A common bug is using the default #'eql test with string keys. Two strings with the same characters are not necessarily eql. For string keys, always use #'equal.

;; Incorrect: Might not work as expected
(defvar *ht-wrong* (make-hash-table :test #'eql))
(setf (gethash "mykey" *ht-wrong*) 1)
(gethash "mykey" *ht-wrong*) ; -> NIL, T (Might fail!)

;; Correct: Always use 'equal' for string keys
(defvar *ht-correct* (make-hash-table :test #'equal))
(setf (gethash "mykey" *ht-correct*) 1)
(gethash "mykey" *ht-correct*) ; -> 1, T (Always works)

Core Operations (CRUD)

Working with hash tables involves a few key functions.

(let ((user-data (make-hash-table :test #'equal)))
  ;; Create / Update: Use (setf gethash)
  (setf (gethash "user:123" user-data) '(:name "Alice" :email "alice@example.com"))
  (setf (gethash "user:456" user-data) '(:name "Bob" :plan "premium"))

  ;; Read: Use gethash
  ;; gethash returns two values: the value and a boolean indicating if the key was found.
  (multiple-value-bind (value found-p) (gethash "user:123" user-data)
    (if found-p
        (format t "Found user: ~a~%" value)
        (format t "User not found.~%")))
  ;; -> Found user: (NAME "Alice" :EMAIL "alice@example.com")

  ;; Delete: Use remhash
  (remhash "user:456" user-data)

  ;; Check for deleted key
  (gethash "user:456" user-data)
  ;; -> NIL, NIL
)

Iterating Over a Hash Table

You can process every key-value pair in a table using maphash or the loop macro.

Using maphash

maphash applies a function to each key-value pair. Note that hash tables are inherently unordered.

(let ((ht (make-hash-table)))
  (setf (gethash :a ht) 1)
  (setf (gethash :b ht) 2)
  (maphash #'(lambda (key value)
               (format t "Key: ~a, Value: ~a~%" key value))
           ht))
;; Output (order is not guaranteed):
;; Key: B, Value: 2
;; Key: A, Value: 1

Using the loop Macro

The loop macro often provides a more readable and flexible way to iterate.

(let ((ht (make-hash-table)))
  (setf (gethash :a ht) 1)
  (setf (gethash :b ht) 2)

  ;; Loop over keys and values
  (loop for key being the hash-key of ht
        using (hash-value value)
        do (format t "~a -> ~a~%" key value))

  ;; Collect all values into a list
  (let ((values (loop for value being the hash-value of ht collect value)))
    (print values));; -> (1 2) or (2 1)
)

Practical Application: A Simple Cache

Hash tables are perfect for memoization, a technique to cache the results of expensive function calls.

(defun make-memoized (fn)
  "Returns a memoized version of a single-argument function."
  (let ((cache (make-hash-table :test #'equal)))
    (lambda (arg)
      (multiple-value-bind (result found-p) (gethash arg cache)
        (if found-p
            result
            (setf (gethash arg cache) (funcall fn arg)))))))

(defun slow-computation (n)
  (format t "Computing for ~a...~%" n)
  (sleep 2) ; Simulate a slow operation
  (* n n))

(defvar memo-slow-computation (make-memoized #'slow-computation))

(funcall memo-slow-computation 5) ; -> Computes and prints 25
(funcall memo-slow-computation 5) ; -> Returns 25 instantly from cache