时间戳

首页 > 解决方案 > 在 SBCL 中为自定义散列表定义散列函数

common-lisp - 在 SBCL 中为自定义散列表定义散列函数

问题描述

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

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

whereht-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，但超规范说这仅适用于equal键（不是equalp，这是哈希表相等测试所必需的）。感谢您的任何帮助。

标签： common-lisphashcodesbcl

解决方案

一个快速而简单的哈希函数代码是简单地将输入 ht 中的 fixnum 键相加，因为对于任何 fixnums 的排列，总和都是相同的。对于这个问题，事实证明，ht fixnums 都明显小于most-positive-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))

推荐阅读