arrays - 偏移独立散列函数

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. 找到字典序最小的数组旋转。

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

   参见 this了解更多。

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

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

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

具有不同元素的数组将散列为相同的值并非不可能(这在散列中是不可避免的)，但同一数组的所有旋转将具有相同的散列。