HashCode - What will happen if equal object happened to hash in the same bucket?

Question

I know this has been asked many times, but I can't find an exact answer to my question.

In chapter 3 of Effective Java, there is a scenario there that shows and explains why hashcode should be overriden together with the equals method. I get the most part of it but there is a part there that I can't understand.

There is a given class there that override the equals method but not the hashCode method. The object is put as a key in a map

Map<PhoneNumber, String> m = new HashMap<PhoneNumber, String>();
m.put(new PhoneNumber(707, 867, 5309), "Jenny");

I understand that if we get using another equal object (m.get(new PhoneNumber(707, 867, 5309))), it will return null simply because their hashcodes are not overriden to return equal value for equal objects (because it will search for the object in another bucket because of different hashcode).

But according to my understanding, in that situation, there is no guarantee that the hashcodes of the two objects will always return distinct. What if they happen to return the same hashcode?

I think it is explained in this part

Even if the two instances happen to hash to the same bucket, the get method will almost certainly return null, as HashMap has an optimization that caches the hash code associated with each entry and doesn’t bother checking for object equality if the hash codes don’t match.

I just don't get the cache thing. Can someone explain this elaborately?

Also, I already did my home work, and found a related question

Influence of HashMap optimization that caches the hash code associated with each entry to its get method

But I'm not that satisfied with the answer accepted, also, the answerer says in the comment that

A hash code can be an arbitrary int, thus each hash code can't have its own bucket. Consequently, some objects with different hash codes end up in the same bucket.

Which I completely disagree. To my understanding different hashcodes will never end up in the same bucket.

Evgeniy Dorofeev Evgeniy Dorofeev · Accepted Answer · 2013-04-19T03:54:38

Take a look at how java.util.HashMap calculates a bucket number for a key by hashCode:

/**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

If hashtable length = 16 then both 128 and 256 will get in bucket #0. Hashtable is an array of entries:

   Entry<K,V>[] table
   ...
   class Entry<K,V> {
           K key;
           V value;
           Entry<K,V> next;
           int hash;
    ...

Entries may form a chain (LinkedList). If bucket #0 (table[0]) is empty (null) then the new entry will be placed directly there, otherwise HashMap will find the last entry in the chain and set the last entry's next = new entry.

HashCode - What will happen if equal object happened to hash in the same bucket?

2 Answers