0

您如何以一般（和高性能）的方式实现哈希码，同时最大限度地减少具有 2 个或更多整数的对象的冲突？

更新：正如许多人所说，你不能完全消除结肠（老实说没有考虑过）。所以我的问题应该是如何以适当的方式最小化碰撞，并进行编辑以反映这一点。

使用 NetBeans 的自动生成失败；例如：

public class HashCodeTest {
    @Test
    public void testHashCode() {
        int loopCount = 0;
        HashSet<Integer> hashSet = new HashSet<Integer>();
        for (int outer = 0; outer < 18; outer++) {
            for (int inner = 0; inner < 2; inner++) {
                loopCount++;
                hashSet.add(new SimpleClass(inner, outer).hashCode());
            }
        }
        org.junit.Assert.assertEquals(loopCount, hashSet.size());
    }

    private class SimpleClass {
        int int1;
        int int2;

        public SimpleClass(int int1, int int2) {
            this.int1 = int1;
            this.int2 = int2;
        }

        @Override
        public int hashCode() {
            int hash = 5;
            hash = 17 * hash + this.int1;
            hash = 17 * hash + this.int2;
            return hash;
        }
    }
}
4

5 回答 5

1

您能否以一般（和高性能）的方式为具有 2 个或更多整数的对象实现哈希码，而无需使用 colisions。

当散列到 32 位（一个整数）由超过 32 位（如 2 个或更多整数）组成的东西时，从技术上讲，零冲突是不可能的。

于 2012-04-05T18:57:55.347 回答
1

这是 eclipse 自动生成的：

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + getOuterType().hashCode();
    result = prime * result + int1;
    result = prime * result + int2;
    return result;
}

使用此代码，您的测试用例通过...

PS：别忘了实施equals()！

于 2012-04-05T19:01:31.680 回答
0

没有办法完全消除哈希冲突。您的方法基本上是减少冲突的首选方法。

于 2012-04-05T18:57:08.237 回答
0

创建零冲突的哈希方法是不可能的。散列方法的想法是您正在获取大量对象并将其映射到一组较小的整数。您能做的最好的事情就是尽量减少您在对象子集中遇到的碰撞次数。

于 2012-04-05T18:58:18.923 回答
0

正如其他人所说，减少碰撞比消除碰撞更重要——特别是因为你没有说你的目标是多少桶。与 2 个桶中有 5 个项目相比，1000 个桶中有 5 个项目的零碰撞要容易得多！即使有很多存储桶，1000 个存储桶与 1001 个存储桶的碰撞看起来也会大不相同。

需要注意的另一件事是，您提供的哈希很有可能甚至不是 HashMap 最终使用的哈希。例如，如果您查看OpenJDK HashMap 代码，您会看到您的密钥的 hashCodes 是通过一个私有hash方法（该链接中的第 264 行）放置的，该方法重新对它们进行哈希处理。因此，如果您在创建一个精心构建的自定义哈希函数以减少冲突（而不仅仅是一个简单的、自动生成的）时遇到麻烦，请确保您还了解谁将使用它以及如何使用它。

于 2012-04-05T19:43:59.893 回答