LISP - 使用哈希表表示集合

Lisp - 使用哈希表实现集合

**集合（Set）是一种基本的数据结构，用于表示唯一元素的集合。虽然 Common Lisp 为列表（List）提供了内置的集合操作函数（如 union、intersection 等），但使用哈希表（Hash Table）**实现集合是一种高效的方法，尤其适用于大型集合。

本章将演示如何从头开始使用哈希表构建一个基本的集合数据结构，然后介绍基于现代库的替代方案。

为什么用哈希表实现集合？

哈希表为添加、删除和检查元素是否存在提供了平均时间复杂度为 O(1)（常数时间）的性能。这相对于使用列表而言是一个显著的性能优势，因为在列表中这些操作需要 O(n) 的时间。

从头构建集合

我们将定义一小部分函数来管理基于哈希表的集合。在这个实现中，我们将把元素作为哈希表中的键（key）来存储。关联的值（value）无关紧要，所以我们只需使用 t。

核心函数

;; set-implementation.lisp

(defun make-set (&key (test 'eql))
  "创建一个新的空集合，以哈希表实现。
  :test 参数指定键的比较函数（例如，'eq, 'eql, 'equal）。"
  (make-hash-table :test test))

(defun set-add (set item)
  "向集合中添加一个元素。如果元素已存在，则不产生任何效果。"
  (setf (gethash item set) t))

(defun set-remove (set item)
  "从集合中移除一个元素。如果元素存在则返回 t，否则返回 nil。"
  (remhash item set))

(defun set-contains-p (set item)
  "如果元素在集合中则返回 t，否则返回 nil。
  ;; gethash 返回两个值：值本身以及一个表示元素是否存在的布尔值。
  ;; 我们检查第二个值以获得明确的结果。"
  (nth-value 1 (gethash item set)))

(defun set-size (set)
  "返回集合中元素的数量。"
  (hash-table-count set))

(defun set-to-list (set)
  "返回集合中所有元素的列表。"
  (loop for key being the hash-keys of set collect key))

使用示例

让我们看看我们的集合实现是如何运作的。

;; 假设上述函数已加载

;; 创建一个集合。默认的比较函数是 'eql'。
(defvar *my-set* (make-set))

;; 添加一些元素
(set-add *my-set* 10)
(set-add *my-set* 20)
(set-add *my-set* "hello")

;; 添加重复元素没有效果
(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*))

;; 检查元素是否存在
(format t "Contains 20? ~a~%" (set-contains-p *my-set* 20))
(format t "Contains 30? ~a~%" (set-contains-p *my-set* 30))

;; 移除一个元素
(set-remove *my-set* 10)
(format t "My Set after removing 10: ~a~%" (sort (set-to-list *my-set*) #'< :key #'princ-to-string))

输出

注意：从哈希表中获取元素的顺序不保证一致，因此我们对列表进行排序以获得可预测的输出。

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

现代方法：使用库

虽然自己构建数据结构是一个很好的学习练习，但在实际项目中，最好使用经过实战检验的库。Common Lisp 事实上的包管理器是 Quicklisp。通过 Quicklisp，您可以轻松加载提供高效数据结构的强大库。

介绍 lparallel 的 queue 作为集合的用途

一个常用且强大的实用程序库是 lparallel，尽管其名称如此，但它包含了一个优秀的、线程安全的队列（queue）实现，可以用来模拟集合。另一个不错的选择是专用的 cl-containers 库。

最佳实践：不要重复造轮子

以下是您在现代 Lisp 项目中处理此问题的方法：

1. 安装 Quicklisp：按照 quicklisp.org 上的说明进行设置。
2. 加载库：在您的 Lisp REPL 中，运行 (ql:quickload :cl-containers)。
3. 使用库的 API：利用高质量的预构建数据结构。

开发工作流程

学习构建像基于哈希表的集合这样的数据结构对于理解计算机科学和性能的底层原理至关重要。然而，对于生产代码，您应该：

• 1. 理解概念：知道为什么哈希表适合实现集合。
• 2. 构建原型：自己实现它以巩固您的知识（如上所示）。
• 3. 使用库：在您的最终应用程序中，切换到健壮、维护良好的库，以获得更好的性能、更多功能（如线程安全）和可靠性。