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

Question

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

也许不是将每个 a[i] 和 b[i] 都乘以 31，您可以存储一个素数数组，并将当前数字存储在数组中prime[i]?

像这样:

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]
    }

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