使用自定义相等性检查

Lisp - 哈希表中的自定义相等性

哈希表 (hash table) 是一种将键 (keys) 映射到值 (values) 的基本数据结构，提供快速查找。在 Common Lisp 中，哈希表的强大功能通过指定键相等性的自定义测试而大大增强。这使你能够精确定义两个键“相同”的含义。

make-hash-table 中的 :test 参数

创建哈希表时，你可以提供 :test 参数来指定用于比较键的相等函数。理解这些常见选项至关重要。

• #'eq：测试对象标识。只有当两个键在内存中是完全相同的对象时，它们才 eq。这是最快的测试，但很少用于字符串或列表键。
• #'eql：默认测试。它的行为类似于 eq，但也认为两个相同类型和值的数字，或两个相同的字符是相等的。
• #'equal：测试结构相等性。它递归比较列表和向量，并逐字符比较字符串。这是字符串或列表键的常见选择。
• #'equalp：equal 的更宽松版本。它忽略字符串/字符中的大小写差异，并认为不同类型的数字（例如 2 和 2.0）是相等的。

字符串键默认行为的问题

让我们看看当我们将默认 :test (#'eql) 用于字符串键时会发生什么。在 Lisp 中，代码中每个字面量字符串 "apple" 都可以创建一个新的、独立的内存对象。

示例：默认 :test (eql)

;; 创建一个使用默认测试的哈希表
(let ((my-hash-table (make-hash-table)))

  ;; 这里的键 "apple" 可能与下面的对象不同
  (setf (gethash "apple" my-hash-table) 1)

  ;; 这个 `gethash` 调用使用另一个 "apple" 字符串对象进行查找。
  ;; 因为它与 `setf` 中使用的键不 `eql`，所以查找失败。
  (format t "Value for \"apple\": ~a~%" (gethash "apple" my-hash-table)))

输出

Value for "apple": NIL

查找失败是因为用于存储值的键和用于检索值的键是两个不同的字符串对象，即使它们的内容相同。它们不 eql。

为字符串使用 equal 和 equalp

要解决此问题，我们必须告诉哈希表比较字符串的内容，而不是它们的内存位置。

示例：使用 :test #'equal（区分大小写）

(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)))

输出

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

使用 #'equal 时，比较是区分大小写的，因此 "apple" 和 "Apple" 被视为不同的键。

示例：使用 :test #'equalp（不区分大小写）

(let ((my-hash-table (make-hash-table :test #'equalp)))
  ;; 首先，我们为键 "apple" 设置值
  (setf (gethash "apple" my-hash-table) 1)

  ;; 由于 `equalp`，"Apple" 被视为相同的键。
  ;; 这会覆盖之前的值。
  (setf (gethash "Apple" my-hash-table) 2)

  ;; 现在查找 "apple" 会检索到该键最近设置的值。
  (format t "Value for \"apple\": ~a~%" (gethash "apple" my-hash-table))
  (format t "Value for \"Apple\": ~a~%" (gethash "Apple" my-hash-table)))

输出

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

最佳实践与高级用法

• 选择正确的测试函数：对于字符串键，#'equal 是最常见和最安全的选择。仅当你明确需要不区分大小写行为时才使用 #'equalp。对于符号或保证是唯一对象的键（例如，表示系统资源的键），请使用 #'eq。
• 性能：这些测试具有不同的性能特征：eq 最快，其次是 eql、equal，最后是 equalp，它最耗费性能。
• 自定义函数：你可以向 :test 提供自己的双参数比较函数。这对于将复杂对象用作键非常强大，在这种情况下，相等性可能基于特定字段，例如用户 ID。