8

是否有任何散列函数为具有相同元素的向量生成相同的桶，具有相同的相对位置但移动了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）。有了它，我只需要移动每个向量，以便最大值始终位于第一个位置。这种方式移位的向量看起来是一样的。但是，向量可以具有重复的元素，因此最大值具有不同的位置。

4

6 回答 6

4

  1. 找到按字典顺序排列的最小数组旋转。

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

    有关更多信息，请参阅此。

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

    This can be done in various ways. Java, for example, would do it as follows:

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

It's not impossible that arrays with different elements will hash to the same value (this is inevitable with hashing), but all rotations of the same array will have the same hash.

于 2013-08-20T12:01:19.740 回答
1

如果我们将 b1 与自身连接起来，那么我们得到：

[1,9,8,7,1,9,8,7]

该数组包含原始数组的所有循环排列。

如果我们然后为每个长度为 4 的子数组计算一个哈希值，并将它们连接起来，你将得到一个唯一的哈希值。哈希函数计算可能需要一些优化，具体取决于数组的大小。

编辑：每个子数组，除了最后一个，它等于第一个！

于 2013-08-20T08:55:18.293 回答
1

如果您不太关心偶尔的哈希冲突，您可以简单地将所有元素的总和作为哈希（但要小心浮点问题），因为这对于向量的任何旋转都是不变的。或者，您可以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) 的计算时间。

只是好奇：您的预期应用是什么？

于 2013-08-20T10:09:37.657 回答
1

假设您始终将数字作为向量分量，请计算：

  • 所有组件的乘积
  • d_i相邻分量 ( i, )的所有差异的乘积(i+1) mod n，其中为所有非负差异添加 1

并乘以两者。

第一个产品从元素的顺序中抽象出来，这是由第二个产品模组件旋转重新引入的。如果有 2 个具有相同值的相邻分量，则将每个差值加 1 可避免映射到 0。

独立的第一个产品是不够的，因为它将所有组件排列映射到相同的哈希值。独立的第二个产品是不够的，因为它将所有沿 (1,...,1) 偏移的向量映射到相同的值。

于 2013-08-20T10:13:39.523 回答
1

不要散列数组的元素，而是散列两个相邻单元格的差异：

#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

更新：如果您不希望 {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;
}
于 2013-08-20T10:21:53.863 回答
0

I have not coded it, but I think it could work:

To get your hash you just need to capture the order of the items, and avoid the offset. Sort the items like this:

a = [1,9,8,7]
s = sort(a) = [1,7,8,9]

Now capture the order between them:

1 => 9
7 => 1
8 => 7
9 => 8

snext = next(s, a) = [9,1,7,8]

Now concat s and snext:

[1,7,8,9,9,1,7,8]

And hash it.

To implement next() function just use vector a as an associative array and iterate through s items.

The array [9,8,7,1] would yield same hash because it shares the same items and their relative order is equal.

Nevertheless, array [1,8,9,7] yields a different hash; it shares the same items but their relative order is not the same.

I hope it helps.

于 2016-06-02T00:42:27.830 回答