我如何证明Object.hashCode（）可以为Java中的两个不同的对象产生类似的哈希代码？ [英] How do I prove that Object.hashCode() can produce similar hash code for two different objects in Java?

问题描述

与面试官讨论了Java Hashmaps的内部实现，以及如果我们覆盖了一个Employee对象的equals（）而不是HashCode（）方法，它将如何工作。

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

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

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

此外，我被告知，一个桶只能有唯一的Hashcode，并且具有相同hashcode的对象进入一个桶。我知道矛盾的一点。 Duh！

Also, I was told that one bucket can only have unique Hashcode in it, and objects with same hashcodes went in one bucket. Which I know contradicts point one. Duh!

从我记得的，我告诉他说，Java Hashcode契约说两个不同的对象可能有相同的hashcode（）。

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

根据我的面试官，默认的object.hashcode（）对于两个不同的对象不会有相同的hashcode（），这是真的吗？

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

甚至可以编写一个演示这个代码。从我的理解，Object.hashcode（）可以产生2 ^ 30个唯一值，如何产生冲突，具有这么低的冲突的可能性，以证明两个不同的对象可以获得相同的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扩展，但他告诉我，这只是逻辑实现，而不是内部算法） / p>

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屋！