列表的非加密哈希函數

Question

嗨，有人可以建議哈希函數，將採取一個整數列表並返回一個新的integer？ 它應該是快速評估和或多或少的碰撞抵抗。 我計劃在近似搜索算法（例如LSH）使用它

Java的hashCode()的列表使用這個公式：

31 + SUM 31^(i+1) *a[i] 

沒有任何人知道爲什麼它是碰撞性？我想這大約是31歲，但不知道如何證明。

Answer 1

你有你的公式錯誤的（它向前算起），它實際上是：

SUM 31^(n-1-i) * a[i] 

其中n是列表的長度，我們還使用了[-1] = 1，或者，如果要單獨擁有它，

​​

（而結果取模2^32，像往常一樣對Java的整數。）

Java的hashCode()的名單（specified in java.util.List，並且應該由該類的每個實現來實現）是在加密意義上不是抗衝突的。那就是，不是很難找到碰撞。

給定任何具有多個元素的整數列表，我們可以將其中一個元素增加1，然後將下一個元素減少31（或其他方式），並使第二個列表具有相同的散列碼。

例如，兩個列表[1, 0]和[0, 31]具有相同的散列碼992 = 31·32 = (1·31 + 1)·31 + 0 = (1·31 + 0)·31 + 31。

它對於意外碰撞具有一定的弱抵抗力，這確實與31是素數（即沒有真正的除數）有關，並且「自然出現」的整數列表（或其他對象的哈希碼）沒有往往會因此而有所不同。

當然，如果我們建立列表的列表，其中的每一個使用相同的策略哈希碼，我們得到的碰撞很容易：[ [0, 1], [0, 0] ]和[ [0, 0], [1, 0] ]具有相同的散列碼31³+ 2·31²+ 31 = 31744，太。