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

Question

我正在研究一个问题，我想在数据结构（例如，哈希表）中存储由两个相等长度的整数数组（例如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

也许不是将每个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]
    }

您也可以尝试使用较大的质数以减少碰撞的可能性。

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;