hashCode uniqueness

Question

Is it possible for two instances of Object to have the same hashCode()?

In theory an object's hashCode is derived from its memory address, so all hashCodes should be unique, but what if objects are moved around during GC?

Answer 1

I think the docs for object's hashCode method state the answer.

"As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)"

Answer 2

Given a reasonable collection of objects, having two with the same hash code is quite likely. In the best case it becomes the birthday problem, with a clash with tens of thousands of objects. In practice objects a created with a relatively small pool of likely hash codes, and clashes can easily happen with merely thousands of objects.

Using memory address is just a way of obtaining a slightly random number. The Sun JDK source has a switch to enable use of a Secure Random Number Generator or a constant. I believe IBM (used to?) use a fast random number generator, but it was not at all secure. The mention in the docs of memory address appears to be of a historical nature (around a decade ago it was not unusual to have object handles with fixed locations).

Here's some code I wrote a few years ago to demonstrate clashes:

class HashClash {
    public static void main(String[] args) {
        final Object obj = new Object();
        final int target = obj.hashCode();
        Object clash;
        long ct = 0;
        do {
            clash = new Object();
            ++ct;
        } while (clash.hashCode() != target && ct<10L*1000*1000*1000L);
        if (clash.hashCode() == target) {
            System.out.println(ct+": "+obj+" - "+clash);
        } else {
            System.out.println("No clashes found");
        }
    }
}

RFE to clarify docs, because this comes up way too frequently: CR 6321873

Answer 3

Think about it. There are an infinite number of potential objects, and only 4 billion hash codes. Clearly, an infinity of potential objects share each hash code.

The Sun JVM either bases the Object hash code on a stable handle to the object or caches the initial hash code. Compaction during GC will not alter the hashCode(). Everything would break if it did.

Answer 4

Is it possible?

Yes.

Does it happen with any reasonable degree of frequency?

No.

Answer 5

I assume the original question is only about the hash codes generated by the default Object implementation. The fact is that hash codes must not be relied on for equality testing and are only used in some specific hash mapping operations (such as those implemented by the very useful HashMap implementation).

As such they have no need of being really unique - they only have to be unique enough to not generate a lot of clashes (which will render the HashMap implementation inefficient).

Also it is expected that when developer implement classes that are meant to be stored in HashMaps they will implement a hash code algorithm that has a low chance of clashes for objects of the same class (assuming you only store objects of the same class in application HashMaps), and knowing about the data makes it much easier to implement robust hashing.

Also see Ken's answer about equality necessitating identical hash codes.

Answer 6

Are you talking about the actual class Object or objects in general? You use both in the question. (And real-world apps generally don't create a lot of instances of Object)

For objects in general, it is common to write a class for which you want to override equals(); and if you do that, you must also override hashCode() so that two different instances of that class that are "equal" must also have the same hash code. You are likely to get a "duplicate" hash code in that case, among instances of the same class.

Also, when implementing hashCode() in different classes, they are often based on something in the object, so you end up with less "random" values, resulting in "duplicate" hash codes among instances of different classes (whether or not those objects are "equal").

In any real-world app, it is not unusual to find to different objects with the same hash code.

Answer 7

If there were as many hashcodes as memory addresses, then it would took the whole memory to store the hash itself. :-)

So, yes, the hash codes should sometimes happen to coincide.