如何证明Object.hashCode()可以为Java中的两个不同对象生成相同的哈希码? [英] How do I prove that Object.hashCode() can produce same hash code for two different objects in Java?

问题描述

与采访者讨论了Java Hashmap的内部实现以及如果我们重写Employee< Emp_ID，Emp_Name>的HashCode()方法时其行为的行为.对象.

Had a discussion with an interviewer regarding internal implementation of Java Hashmaps and how it would behave if we override equals() but not the HashCode() method for an Employee<Emp_ID, Emp_Name> object.

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

I was told that hashCode for two different objects would never be the same for the default object.hashCode() implementation, unless we overrode the hashCode() ourselves.

据我所记得，我告诉他Java Hashcode契约说两个不同的对象可能"被拒绝".具有相同的hashcode()，而不是必须".

From what I remembered, I told him that Java Hashcode contracts says that two different objects "may" have the same hashcode() not that it "must".

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

According to my interviewer, the default object.hashcode() never returns the same hashcode() for two different objects, Is this true?

是否甚至可以远程编写代码来证明这一点.据我了解，Object.hashcode()可以产生2 ^ 30个唯一值，一个是如何产生冲突的，发生冲突的可能性如此之低，以证明两个不同的对象可以使用Object classes方法获得相同的hashcode().

Is it even remotely possible to write a code that demonstrates this. From what I understand, Object.hashcode() can produce 2^30 unique values, how does one produce a collision, with such low possibility of collision to demonstrate that two different objects can get the same hashcode() with the Object classes method.

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

Or is he right, with the default Object.HashCode() implementation, we will never have a collision i.e two different objects can never have the same HashCode. If so, why do so many java manuals don't explicitly say so.

如何编写一些代码来证明这一点?因为在进行演示时，我还可以证明哈希图中的存储桶可以包含不同的HashCodes(我试图向他展示调试器，在其中扩展了hashMap，但他告诉我这只是逻辑上的实现，而不是内部算法?)

How can I write some code to demonstrate this? Because on demonstrating this, I can also prove that a bucket in a hashmap can contain different HashCodes(I tried to show him the debugger where the hashMap was expanded but he told me that this is just logical Implementation and not the internal algo?)

推荐答案

2 ^ 30个唯一值听起来很多，但

2^30 unique values sounds like a lot but the birthday problem means we don't need many objects to get a collision.

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

The following program works for me in about a second and gives a collision between objects 196 and 121949. I suspect it will heavily depend on your system configuration, compiler version etc.

从 Hashable 类的实现中可以看到，每个人都被保证是唯一的，但仍然存在冲突.

As you can see from the implementation of the Hashable class, every one is guarenteed to be unique and yet there are still collisions.

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

这篇关于如何证明Object.hashCode()可以为Java中的两个不同对象生成相同的哈希码?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！