偏移独立散列函数

Question

是否有任何哈希函数为具有相同元素的向量生成相同的桶,具有相同的相对位置但是移位了k次？

例如:

hash([1,9,8,7]) -> b1
hash([9,8,7,1]) -> b1

hash([1,8,9,7]) -> b2
hash([1,9,8,5]) -> b3

v1 = [1,9,8,7] v2 = [9,8,7,1]两个向量应该得到相同的散列,因为v2是v1左移k = 3次.

但是v3 = [1,8,9,7]不保持相同的相对顺序,并且v4 = [1,9,8,5]具有不同的值,因此它们都没有得到散列b1.

我最初的方法是计算每个向量的最大值,并将其位置视为参考(偏移= 0).拥有它我只需要移动每个向量,以便最大值始终位于第一个位置.这种方式移位的矢量看起来是一样的.然而,向量可以具有重复的元素,因此最大值具有不同的位置.

Answer 1

1. 求字典顺序最小的数组旋转。

   本机方法是检查 O(n ² ) 中的所有旋转，但可以使用 Booth 算法、Shiloach 快速规范化算法或 Duval 林登分解算法在线性时间内完成。

   请参阅此了解更多信息。

2. 计算旋转数组的哈希值。

   这可以通过多种方式来完成。例如，Java 将按如下方式执行：

   hash = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
   

具有不同元素的数组并非不可能散列到相同的值（这是散列不可避免的），但同一数组的所有旋转都将具有相同的散列。