How HashMap retrieves different values if Key's hashcode is same but equals method return false

Question

I'm not able to understand on working pattern of HashMap. Kindly help to understand it.

Say we have two objects Obj1 and Obj2 having same Hashcode as 1212. Now when we run "==" and equals it returns false.

Now i use ValueObj1 and Valueobj2 as value in a HashMap with Keys Obj1 and Obj2 respectively. I believe both the values will be save in same bucket making as List.

My question how HashMap picks Valueobj2 for Obj2 and ValueObj1 for Obj1. Say there are n.. such objects and values. How this key--> value association works internally even though hashcode is same but values are different.

Assuming both condition equals is not overridden and overridden.

Answer 1

A HashMap/HashSet implements per bucket a list of keys (on the case of a Map together with the values). If multiple key's share the same hashCode value, they are placed in this list.

So the search method first extracts the hashCode of the queried key and then iterates over the corresponding list until an equals method succeeds. In case of a HashSet it means the key is found, in case of a HashMap, it returns the other side of the tuple: the value.

The memory of a HashMap thus works like:

+--------+--------+--------+--------+
|   00   |   01   |   10   |   11   |
+--------+--------+--------+--------+
    |        |        |        |
 k00/v00     _     k06/v06     _
    |                 |
 k08/v08           k14/v14
    |                 |
 k04/v04              _
    |
    _

What you see is on top the four buckets. Each bucket has a list (the items underneath), that stores tuples of keys (k) and values (v). Since there are here only four buckets, the hash algorithm uses a modulo 4 operation, so a key k06 with value v06 would be placed in bucket 06 mod 4 = 02 thus 10. In case a second key k14 is added with 14 mod 4 = 02 thus 10, it is simply added to the list.

Since the values are stored with it as well, one can perform a fast lookup operation. The key is thus stored together with the value.

You noticed, that iterating over the (linked) list is an expensive operation. But the point of a HashMap is that one hopes, that the number of hash-collisions to use the correct term (number of keys sharing the same bucket) is very low. In general one might expect two or three elements per bucket. The performance boost is thus achieved by selecting the correct bucket in constant time, searching the bucket requires however linear time (or in case there is a complete ordering on the key's, one might implement a (balanced) binary tree to search in logarithmic time). Worst-case however, a HashMap can achieve, the same performance as an ArrayList/LinkedList of entries, but given the hash-function has been designed decently, the odds are very low.