是否有任何散列函数为具有相同元素的向量生成相同的存储桶，具有相同的相对位置，但是移位了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）。有了这个，我只需要移动每个向量，使最大值总是在第一个位置。这种方式移动的向量看起来是一样的。然而，向量可以具有重复的元素，因此最大值具有不同的位置。
找到字典上最小的数组旋转。
原生方法是检查O中的所有旋转，但它可以使用布斯算法，Shiloach的快速优化算法或Duval的Lyndon因式分解算法在线性时间内完成。
有关更多信息，请参见this。
计算旋转数组的散列。
这可以通过各种方式完成。 Java中，例如，可以按如下方式做到这一点：
hash = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
这不是不可能的，不同的元素阵列将返回相同的值（这是不可避免的散列），但同一阵列的所有旋转将具有相同的散列。
如果我们串接B1与本身然后我们得到：
[1,9,8,7,1,9,8,7]
此数组包含原始数组的所有循环排列。
如果我们然后计算每个长度为4的子数组的散列值并加入并组合这些散列值，那么您将拥有一个唯一的散列值。散列函数计算可能需要进行一些优化，具体取决于阵列的大小。
编辑：每个子数组，除了最后一个，等于第一个！
如果你不太关心偶尔发生的散列冲突，你可以简单地将所有元素的总和作为散列（但要小心浮点问题），因为这对向量的任何旋转都是不变的。或者，您可以将xor或总和所有单个元素的散列值相加。你也可以根据后续元素的差异来计算某些东西（同时包含最后一个元素到第一个元素）。添加一些旋转不变的属性，两个“不相等”的数组产生相同散列的几率会非常低。也许类似于
n = length(x)
rot_invariant_hash = hash(n) + sum(hash(x[i])) + sum(hash(x[mod(i+1, n)] - x[i]))
您可以在其中替换任何其他可交换（？）操作（如XOR）的所有总和。还要确保应用于差异的散列函数不是标识函数，否则这些部分将全部加起来为零。所有这些都需要O（n）的计算时间。
只是一个好奇心：你打算的应用是什么？
我正在尝试开发循环多边形的散列函数。因此，输入向量是外接圆中不同节点的相对距离。 –
无（对于OP）：如果你需要做一个最后的比较（散列之后），你将不得不把你的循环多边形变成一些规范的形式。 – joop
假设你总是有数字作为矢量分量，计算：
i，(i+1) mod n） 其中加1的d_i对于所有非负差异并将两者相乘。
第一个产品从元素的顺序抽象出来，这是由第二个产品的模数旋转重新引入的。如果存在具有相同值的两个相邻分量，则将每个差分加1避免映射到0。
独立的第一个产品是不够的，因为它将所有组件排列映射到相同的散列值。因为它将沿着（1，...，1）偏移的所有向量映射到相同的值，所以独立的第二个产品是不够的。
我会试试这个解决方案，但我有一个观察：如果连续的元素是相等的，那么相邻元素的所有差异的乘积就是零，所以我认为它应该是同一个符号的所有差异加和偏移的乘积差异本身。 –
@PabloFranciscoPérezHidalgo：好的，谢谢。答案调整。 – collapsar
不要散列数组的元素，哈希两个相邻单元的差异，而不是：
#include <stdio.h>
unsigned hashdiff(unsigned arr[], size_t siz);
/* toy hash function: don't try this at home ... */
#define HASH1(v) ((v)*7654321)
unsigned hashdiff(unsigned arr[], size_t siz)
{
unsigned idx;
unsigned hash;
if (siz < 1) return 0;
if (siz < 2) return HASH1(arr[0]);
hash = HASH1(arr[0] - arr[siz-1]);
for(idx=1; idx < siz; idx++) {
hash ^= HASH1(arr[idx] - arr[idx-1]);
}
return hash;
}
unsigned arr1[] = {1,9,8,7};
unsigned arr2[] = {9,8,7,1 };
unsigned arr3[] = {1,8,9,7 };
unsigned arr4[] = {1,9,8,5 };
int main(void)
{
unsigned hash;
hash = hashdiff (arr1, 4); printf("%x\n", hash);
hash = hashdiff (arr2, 4); printf("%x\n", hash);
hash = hashdiff (arr3, 4); printf("%x\n", hash);
hash = hashdiff (arr4, 4); printf("%x\n", hash);
return 0;
}
结果：
./a.out
fee56452
fee56452
1100b22
fca02416
UPDATE：如果你不想{1， 2,3,4}和{} 11,12,13,14散列为相同的值，可以增加这样的区别：
#define HASH1(v) ((v)*7654321)
#define HASH2(a,b) HASH1(3u*(a)-5u*(b))
unsigned hashdiff2(unsigned arr[], size_t siz)
{
unsigned idx;
unsigned hash;
if (siz < 1) return 0;
if (siz < 2) return HASH1(arr[0]);
hash = HASH2(arr[0] , arr[siz-1]);
for(idx=1; idx < siz; idx++) {
hash ^= HASH2(arr[idx] , arr[idx-1]);
}
return hash;
}
我还没有编码的，但我认为它可以工作：
为了让您的哈希值，你只需要抓住项目的顺序，避免偏移。有点像这样的项目：
a = [1,9,8,7]
s = sort(a) = [1,7,8,9]
现在捕捉它们之间的顺序：
1 => 9
7 => 1
8 => 7
9 => 8
snext = next(s, a) = [9,1,7,8]
现在CONCAT S和snext：
[1,7,8,9,9,1,7,8]
和散列它。
为了实现next（）函数只使用载体作为关联数组和遍历s个项目。
阵列因为它共享相同的项目和它们的相对阶数等于[9,8,7,1]将产生相同的散列。
然而，阵列[1,8,9,7]产生不同的散列;它共享相同的项目，但它们的相对顺序不一样。
我希望它有帮助。
没有必要连接向量与自身，只是循环地从每个向量位置迭代，这将提供相同的结果，而不会使内存使用加倍。我认为你的解决方案在形式上是正确的，但如果我没有错，假设每个子阵列哈希计算都是O（n）[在这个例子中n = 4]，那么你的方法的时间复杂度至少为O（n^2）。我想知道是否可以改进。 –
它取决于散列函数的计算：假设h（k）= a0 + a1 k^1 + a2 k^2 + ...那么我们可以用一个常数计算第二个置换的h与第二个置换的h操作次数。因此h（1,9,8,7）可以被重新用来计算h（9,8,7,1），我们可以重用9,8,7部分（用k除）。 – DDW