Using Custom Equality Check

Lisp - Custom Equality in Hash Tables

A hash table is a fundamental data structure for mapping keys to values, offering fast lookups. In Common Lisp, the power of hash tables is greatly enhanced by the ability to specify a custom test for key equality. This allows you to define precisely what it means for two keys to be “the same”.

The :test Argument in make-hash-table

When you create a hash table, you can provide a :test argument to specify which equality function to use for comparing keys. Understanding the common options is crucial.

• #'eq: Tests for object identity. Two keys are eq only if they are the exact same object in memory. This is the fastest test but rarely used for string or list keys.
• #'eql: The default test. It behaves like eq but also considers two numbers of the same type and value, or two characters that are the same, to be equal.
• #'equal: Tests for structural equality. It recursively compares lists and vectors, and compares strings character by character. This is a common choice for string or list keys.
• #'equalp: A more lenient version of equal. It ignores case differences in strings/characters and considers numbers of different types (e.g., 2 and 2.0) to be equal.

The Problem with Default Behavior for String Keys

Let’s see what happens when we use the default :test (#'eql) with string keys. In Lisp, each literal string "apple" in your code can create a new, distinct object in memory.

Example: Default :test (eql)

;; Create a hash table with the default test
(let ((my-hash-table (make-hash-table)))

  ;; The key "apple" here is likely a different object from the one below
  (setf (gethash "apple" my-hash-table) 1)

  ;; This `gethash` call uses yet another "apple" string object for lookup.
  ;; Since it's not `eql` to the key used in `setf`, the lookup fails.
  (format t "Value for \"apple\": ~a~%" (gethash "apple" my-hash-table)))

Output

Value for "apple": NIL

The lookup fails because the key used to store the value and the key used to retrieve it are two different string objects, even though their contents are the same. They are not eql.

Using equal and equalp for Strings

To fix this, we must tell the hash table to compare the contents of the strings, not their memory locations.

Example: Using :test #'equal (Case-Sensitive)

(let ((my-hash-table (make-hash-table :test #'equal)))
  (setf (gethash "apple" my-hash-table) 1)
  (setf (gethash "Apple" my-hash-table) 2)

  (format t "Value for \"apple\": ~a~%" (gethash "apple" my-hash-table))
  (format t "Value for \"Apple\": ~a~%" (gethash "Apple" my-hash-table)))

Output

Value for "apple": 1
Value for "Apple": 2

With #'equal, the comparison is case-sensitive, so "apple" and "Apple" are treated as distinct keys.

Example: Using :test #'equalp (Case-Insensitive)

(let ((my-hash-table (make-hash-table :test #'equalp)))
  ;; First, we set the value for the key "apple"
  (setf (gethash "apple" my-hash-table) 1)

  ;; Because of `equalp`, "Apple" is considered the SAME key.
  ;; This overwrites the previous value.
  (setf (gethash "Apple" my-hash-table) 2)

  ;; Looking up "apple" now retrieves the most recently set value for that key.
  (format t "Value for \"apple\": ~a~%" (gethash "apple" my-hash-table))
  (format t "Value for \"Apple\": ~a~%" (gethash "Apple" my-hash-table)))

Output

Value for "apple": 2
Value for "Apple": 2

Best Practices and Advanced Usage

• Choose the right test: For string keys, #'equal is the most common and safest choice. Use #'equalp only if you explicitly need case-insensitive behavior. Use #'eq for keys that are symbols or guaranteed to be unique objects (e.g., objects representing system resources).
• Performance: The tests have different performance characteristics: eq is the fastest, followed by eql, equal, and finally equalp, which is the most expensive.
• Custom Functions: You can provide your own two-argument comparison function to :test. This is powerful for using complex objects as keys, where equality might be based on a specific field, like a user ID.