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

Question

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

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

另外,有人告诉我,一个存储桶中只能有一个唯一的Hashcode,而具有相同哈希码的对象只能存储在一个存储桶中.我知道这与第一点相矛盾.咄!

根据我的记忆,我告诉他Java Hashcode合同说两个不同的对象可能有相同的hashcode().

根据我的采访者的说法,默认的object.hashcode()永远不会有两个不同对象的相同hashcode(),这是真的吗？

甚至可以编写一个演示此代码的代码.根据我的理解,Object.hashcode()可以产生2 ^ 30个唯一值,如何产生碰撞,具有如此低的碰撞可能性,以证明两个不同的对象可以使用Object类方法获得相同的hashcode().

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

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

Answer 1

2 ^ 30个唯一值听起来很多,但生日问题意味着我们不需要很多对象来进行碰撞.

以下程序在大约一秒钟内为我工作,并在对象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");
    }
}