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

Question

Java 方法，Arrays.hashCode() 或 Objects.hash() return 对于一些具有不同内容的整数数组，例如

相同的散列

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

相同的结果是由自定义哈希码方法 return 编辑的，例如：

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

没有办法满足您的要求

您必须了解散列函数不能创建双向映射。这就是您在这里需要的！

含义：存在（接近）无限数量的具有任意 int 值的数组。如果每个散列都应该唯一地指向一个特定的数组设置，您可以通过其散列来识别每个数组。但是 int（或 long）的范围不是无限的。 count 它们的数组组合可能比 int 值更多！

不能将不定集映射到非不定集。

换句话说：如果存在这样的散列方法，您可以将其转化为一种压缩算法，将任何内容缩减为单个 int 值。

因此：冲突是哈希算法固有的属性。你无法避免它们。如果有的话，您可以微调特定的哈希函数，以最大限度地减少特定输入数据集的冲突。但正如所说：从 conceptual/mathematical 的角度来看，你所要求的是不可能的。

Answer 2

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

你的问题下已经有几条评论说这不可能，我只是想补充一些你没有想过的有趣的东西（可能你根本不知道）。

一般来说，hash collisions 在 java 数据结构中的出现频率比您想象的要高得多。根据 Birthday problem and taking into consideration that a hash is actually 32 bits, we get to the fact that it would take only 77,164 unique values before there is a 50% chances to generate a collision (and that is in the best case). So collisions are more than fine. That being said, there is JEP 改进这一点（根据我的理解，首先制作散列 - long 然后处理它；但没有深入研究它）。

既然您知道散列冲突更有效，那么想想为什么要使用它们。基本上用于快速（呃）查找。当有两个具有相同 hash 的条目时，这意味着它们将以相同的 "bucket" 结尾，而在 java 中，那个桶是一个 完美平衡的红色- black tree（对于 HashMap，因此，HashSet）- 在查找条目时仍然非常快。因此，一般，任何基于散列的结构都有一个常数的搜索时间（即：摊销O(1)），所以不用担心关于哈希冲突。

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

Fastest way to calculate hash for Integer array without collision

java

arrays

integer

hashcode