爲什麼`sxhash`爲所有結構返回一個常量？

當在結構上使用Common Lisp sxhash函數時，我得到了所有結構的相同值（在SBCL中只有相同類型的結構）。例如，下面的代碼打印出兩個具有相同值的整數列表。爲什麼`sxhash`爲所有結構返回一個常量？

(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頁有以下語句：

對於任何兩個對象，x和y，這兩者都是位向量，字符，conses之外，數字路徑名，字符串或符號，以及哪個類似，（sxhash x）和（sxhash y）產生相同的數學值，即使x和y存在於相同實現的不同Lisp圖像中。請參見第3.2.4節（編譯文件中的文字對象）。

對象的散列碼在單個會話中始終是相同的，前提是該對象不會被可視地修改爲關於與等效性測試相等。參見18.1.2節（修改哈希表表鍵）。

後者語句未指定，但似乎暗示，這將是明智的這兩個結構不屬於equal會有不同的哈希碼（模碰撞）。但是，第一段中的結構可疑地缺失。起初，我將這寫成了Allegro Lisp中的一個錯誤，但現在我發現它有兩種不同的實現方式，我認爲必須有一些關於我不明白的規範。

來源

2014-01-14 asm

一個保證是，如果'（等於x y）'那麼'（=（sxhash x）（sxhash y））'。我似乎記得（但我可能會混淆comp.lang.lisp和hyperspec），你看到的並不少見，因爲有不同的東西會有相同的sxhash散列值。 – Vatine

@Vantine是的，看起來至少SBCL和Allegro是出於內存佔用的原因。他們不能使用內存地址，因爲它會改變，並且hyperspec要求'sxhash'對於相同實現中的類似對象是相同的。此外，他們不能做遞歸遍歷（安全），因爲對象可能會發生變異。 – asm

我詢問過弗朗茨的支持，這是他們的迴應。據推測，SBCL出於類似的原因正在做類似的事情。

函數cl：sxhash總是爲結構體返回相同的值。原因是因爲它沒有額外的空間來存儲一個唯一的哈希代碼。因此，使用結構作爲鍵是非常低效的。 excl :: hash-table-stats函數演示給定一個散列表，其中結構用作鍵;直方圖成爲最差的情況，因爲每個鍵都需要相同的索引。

決定保留結構對象的相同行爲，因爲在所有結構對象中自動包含哈希槽將使所有結構的平均值延長一個單詞。對於小結構，這是我們許多用戶無法接受的。

取而代之的是，用戶可以定義與一個額外的時隙中的結構，並且構造該結構類型可以存儲一個唯一的值到該槽（無論是通過每次遞增計數器得到的隨機值或值構造函數運行）。此外，創建一個散列生成函數，該函數訪問此散列槽以生成其值值。如果被散列的結構被埋藏在一個列表中，那麼這個散列函數將需要知道如何遍歷這些關鍵字以獲得一個唯一的值，即。最後，使用散列函數參數爲make-hash-table（仍然使用相等的測試參數）構建散列表，以創建一個散列表，該散列表將是均勻分佈的散列表。

或者，如果你能保證無縫隙的在你的結構將改變它們用作哈希表密鑰後，您可以使用equalp測試功能在您的化妝散列表呼叫，而不是平等的。但是，如果確實這樣做，則確保這些結構對象不會更改，因爲在散列表中可能找不到。

來源

2014-01-15 01:56:12 asm

在http://marc.info/?l=sbcl-devel&m=121182898514193&w=2上也有一些討論。 – Hugh

謝謝，我希望有更多關於SBCL的知識的人會證實。 – asm

有很多sxhash兩個重要的性質：如果(equal x y)然後(= (sxhash x) (sxhash y))和由sxhash返回的值是各種方式獲得（即使口齒不清圖像之間）的任何對象是相同的。

現在結構equal如果只是如果他們eq（即它們具有相同的地址），但sxhash不能簡單地返回結構的地址（或散列物），因爲地址可由於垃圾收集改變。因此，在設計lisp實現時，必須選擇每個結構是否具有相同的sxhash，或者在垃圾收集器移動結構時不會在每個結構中存儲某些標識，因此可用於該對象。大多數實現（包括Franz和sbcl）都會考慮添加這樣一個值，如果只有少量備用位被賦予，那麼浪費空間或無用。

這個權衡最終只會影響用戶嘗試實現哈希表，因爲實現自己的哈希表可以使用對象的地址並通知垃圾收集器這樣它們可以在對象移動時重新哈希（我不知道無論是否有任何實現都這樣做）。某些實現（包括sbcl）允許您使用自己的比較/散列操作來自定義內置散列表。也許如果你自己實現散列，你可以爲結構添加一個額外的字段。

我相信在sbcl中由sxhash返回的結果是通過散列結構類型的名稱來確定的。

來源

2017-07-18 15:21:09

爲什麼`sxhash`爲所有結構返回一個常量？

回答

相關問題