SBCL中EQ哈希表真的比EQUAL哈希表更高效吗？

我一直觉得哈希表使用EQ作为测试函数时效率应该远高于EQUAL，但下面的测试结果却正好相反，想请教大家这背后的原因。

辅助函数：生成随机字符串 #

(defun random-string (n)
  "Generate a random string of length n."
  (let ((charset "ABCDEFGHIJKLMNOPQRSTUVWXYZ"))
    (iter (repeat n)
          (collect (char charset (random (length charset)))
                   result-type string))))

测试1：使用EQUAL的哈希表 #

* (defparameter random-strings (iter (for i from 1 to 5000)
                                     (collect (random-string 5))))
RANDOM-STRINGS

* (defparameter ht (make-hash-table :test #'equal :size 10000))
HT

* (dolist (rs random-strings)
    (setf (gethash rs ht) t))
NIL

* (time (dotimes (i 1000000)
          (dolist (rs random-strings)
            (gethash rs ht))))

Evaluation took:
  14.420 seconds of real time
  8.703125 seconds of total run time (8.687500 user, 0.015625 system)
  60.35% CPU
  51,914,146,826 processor cycles
  0 bytes consed

测试2：使用EQ的哈希表 #

* (defparameter random-strings (iter (for i from 1 to 5000)
                                     (collect (intern (random-string 5)))))
RANDOM-STRINGS

* (defparameter ht (make-hash-table :test #'eq :size 10000))
HT

* (dolist (rs random-strings)
    (setf (gethash rs ht) t))
NIL

* (time (dotimes (i 1000000)
          (dolist (rs random-strings)
            (gethash rs ht))))

Evaluation took:
  15.309 seconds of real time
  9.500000 seconds of total run time (9.484375 user, 0.015625 system)
  62.06% CPU
  55,112,812,169 processor cycles
  0 bytes consed

结果分析 #

这种反常结果可以从几个核心角度解释：

• EQUAL的实现优化：多数Common Lisp实现会给EQUAL做针对性优化——当比较的两个对象是同一个实例时（比如本次测试中，查找用的字符串和哈希表中存储的是同一个对象），EQUAL会直接退化为EQ的指针比较，完全跳过逐字符检查的开销，此时两者的执行逻辑几乎一致。
• 符号哈希的额外开销：intern生成的符号对象，除了包含名字字符串外，还关联了包、属性列表等额外数据。其哈希值计算逻辑比单纯的字符串哈希更复杂，或者不同Lisp实现中符号哈希算法本身的耗时就高于字符串。
• 哈希冲突概率差异：两种哈希表使用的哈希函数不同，可能导致EQ哈希表的冲突率更高，进而增加了查找时的比较次数。如果测试中符号的哈希值分布不如字符串均匀，就会拉长查找耗时。
• 具体实现的差异：不同Common Lisp实现（如SBCL、CCL）对哈希表、EQ/EQUAL的优化程度不同，本次测试结果高度依赖你使用的具体Lisp环境。

内容的提问来源于stack exchange，提问作者davypough