嗨，有人可以建议一个哈希函数来获取整数列表并返回一个新的integer吗？它应该快速评估并且或多或少地抗碰撞。我计划在近似搜索算法中使用它（例如 LSH）
Java 的hashCode()列表使用这个公式：
31 + SUM 31^(i+1) *a[i]
有人知道为什么它是抗碰撞的吗？我想这大约是 31 是一个素数，但不知道如何证明它。
问问题
830 次
1 回答
1
您的公式错误（倒数），实际上是：
SUM 31^(n-1-i) * a[i]
其中n是列表的长度，我们也使用 a[-1] = 1。或者，如果你想单独拥有它，
31^n + SUM 31^(n-1-i) * a[i]
（和 Java 的整数一样，结果取模 2^32。）
Java 的hashCode()for List （在 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。
于 2013-05-11T15:45:10.577 回答