LISP - 列表作为集合 vs 哈希表作为集合

Lisp - 集合实现：列表 vs. 哈希表

集合是独一无二的元素的集合。在 Common Lisp 中，有两种主要的方法来实现集合，每种方法都有独特的性能特点和使用场景：使用简单的列表或使用哈希表（hash table）。

方法一：将集合实现为列表

表示集合最简单的方法是使用列表，其中你需要手动强制实现唯一性。Common Lisp 提供了辅助函数，使这变得容易且符合惯用法。

基于列表的惯用集合操作

;; 创建一个列表形式的集合。
(defvar *my-list-set* '(1 2 3 4 5))

;; 使用 MEMBER 检查成员是否存在。
;; MEMBER 返回从找到的元素开始的列表剩余部分（一个“真”值），
;; 如果未找到则返回 NIL（假）。
(print (member 3 *my-list-set*))   ; ==> (3 4 5)
(print (member 6 *my-list-set*))   ; ==> NIL

;; 使用 ADJOIN 添加元素。
;; ADJOIN 仅在元素不存在时才添加它。
;; 它是非破坏性的，并返回一个新列表。
(let ((new-set (adjoin 6 *my-list-set*)))
  (print new-set))                ; ==> (6 1 2 3 4 5)

;; 尝试添加一个已存在的元素不会有任何效果。
(let ((same-set (adjoin 3 *my-list-set*)))
  (print same-set))               ; ==> (1 2 3 4 5)

;; 使用 REMOVE 删除元素。
(let ((removed-set (remove 3 *my-list-set*)))
  (print removed-set))             ; ==> (1 2 4 5)

输出

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

基于列表的集合的特点

• 实现简单：易于理解，并使用标准列表函数。
• 保留插入顺序：adjoin 等函数会添加到列表前端，实际上创建了反向的插入顺序。这个顺序是可预测的。
• 成员检查效率低（O(n)）：要检查元素是否存在 (member)，Lisp 可能需要扫描整个列表，这使得它在大集合中速度较慢。
• 添加效率低（O(n)）：添加元素 (adjoin) 需要首先进行成员检查，导致 O(n) 复杂度。
• 适用于小集合：非常适合性能要求不高且重视简单性的小型集合。

方法二：将集合实现为哈希表

对于高性能集合，哈希表是更优的选择。我们将集合的元素用作哈希表中的键。值是无关紧要的，通常设置为 t。

基于哈希表的集合实现

;; 创建一个空的哈希集合（我们必须为键比较指定一个“测试”）。
(defvar *my-hash-set* (make-hash-table :test 'equal))

;; 添加多个项的辅助函数。
(defun add-to-set (set &rest items)
  (dolist (item items) (setf (gethash item set) t)))

;; 向哈希集合添加元素。
(add-to-set *my-hash-set* 1 2 3 4 5)

;; 使用 GETHASH 检查成员是否存在。
;; GETHASH 返回值和第二个布尔值，指示元素是否存在。
(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))

;; 使用 REMHASH 删除元素。
(remhash 1 *my-hash-set*)
(format t "Size of set after removing 1: ~a~%" (hash-table-count *my-hash-set*))

输出

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

基于哈希表的集合的特点

• 高效的成员检查（平均 O(1)）：检查元素是否存在非常快，平均复杂度为常数时间。
• 高效的添加/删除（平均 O(1)）：添加和删除元素平均也是常数时间操作。
• 不保留顺序：哈希表不保证其键的任何特定顺序。
• 空间开销：哈希表的内存占用比列表高，特别是对于非常小的集合。
• 需要良好的哈希函数：性能取决于哈希函数。对于自定义对象，可能需要定义自定义的哈希函数。

结论：如何选择？

特性	列表作为集合	哈希表作为集合
成员检查	慢 (O(n))	快 (平均 O(1))
添加/删除	慢 (O(n))	快 (平均 O(1))
保留顺序	是	否
最佳用途	小型、性能非关键集合	大型或性能关键集合
实现	非常简单，使用内置列表函数	略复杂，需要哈希表设置