SBCL自定义哈希表中适配equalp比较的哈希函数实现问题

最优现成方案 #

SBCL内置了sb-ext:hash-equiv函数，其返回值完全匹配equalp的相等判断规则，输出为非负fixnum类型，直接使用即可满足需求：

(defun ht-hash-fn (struct-key)
  (sb-ext:hash-equiv (ht-accessor struct-key)))

该实现完全符合自定义哈希表测试的约束：只要两个结构体内的哈希表内容满足equalp相等，返回的哈希值一定相等。

自定义实现方案 #

如果需要手动实现逻辑（比如需要自定义哈希碰撞规避规则、或者要兼容其他Common Lisp实现），可以遍历内部哈希表的fixnum键，采用顺序无关的方式组合哈希值：

(defun ht-hash-fn (struct-key)
  (let ((hash 0))
    (maphash (lambda (k v)
               (declare (ignore v)
                        (type fixnum k))
               ;; 异或操作天然顺序无关，移位操作可降低相近数值的碰撞概率
               (setf hash (logxor hash (ash (sxhash k) 3))))
             (ht-accessor struct-key))
    hash))

该实现的核心逻辑说明：

• fixnum类型的相等判断中equal和equalp规则完全一致，因此对单个fixnum键使用sxhash是合法的
• 采用异或组合哈希值是因为内部存储的是fixnum集合，集合的相等性和元素顺序无关，异或操作不会受遍历顺序影响

核心注意事项 #

自定义哈希表测试时必须严格遵守一致性约定：只要两个键通过ht-equality-fn判断为相等，二者的ht-hash-fn返回值必须完全相等，否则会出现哈希表查询失效、重复插入相同键等问题。

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