列表的非加密哈希函数

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，太。