在SBCL中为自定义哈希表定义哈希函数

Question

SBCL手册说，可以使用以下宏来定义自定义哈希表的测试：

(sb-ext:define-hash-table-test ht-equality-fn ht-hash-fn)

其中ht-equality-fn确定两个键是否相同，ht-hash-fn确定键的哈希值。

在这个特定的例子中，键本身就是结构(用defstruct定义)，其中的一个槽包含一个哈希表，表中有固定的键和T值(表示固定数的集合)。

如果我正确理解了SBCL要求，那么编写ht-equality-fn的简单方法似乎是：

(defun ht-equality-fn (key1 key2)
  (equalp (ht-accessor key1) (ht-accessor key2))

但我不知道如何编写散列函数来获得非负的fixnum散列代码：

(defun ht-hash-fn (ht)
  ???)

一开始我想使用sxhash，但hyperspec说这只适用于equal键(而不是equalp，因为哈希表相等性测试需要)。谢谢你的帮助。

Answer 1

一个快捷的散列函数代码是简单地对输入ht中的fixnum键求和，因为对于任何fixnums的排列，总和都是相同的。对于这个问题，正如事实证明的那样，ht的固定数都明显小于most-positive-fixnum，因此和不应该超过最大值。然而，考虑到许多不同的fixnum集合可以加起来为相同的值，最坏情况下的散列性能可能是不足的。

(defun ht-hash-fn (ht)
  (declare (hash-table ht))
  (let ((sum 0))
    (declare (fixnum sum))
    (maphash (lambda (key value)
               (declare (fixnum key) (ignore value))
               (incf sum key))
      ht)
    sum))