LISP - 哈希表

Lisp - 散列表

散列表（Hash Table），是一种基本的数据结构，用于存储键值对的集合。它提供了高效（均摊O(1)时间复杂度）的查找、插入和删除操作。在Lisp中，它相当于Python的Dictionary、Java/JavaScript的Map或Ruby/Perl的hash。

创建散列表

你可以使用 make-hash-table 函数创建散列表。它最重要的参数是 :test，用于指定键的比较方式。

(make-hash-table :test #'eql :size 100)

:test 参数的选择至关重要，它决定了散列表的行为：

• #'eq：通过对象标识（内存位置）比较键。速度快，但仅当您使用 完全相同的对象 作为存储和检索的键时才有效。适用于符号（symbol）。
• #'eql （默认值）：按照 eq 比较，但也会将两个类型和值都相同的数字，或者两个相同的字符视为相同。这是一个安全且通用的默认选项。
• #'equal：按结构比较。它会把内容相同的两个不同列表或字符串视为同一个键。这更灵活，但速度较慢。
• #'equalp：equal 的一个不区分大小写且不区分数字类型的版本。

常见错误：选择错误的比较函数

一个常见的错误是将默认的 #'eql 比较函数用于字符串键。两个具有相同字符的字符串不一定 eql。对于字符串键，请始终使用 #'equal。

;; 不正确：可能无法按预期工作
(defvar *ht-wrong* (make-hash-table :test #'eql))
(setf (gethash "mykey" *ht-wrong*) 1)
(gethash "mykey" *ht-wrong*) ; -> NIL, T (Might fail!)

;; 正确：对于字符串键始终使用 'equal'
(defvar *ht-correct* (make-hash-table :test #'equal))
(setf (gethash "mykey" *ht-correct*) 1)
(gethash "mykey" *ht-correct*) ; -> 1, T (Always works)

核心操作（增删改查）

使用散列表涉及几个关键函数。

(let ((user-data (make-hash-table :test #'equal)))
  ;; 创建 / 更新：使用 (setf gethash)
  (setf (gethash "user:123" user-data) '(:name "Alice" :email "alice@example.com"))
  (setf (gethash "user:456" user-data) '(:name "Bob" :plan "premium"))

  ;; 读取：使用 gethash
  ;; gethash 返回两个值：键对应的值和一个布尔值，指示是否找到了键。
  (multiple-value-bind (value found-p) (gethash "user:123" user-data)
    (if found-p
        (format t "Found user: ~a~%" value)
        (format t "User not found.~%")))
  ;; -> Found user: (NAME "Alice" :EMAIL "alice@example.com")

  ;; 删除：使用 remhash
  (remhash "user:456" user-data)

  ;; 检查被删除的键
  (gethash "user:456" user-data)
  ;; -> NIL, NIL
)

遍历散列表

您可以使用 maphash 或 loop 宏处理表中的每个键值对。

使用 maphash

maphash 将一个函数应用于每个键值对。请注意，散列表本质上是无序的。

(let ((ht (make-hash-table)))
  (setf (gethash :a ht) 1)
  (setf (gethash :b ht) 2)
  (maphash #'(lambda (key value)
               (format t "Key: ~a, Value: ~a~%" key value))
           ht))
;; 输出（顺序不保证）：
;; Key: B, Value: 2
;; Key: A, Value: 1

使用 loop 宏

loop 宏通常提供了一种更具可读性和灵活性的迭代方式。

(let ((ht (make-hash-table)))
  (setf (gethash :a ht) 1)
  (setf (gethash :b ht) 2)

  ;; 遍历键和值
  (loop for key being the hash-key of ht
        using (hash-value value)
        do (format t "~a -> ~a~%" key value))

  ;; 将所有值收集到一个列表中
  (let ((values (loop for value being the hash-value of ht collect value)))
    (print values));; -> (1 2) or (2 1)
)

实际应用：一个简单的缓存

散列表非常适合记忆化（memoization），这是一种缓存昂贵函数调用结果的技术。

(defun make-memoized (fn)
  "返回一个单参数函数的记忆化版本。"
  (let ((cache (make-hash-table :test #'equal)))
    (lambda (arg)
      (multiple-value-bind (result found-p) (gethash arg cache)
        (if found-p
            result
            (setf (gethash arg cache) (funcall fn arg)))))))

(defun slow-computation (n)
  (format t "Computing for ~a...~%" n)
  (sleep 2) ; 模拟一个慢速操作
  (* n n))

(defvar memo-slow-computation (make-memoized #'slow-computation))

(funcall memo-slow-computation 5) ; -> 计算并打印 25
(funcall memo-slow-computation 5) ; -> 从缓存中立即返回 25