两个整数数组的哈希函数如何最小化碰撞？

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代码来计算幂次。

- Christian

---

这不是真正的Java。在Java中没有“mod”运算符，而且...不清楚你所说的“^”是指指数运算还是按位或运算？请向我们展示你实际使用的代码。 - Stephen C

@stephen C：我想它代表的是“幂运算”的“力量”，而不是双星号。如果是这样，那么结果int会溢出。应该使用long而不是int(eger)。 - user2670200

@StephenC：我修复了代码，使用了实际的Java代码。是的，我使用了“power of”与BigInteger结合来处理大幂次结果的模数。 - Christian

你能澄清一下你认为哪些类型的对象是等价的吗？ - McKay M

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

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

- McKay M

---

我非常喜欢那个想法，并尝试使用数组中的不同质数（例如从31开始），并同时使用我的数组的修改值和原始值。虽然比Objects.hash表现更好，但不幸的是，它在一段时间后也会导致冲突。 - Christian

Answer 2

只是陈述显而易见的事实...

return Objects.hash(a_new, b_new);

- Bohemian

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;

- Christian