LISP - List as Set vs HashTable as Set

Lisp - Implementing Sets: Lists vs. Hash Tables

A set is a collection of unique items. In Common Lisp, there are two primary ways to implement sets, each with distinct performance characteristics and use cases: using a simple list or using a hash table.

Approach 1: Set as a List

The simplest way to represent a set is with a list where you manually enforce uniqueness. Common Lisp provides helper functions that make this easy and idiomatic.

Idiomatic List-Based Set Operations

;; Create a set as a list.
(defvar *my-list-set* '(1 2 3 4 5))

;; Check for membership with MEMBER.
;; MEMBER returns the rest of the list from the found item (a 'true' value),
;; or NIL (false) if not found.
(print (member 3 *my-list-set*))   ; ==> (3 4 5)
(print (member 6 *my-list-set*))   ; ==> NIL

;; Add an element with ADJOIN.
;; ADJOIN only adds the element if it's not already present.
;; It's non-destructive and returns a new list.
(let ((new-set (adjoin 6 *my-list-set*)))
  (print new-set))                ; ==> (6 1 2 3 4 5)

;; Trying to add an existing element does nothing.
(let ((same-set (adjoin 3 *my-list-set*)))
  (print same-set))               ; ==> (1 2 3 4 5)

;; Remove an element with REMOVE.
(let ((removed-set (remove 3 *my-list-set*)))
  (print removed-set))             ; ==> (1 2 4 5)

Output

(3 4 5)
NIL
(6 1 2 3 4 5)
(1 2 3 4 5)
(1 2 4 5)

Characteristics of List-Based Sets

• Simple to Implement: Easy to understand and uses standard list functions.
• Preserves Insertion Order: Functions like adjoin add to the front, creating a de facto reverse insertion order. This order is predictable.
• Inefficient Membership Check (O(n)): To check if an element exists (member), Lisp may have to scan the entire list, making it slow for large sets.
• Inefficient Addition (O(n)): Adding an element (adjoin) requires a membership check first, resulting in O(n) complexity.
• Good for Small Sets: Ideal for small collections where performance is not critical and simplicity is valued.

Approach 2: Set as a Hash Table

For high-performance sets, a hash table is the superior choice. We use the set’s elements as keys in the hash table. The values are irrelevant and are typically set to t.

Hash Table-Based Set Implementation

;; Create an empty hash set (we must specify a 'test' for key comparison).
(defvar *my-hash-set* (make-hash-table :test 'equal))

;; Helper function to add multiple items.
(defun add-to-set (set &rest items)
  (dolist (item items) (setf (gethash item set) t)))

;; Add elements to the hash set.
(add-to-set *my-hash-set* 1 2 3 4 5)

;; Check for membership with GETHASH.
;; GETHASH returns the value and a second boolean value indicating presence.
(multiple-value-bind (value present-p) (gethash 3 *my-hash-set*)
  (format t "Value for 3: ~a, Present: ~a~%" value present-p))

(multiple-value-bind (value present-p) (gethash 6 *my-hash-set*)
  (format t "Value for 6: ~a, Present: ~a~%" value present-p))

;; Remove an element with REMHASH.
(remhash 1 *my-hash-set*)
(format t "Size of set after removing 1: ~a~%" (hash-table-count *my-hash-set*))

Output

Value for 3: T, Present: T
Value for 6: NIL, Present: NIL
Size of set after removing 1: 4

Characteristics of Hash Table-Based Sets

• Efficient Membership Check (Average O(1)): Checking for an element is extremely fast, with constant-time average complexity.
• Efficient Addition/Deletion (Average O(1)): Adding and removing elements are also constant-time operations on average.
• No Order Preservation: Hash tables do not guarantee any specific order for their keys.
• Space Overhead: Hash tables have a higher memory footprint than lists, especially for very small sets.
• Requires Good Hashing: Performance depends on the hash function. For custom objects, you may need to define a custom hash function.

Conclusion: Which to Choose?

Feature	Set as List	Set as Hash Table
Membership Check	Slow (O(n))	Fast (Average O(1))
Addition/Deletion	Slow (O(n))	Fast (Average O(1))
Order Preserving	Yes	No
Best For	Small, non-performance-critical sets	Large or performance-critical sets
Implementation	Very simple, uses built-in list functions	Slightly more complex, requires hash table setup