LISP - Representing Set with HashTable

Lisp - Implementing a Set with Hash Tables

A set is a fundamental data structure representing a collection of unique items. While Common Lisp has built-in functions for set operations on lists (union, intersection, etc.), implementing a set using a hash table is a highly efficient approach, especially for large collections.

This chapter demonstrates how to build a basic set data structure from scratch using a hash table, and then introduces modern library-based alternatives.

Why Use a Hash Table for a Set?

Hash tables provide an average time complexity of O(1) (constant time) for adding, removing, and checking for the existence of an element. This is a significant performance advantage over using lists, where these operations take O(n) time.

Building a Set from Scratch

We will define a small collection of functions to manage our hash-table-based set. In this implementation, we will store items as keys in the hash table. The associated value doesn’t matter, so we’ll just use t.

Core Functions

;; set-implementation.lisp

(defun make-set (&key (test 'eql))
  "Creates a new, empty set, implemented as a hash table.
  The :test argument specifies the key comparison function (e.g., 'eq, 'eql, 'equal)."
  (make-hash-table :test test))

(defun set-add (set item)
  "Adds an item to the set. Has no effect if the item is already present."
  (setf (gethash item set) t))

(defun set-remove (set item)
  "Removes an item from the set. Returns t if the item was present, nil otherwise."
  (remhash item set))

(defun set-contains-p (set item)
  "Returns t if the item is in the set, nil otherwise."
  ;; gethash returns two values: the value and a boolean indicating presence.
  ;; We check the second value for an unambiguous result.
  (nth-value 1 (gethash item set)))

(defun set-size (set)
  "Returns the number of items in the set."
  (hash-table-count set))

(defun set-to-list (set)
  "Returns a list of all items in the set."
  (loop for key being the hash-keys of set collect key))

Example Usage

Let’s see our set implementation in action.

;; Assuming the functions above are loaded

;; Create a set. The default test is 'eql'.
(defvar *my-set* (make-set))

;; Add some elements
(set-add *my-set* 10)
(set-add *my-set* 20)
(set-add *my-set* "hello")

;; Adding a duplicate has no effect
(set-add *my-set* 10)

(format t "My Set: ~a~%" (sort (set-to-list *my-set*) #'< :key #'princ-to-string))
(format t "Size of My Set: ~a~%" (set-size *my-set*))

;; Check for element presence
(format t "Contains 20? ~a~%" (set-contains-p *my-set* 20))
(format t "Contains 30? ~a~%" (set-contains-p *my-set* 30))

;; Remove an element
(set-remove *my-set* 10)
(format t "My Set after removing 10: ~a~%" (sort (set-to-list *my-set*) #'< :key #'princ-to-string))

Output

Note: The order of elements from a hash table is not guaranteed, so we sort the list for predictable output.

My Set: (10 20 "hello")
Size of My Set: 3
Contains 20? T
Contains 30? NIL
My Set after removing 10: (20 "hello")

The Modern Approach: Using Libraries

While building your own data structures is a great learning exercise, in real-world projects, it’s best to use battle-tested libraries. The de facto package manager for Common Lisp is Quicklisp. With Quicklisp, you can easily load powerful libraries that provide efficient data structures.

Introducing lparallel’s queue as a Set

A common and powerful utility library is lparallel, which, despite its name, contains an excellent, thread-safe queue implementation that can be used to model sets. Another good choice is the dedicated cl-containers library.

Best Practice: Don’t Reinvent the Wheel

Here’s how you might approach this in a modern Lisp project:

1. Install Quicklisp: Follow the instructions at quicklisp.org to set it up.
2. Load a Library: In your Lisp REPL, run (ql:quickload :cl-containers).
3. Use the Library’s API: Leverage the high-quality, pre-built data structures.

Development Workflow

Learning to build data structures like a hash-table-based set is crucial for understanding the underlying principles of computer science and performance. However, for production code, you should:

• 1. Understand the concept: Know why a hash table is good for a set.
• 2. Build a prototype: Implement it yourself to solidify your knowledge (as we did above).
• 3. Use a library: In your final application, switch to a robust, well-maintained library for better performance, more features (like thread safety), and reliability.