Searching key in HashTable

Lisp - Searching a Hash Table

Hash tables are a fundamental data structure in Common Lisp, providing an efficient way to store and retrieve data using key-value pairs. Due to their typical average-case O(1) time complexity for lookups, they are ideal for caching, memoization, and managing dictionaries of data. This chapter explores how to search for values in a Lisp hash table.

The gethash Function

The primary function for searching a hash table is gethash.

(gethash key hash-table [default-value])

gethash returns two values:

• value: The value associated with the key. If the key is not found, it returns default-value (which is NIL if not provided).
• found-p: A boolean (T or NIL) indicating whether the key was actually present in the hash table.

Idiomatic Searching with multiple-value-bind

Because gethash returns NIL for a missing key, you can’t distinguish between a key that is absent and a key whose value is actually NIL. The idiomatic and correct way to handle this is to use multiple-value-bind to capture both return values.

;; General pattern for safe hash table lookups
(multiple-value-bind (value found-p) (gethash key my-hash-table)
  (if found-p
      (format t "Key found! Value: ~a~%" value)
      (format t "Key not found.~%")))

Example 1: Hash Table with Symbol Keys

By default, make-hash-table creates a table that compares keys with eql, which is suitable for numbers, characters, and symbols.

main.lisp

;; Create a hash table (default test is 'eql')
(let ((my-table (make-hash-table)))
  ;; Add some key-value pairs
  (setf (gethash 'id-001 my-table) "Alice")
  (setf (gethash 'id-002 my-table) "Bob")

  ;; --- Search for a key that exists ---
  (multiple-value-bind (value found-p) (gethash 'id-001 my-table)
    (if found-p
        (format t "Found key 'id-001. User: ~a~%" value)
        (format t "Key 'id-001 not found.~%")))

  ;; --- Search for a key that does NOT exist ---
  (multiple-value-bind (value found-p) (gethash 'id-003 my-table)
    (if found-p
        (format t "Found key 'id-003. User: ~a~%" value)
        (format t "Key 'id-003 not found.~%"))))

Output

Found key 'id-001. User: Alice
Key 'id-003 not found.

Example 2: Hash Table with String Keys

When using string keys, you must create the hash table with :test #'equal, because two strings with the same content may not be eql.

main.lisp

;; Create a hash table suitable for string keys
(let ((fruit-prices (make-hash-table :test #'equal)))
  ;; Add some key-value pairs
  (setf (gethash "apple" fruit-prices) 1.50)
  (setf (gethash "banana" fruit-prices) 0.75)

  ;; --- Search for a key that exists ---
  (multiple-value-bind (price found-p) (gethash "apple" fruit-prices)
    (if found-p
        (format t "Price of an apple: $~,2f~%" price)
        (format t "Apple not found in price list.~%")))

  ;; --- Search for a key that does NOT exist ---
  (multiple-value-bind (price found-p) (gethash "mango" fruit-prices)
    (if found-p
        (format t "Price of a mango: $~,2f~%" price)
        (format t "Mango not found in price list.~%"))))

Output

Price of an apple: $1.50
Mango not found in price list.

Modifying and Clearing Hash Tables

Beyond searching, you will often need to modify hash tables:

• Adding/Updating: (setf (gethash key table) value) is used for both adding a new pair and updating the value of an existing key.
• Removing: (remhash key table) removes the key-value pair from the table. It returns T if the key was found and removed, otherwise NIL.
• Clearing: (clrhash table) removes all entries from the hash table, leaving it empty.