在哈希表中搜索键

Lisp - 搜索哈希表

哈希表（Hash table）是 Common Lisp 中一种基本的数据结构，它提供了一种高效的方式来使用键值对存储和检索数据。由于其在查找操作中典型的平均时间复杂度为 O(1)，因此它们非常适合用于缓存、记忆化（memoization）和管理数据字典。本章探讨如何在 Lisp 哈希表中搜索值。

gethash 函数

用于搜索哈希表的主要函数是 gethash。

(gethash key hash-table [default-value])

gethash 返回两个值：

• value：与 key 关联的值。如果未找到键，则返回 default-value（如果未提供，则为 NIL）。
• found-p：一个布尔值（T 或 NIL），指示 key 是否实际存在于哈希表中。

使用 multiple-value-bind 进行惯用搜索

由于 gethash 在键不存在时返回 NIL，因此您无法区分键缺失和键的值实际为 NIL 的情况。处理这种情况的惯用且正确的方法是使用 multiple-value-bind 来捕获两个返回值。

;; 安全哈希表查找的通用模式
(multiple-value-bind (value found-p) (gethash key my-hash-table)
  (if found-p
      (format t "Key found! Value: ~a~%" value)
      (format t "Key not found.~%")))

示例 1：使用符号作为键的哈希表

默认情况下，make-hash-table 创建的表会使用 eql 比较键，这适用于数字、字符和符号。

main.lisp

;; 创建一个哈希表（默认测试函数为 'eql'）
(let ((my-table (make-hash-table)))
  ;; 添加一些键值对
  (setf (gethash 'id-001 my-table) "Alice")
  (setf (gethash 'id-002 my-table) "Bob")

  ;; --- 搜索存在的键 ---
  (multiple-value-bind (value found-p) (gethash 'id-001 my-table)
    (if found-p
        (format t "Found key 'id-001. User: ~a~%" value)
        (format t "Key 'id-001 not found.~%")))

  ;; --- 搜索不存在的键 ---
  (multiple-value-bind (value found-p) (gethash 'id-003 my-table)
    (if found-p
        (format t "Found key 'id-003. User: ~a~%" value)
        (format t "Key 'id-003 not found.~%"))))

输出

Found key 'id-001. User: Alice
Key 'id-003 not found.

示例 2：使用字符串作为键的哈希表

当使用字符串作为键时，您必须使用 :test #'equal 创建哈希表，因为两个内容相同的字符串可能不 eql。

main.lisp

;; 创建一个适合字符串键的哈希表
(let ((fruit-prices (make-hash-table :test #'equal)))
  ;; 添加一些键值对
  (setf (gethash "apple" fruit-prices) 1.50)
  (setf (gethash "banana" fruit-prices) 0.75)

  ;; --- 搜索存在的键 ---
  (multiple-value-bind (price found-p) (gethash "apple" fruit-prices)
    (if found-p
        (format t "Price of an apple: $~,2f~%" price)
        (format t "Apple not found in price list.~%")))

  ;; --- 搜索不存在的键 ---
  (multiple-value-bind (price found-p) (gethash "mango" fruit-prices)
    (if found-p
        (format t "Price of a mango: $~,2f~%" price)
        (format t "Mango not found in price list.~%"))))

输出

Price of an apple: $1.50
Mango not found in price list.

修改和清空哈希表

除了搜索，您经常需要修改哈希表：

• 添加/更新：(setf (gethash key table) value) 用于添加新键值对和更新现有键的值。
• 移除：(remhash key table) 从表中移除键值对。如果找到并移除了键，它返回 T，否则返回 NIL。
• 清空：(clrhash table) 移除哈希表中的所有条目，使其变为空。