为什么`sxhash`为所有结构返回一个常量？

Question

sxhash在结构上使用Common Lisp 函数时,我得到所有结构的相同值(在SBCL中只有相同类型的结构).例如,以下代码打印两个整数列表,所有这些整数都具有相同的值.

(progn 
  (defstruct foo 
    data)
  (print (mapcar #'sxhash (loop for i below 10 collect (make-foo :data i))))
  (defstruct bar 
    data)
  (print (mapcar #'sxhash (loop for i below 10 collect (make-bar :data i)))))

 ;;; Allegro
 (319 319 319 319 319 319 319 319 319 319) 
 (319 319 319 319 319 319 319 319 319 319) 
 ;;; SBCL
 (22591133455133788 22591133455133788 22591133455133788 22591133455133788
 22591133455133788 22591133455133788 22591133455133788 22591133455133788
 22591133455133788 22591133455133788) 
(21321591953876048 21321591953876048 21321591953876048 21321591953876048
 21321591953876048 21321591953876048 21321591953876048 21321591953876048
 21321591953876048 21321591953876048) 

我已经在Allegro Lisp和SBCL中尝试了这个,并且两个返回(不同)常量用于所有结构(在SBCL中相同类型).在链接的sxhashHyperspec页面上有以下语句:

2. 对于任何两个对象,x和y,它们都是位向量,字符,圆锥,数字,路径名,字符串或符号,并且相似,(sxhash x)和(sxhash y)产生相同的数学值,即使x和y存在于相同实现的不同Lisp图像中.请参见第3.2.4节(编译文件中的文字对象).

3. 对象的哈希码在单个会话中始终是相同的,前提是对象在等效性测试相等方面没有明显修改.请参见第18.1.2节(修改哈希表键).

后一种说法没有具体说明,但似乎暗示,两个不equal具有不同哈希码的结构(模数碰撞)是明智的.但是,第一段清单中的结构是可疑的.起初我把它归结为Allegro Lisp中的一个错误,但现在我在两个不同的实现中看到它,我认为必须有一些关于我不理解的规范.

Answer 1

我查询了Franz的支持,这是他们的回应.据推测,SBCL正在做类似的事情.

函数cl:sxhash始终为结构对象返回相同的值.这是因为它没有额外的空间来存储其中的唯一哈希码.结果,使用结构作为键是非常低效的.excl :: hash-table-stats函数在给定带有用作键的结构的哈希表时演示了这一点; 直方图成为最坏的情况,因为每个键都需要相同的索引.

决定保持结构对象的相同行为,因为在所有结构对象中自动包含散列槽将使所有结构平均延长一个单词.对于小型结构,这对我们的许多用户来说是不可接受的.

相反,用户可以定义具有额外槽的结构,并且该结构类型的构造函数可以将唯一值存储到该槽​​中(随机值或通过在每次运行构造函数时递增计数器而获得的值).此外,创建一个哈希生成函数,该函数访问此哈希槽以生成其值.如果要散列的结构被隐藏在列表中,那么这个散列函数需要知道如何遍历这些键以获得唯一值.最后,使用记录的:hash-function参数来构建哈希表,使用make-hash-table(仍使用相等的测试参数),以创建一个分布均匀的哈希表.

或者,如果您可以保证在将结构中的任何插槽用作散列表中的键之后不会更改它们,则可以在make-hash-table调用中使用equalp测试函数,而不是相等.但是,如果这样做,请确保这些struct对象不会更改,因为它们可能在散列表中找不到.