我如何证明 Object.hashCode() 可以为 Java 中的两个不同对象生成相同的哈希码？

Question

与面试官讨论了 Java Hashmaps 的内部实现，以及如果我们重写 equals() 但不重写 Employee 对象。

有人告诉我，对于默认的 object.hashCode() 实现，两个不同对象的 hashCode 永远不会相同，除非我们自己覆盖 hashCode()。

根据我的记忆，我告诉他 Java Hashcode 合同说两个不同的对象“可能”具有相同的 hashcode() 而不是它“必须”。

据我的面试官说，默认的 object.hashcode() 永远不会 returns 两个不同的对象使用相同的 hashcode()，这是真的吗？

是否有可能编写一段代码来演示这一点。据我了解，Object.hashcode() 可以产生 2^30 个唯一值，一个人如何产生碰撞，碰撞的可能性如此之低，以证明两个不同的对象可以获得与对象相同的 hashcode() 类方法。

或者他是对的，使用默认的 Object.HashCode() 实现，我们永远不会发生冲突，即两个不同的对象永远不会有相同的 HashCode。如果是这样，为什么那么多 java 手册没有明确说明。

如何编写一些代码来演示这一点？因为在演示这一点时，我还可以证明 hashmap 中的桶可以包含不同的 HashCode（我试图向他展示扩展 hashMap 的调试器，但他告诉我这只是逻辑实现而不是内部算法？）

Answer 1

使用 Oracle JVM 并设置 -XX:hashCode=2。如果我没记错的话，这会将默认实现选择为 "constant 1"。只是为了证明你是对的。

Answer 2

如果您有足够大的堆（假设 64 位地址 space）并且对象足够小（64 位 JVM 上的最小对象大小为 8 字节），那么您将能够表示超过 2^32 个同时可达的对象。那时，对象的身份哈希码不能是唯一的。

但是，您不需要庞大的堆。如果你创建了一个足够大的对象池（例如在一个大数组中）并随机删除并重新创建它们，那么（我认为）保证你会发生哈希码冲突......如果你继续这样做足够长的时间。

旧版本 Java 中哈希码的默认算法是基于对象的地址 首次调用哈希码时 。如果垃圾收集器移动了一个对象，并且在第一个对象的原始地址创建了另一个对象，并调用了identityHashCode，那么这两个对象将具有相同的identity hashcode。
当前 (Java 8) 默认算法使用 PRNG。 "birthday paradox" 公式会告诉您一个对象的身份哈希码与另一个对象的身份哈希码相同的概率。

@BastianJ 提到的 -XXhashCode=n 选项具有以下行为：

hashCode == 0: Returns 新生成的伪随机数
hashCode == 1: 将对象地址与偶尔变化的伪随机数进行异或。
hashCode == 2: hashCode为1！（因此 @BastianJ 的 "cheat" 回答。）
hashCode == 3: hashcode是一个递增的序列号。
hashCode == 4:对象地址的低32位
hashCode >= 5：这是 Java8 的默认算法。它使用 Marsaglia 的 xor-shift PRNG 和线程特定的种子。

如果您下载了 OpenJDK Java 8 源代码，您将在 hotspot/src/share/vm/runtime/synchronizer.cp 中找到实现。寻找 get_next_hash() 方法。

所以这是另一种证明方式。给他看源代码！

Answer 3

2^30 个唯一值听起来很多，但 the birthday problem 意味着我们不需要很多对象就可以发生碰撞。

以下程序在大约一秒钟内为我工作，并在对象 196 和 121949 之间产生碰撞。我怀疑这在很大程度上取决于您的系统配置、编译器版本等。

从 Hashable class 的实现可以看出，每一个都保证是唯一的，但仍然存在冲突。

class HashCollider
{
    static class Hashable
    {
        private static int curr_id = 0;
        public  final  int id;

        Hashable()
        {
            id = curr_id++;
        }
    }

    public static void main(String[] args)
    {
        final int NUM_OBJS = 200000; // birthday problem suggests
                                     // this will be plenty

        Hashable objs[] = new Hashable[NUM_OBJS];  
        for (int i = 0; i < NUM_OBJS; ++i) objs[i] = new Hashable();

        for (int i = 0; i < NUM_OBJS; ++i)
        {
            for (int j = i + 1; j < NUM_OBJS; ++j)
            {
                if (objs[i].hashCode() == objs[j].hashCode())
                {
                    System.out.println("Objects with IDs " + objs[i].id
                                     + " and " + objs[j].id + " collided.");
                    System.exit(0);
                }
            }
        }

        System.out.println("No collision");
    }
}

Answer 4

除了一些代码高尔夫和统计数据外，我没有什么可以添加到 (+1)。

Wikipedia 文章关于Birthday problem that Michael linked to has a nice table 发生碰撞所需的事件数，在给定特定大小的值 space 的情况下具有所需的概率。例如，Java 的 hashCode 有 32 位，给出的值 space 为 40 亿。要获得 50% 的碰撞概率，大约需要 77,000 个事件。

这是查找具有相同 hashCode 的两个 Object 实例的简单方法：

static int findCollision() {
    Map<Integer,Object> map = new HashMap<>();
    Object n, o;

    do {
        n = new Object();
        o = map.put(n.hashCode(), n);
    } while (o == null);

    assert n != o && n.hashCode() == o.hashCode();
    return map.size() + 1;
}

这 returns 发生碰撞的尝试次数。我运行这很多次并生成了一些统计数据：

    System.out.println(
        IntStream.generate(HashCollisions::findCollision)
                 .limit(1000)
                 .summaryStatistics());

IntSummaryStatistics{count=1000, sum=59023718, min=635, average=59023.718000, max=167347}

这似乎与维基百科中的数字table非常吻合。顺便说一句，这在我的笔记本电脑上运行只用了大约 10 秒，所以这远非病态案例。

首先您是对的，但值得重复：哈希码不是唯一的！

我如何证明 Object.hashCode() 可以为 Java 中的两个不同对象生成相同的哈希码？

How do I prove that Object.hashCode() can produce same hash code for two different objects in Java?

java

algorithm

collections

hashcode