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

Question

使用 Common Lisp 时 sxhash结构上的函数我为所有结构获得相同的值(在 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 中的相同类型)返回(不同的)常量。在链接的 sxhash Hyperspec 页面上有以下语句:

2. For any two objects, x and y, both of which are bit vectors, characters, conses, numbers, pathnames, strings, or symbols, and whichare similar, (sxhash x) and (sxhash y) yield the same mathematicalvalue even if x and y exist in different Lisp images of the sameimplementation. See Section 3.2.4 (Literal Objects in Compiled Files).

3. The hash-code for an object is always the same within a single session provided that the object is not visibly modified with regardto the equivalence test equal. See Section 18.1.2 (Modifying HashTable Keys).

后一个语句没有指定，但似乎暗示，两个不相等的结构将具有不同的哈希码(模冲突)是明智的。但是，可疑的是第一段的列表中没有结构。起初我将其归因于 Allegro Lisp 中的错误，但现在我在两种不同的实现中看到它，我认为一定有一些我不理解的规范。

Answer 1

我询问过 Franz 的支持，这是他们的回复。据推测，SBCL 出于类似原因正在做类似的事情。

The function cl:sxhash always returns the same value for structure objects. The reason for this is because it has no extra space to store a unique hash code within it. As a result, using structures as keys is very inefficient. The excl::hash-table-stats function demonstrates this when given a hash-table with structs used as keys; the histogram becomes the worst case, because every key wants the same index.

The decision was made to keep the same behavior for structure objects, because the automatic inclusion of a hashing slot in all structure objects would have made all structs an average of one word longer. For small structs this is unacceptable for many of our users.

Instead, a user may define a struct with an extra slot, and the constructor for that struct type could store a unique value into that slot (either a random value or a value gotten by incrementing a counter each time the constructor is run). Also, create a hash generating function which accesses this hash-slot to generate its value. If the structs to be hashed are buried inside a list, then this hash function would need to know how to traverse these keys to obtain a unique value. Finally, then, build your hash-table using the documented :hash-function argument to make-hash-table (still using the equal test argument), to create a hash-table which will be well-distributed.

Alternatively, and if you can guarantee that none of the slots in your structures will be changed after they are used as keys in the hash-table, you can use the equalp test function in your make-hash-table call, rather than equal. If you do, however, make sure that these struct objects don't change, because then they may not be found in the hash-table.