无冲突计算整数数组散列的最快方法

Question

Java 方法 Arrays.hashCode() 或 Objects.hash() 为某些具有不同内容的整数数组返回相同的哈希值，例如

Integer[] a = {0,4,5,0}     // hash 927520
Integer[] b = {0,3,36,0}    // hash 927520

自定义哈希码方法返回相同的结果，例如：

public int hash(final Integer[] indexes) {
    final int prime = 31;
    int result = 1;
    for (Integer i : indexes) {
        result = prime * result + ((i == null) ? 0 : i.hashCode());
    }
    return result;
}

我同意这是预期的行为。但是，由于内容不同，我想为它们生成不同的哈希码。

在没有冲突的情况下计算整数数组哈希的最快方法是什么

Answer 1

问题有点不同。首先想想为什么需要hashCode以 = 开头来进行快速（呃）查找。拥有两个生成相同哈希值的对象根本不是问题，因为这并不意味着它们是相同的（当然，您仍然需要检查equals）。

您在问题下已经有一些评论，说这是不可能的，我只是想添加一些您没有想到的有趣的事情（可能您根本不知道它们）。

一般来说，hash collisions在 Java 数据结构中，它们的出现频率比您想象的要高得多。根据生日问题并考虑到 ahash实际上是32 bits，我们发现只需要 77,164 个唯一值就有机会50%生成碰撞（这是最好的情况）。所以碰撞是再好不过的了。话虽这么说，有JEP可以改进这一点（根据我的理解，首先制作哈希 - along并对其进行处理；但还没有深入研究它）。

既然您知道哈希冲突非常好，那么请考虑一下为什么使用它们。基本上是为了快速（呃）查找。当有两个条目具有相同的 时hash，这意味着它们将在同一个“桶”中结束，并且在 java 中，该桶是一个完美平衡的红黑树（对于HashMap，因此，HashSet） - 当查找时仍然非常快用于条目。因此，一般来说，任何基于哈希的结构都有一个恒定的搜索时间（即：摊销O(1)），因此不必担心哈希冲突。