为何Arrays.hashCode(int[])对不同数组返回相同哈希值？求替代方案

冲突原因 #

Arrays.hashCode(int[])采用线性累加的哈希计算逻辑，核心公式为：

result = 31 * result + element[i]

初始result为0，遍历数组元素依次累加计算。

你遇到的情况属于哈希碰撞，本质是两个数组满足31*a1 + b1 = 31*a2 + b2的等式：

• 数组[72,99]计算：31*72 + 99 = 2331
• 数组[73,68]计算：31*73 + 68 = 2331
  哈希碰撞是哈希函数的固有特性——哈希值输出空间有限（int类型最多2^32种可能），但输入的整数数组组合是无限的，必然存在不同输入对应相同哈希值的情况，而Arrays.hashCode的简单线性算法更容易触发这类碰撞。

可行替代方案 #

• 使用Arrays.deepHashCode(int[])：该方法基于数组内容计算哈希，对一维数组的计算逻辑更严谨，对多维数组会递归处理嵌套结构，能降低碰撞概率。
• 自定义哈希算法：结合元素索引或使用更大的质数乘数，进一步减少碰撞可能，示例代码：

  public static int customHashCode(int[] arr) {
      int result = 1;
      for (int i = 0; i < arr.length; i++) {
          result = result * 127 + (i + 1) * arr[i];
      }
      return result;
  }
  

• 复合哈希校验：同时计算多个不同哈希算法的结果，将其组合为复合哈希值，能大幅降低碰撞的概率。

内容的提问来源于stack exchange，提问作者Arno_Geismar