具有最小冲突的两个整数数组的哈希函数

Question

我正在解决一个问题，我想在数据结构（例如 hashmap）中存储由两个等长整数数组（例如 int a[] ={1,2,3,4} 和 int b[] ={1,2,2,6}）组成的对象.但是，对于不同的对象，两个数组的长度可能会有所不同。两个数组都由给定区间（例如 0-200 之间）的整数组成。

为了用两个数组存储对象，我想分配一个计算速度快、保留两个序列并导致最小冲突的散列键。

我首先尝试使用 Arrays.deepHashCode(int[][])，但很快就发现了冲突。其次，我尝试通过将 a[i] 和 b[i] 更改为新值来更平均地分配数组中的值，以便 a_new[i] = Math.pow(31,a[i]) % Math.pow(2,16) （实际上使用 BigInteger 来避免溢出：BigInteger.valueOf(31).modPow(BigInteger.valueOf(a[i]), BigInteger.valueOf(Math.pow(2,16)))；使用BigInteger。由于值的区间是有限的，我可以为每个可能的值预先计算它。结果我想出了以下解决方案：

    int result = 31;
    for (int i = 0; i < a.length; i++) {
        result = result * 31 * a_new[i];
        result = result * 31 * b_new[i];
    }

当只有较小的数组时，此解决方案似乎有效，但一旦 a[] 和 b[] 最多可包含 10 个值，它也会导致冲突。现在我想知道，是否有更好的方法来实现我想要的更少碰撞。

编辑：我将其修复为使用适当的 java 权力代码

Answer 1

也许您可以存储一个质数数组，并将数组中的当前数乘以 prime[i]，而不是将每个 a[i] 和 b[i] 乘以 31？

像这样：

int result = 31;
int[] primes = {3, 5, 7, 11, 13, 17, 19, 23, ... };
    for (int i = 0; i < a.length; i++) {
        result = result * primes[i % primes.length] * a_new[i]
        result = result * primes[i % primes.length] * b_new[i]
    }

您也可以尝试使用更大的素数来减少碰撞的可能性。

Answer 2

只是说明显而易见的...

return Objects.hash(a_new, b_new);

Answer 3

感谢所有回复和想法。最终，我想出了一个似乎对我有用的不同解决方案，到目前为止还没有导致任何冲突。

我决定创建两个不同的哈希，而不是为两个数组创建一个哈希。一个哈希基于数组中的整数集，另一个基于序列（与我的问题相同）。然后将两个哈希用作 MultiKeyMap (Apache Commons Collections 4.4 API) 中的键，我在其中存储连接到两个数组的数据。

基于序列的哈希：

    int result = 31;
    for (int i = 0; i < a.length; i++) {
        result = result * 31 * a_new[i];
        result = result * 31 * b_new[i];
    }

    return result;

基于集合的哈希：


    int resultA = 31;
    int resultB = 179;
    for (int i = 0; i < a.length; i++) {
        resultA += a_new[i];
        resultB += b_new[i];
    }

   return resultA *31 * resultB;

具有最小冲突的两个整数数组的哈希函数

Hash function for two integer arrays with minimal collisions

java

arrays

hash

hash-function

computation-theory