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

Question

与一位面试官讨论了 Java Hashmaps 的内部实现，以及如果我们为 Employee 对象覆盖 equals() 而不是 HashCode() 方法，它会如何表现。

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

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

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

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

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

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

Answer 1

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

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

正如您从 Hashable 类的实现中看到的那样，每一个都保证是唯一的，但仍然存在冲突。

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");
    }
}