java HashMap collision

Question

I was reading about how hashmap works. I was reading through the "What will happen if two different objects have same hashcode".

According to it if two objects has same hashcode both will be stored in LinkedList but as far as I know if two hashcode then previous one will get overridden with new one(correct me if I am wrong).

Can someone please put more light on how hashmap use object as key internally and what will happen if two objects has same hashcode and how both objects will be fetched with get()?

Answer 1

No, the first one isn't overridden just because the second one has the same hashCode.

It will be overridden only if it is also equal (as said by equals). If not, both values will be kept in the linked list.

When fetching a key, all nodes with the same hashCode will be compared to the provided key until one is equal then its value will be returned (using the equals method).

If no key in the map is equal, you'll get null.

The only problem you have if many objects have the same hashCode (or more precisely the same hashCode modulo the size of the internal Entry[] table) is that the linked list will always be read, which is slower (and defeats the purpose of any hash table). That's why it's important when designing a hashcode method to ensure the generated integers are well distributed.

Answer 2

Let me explain working of hashmap.

Working of put method:

HashMap works on principle of hashing, we have put() and get() method for storing and retrieving object form HashMap. When we pass an both key and value to put() method to store on HashMap , it uses key object hashcode() method to calculate hashcode and they by applying hashing on that hashcode it identifies bucket location for storing value object. While retrieving it uses key object equals method to find out correct key value pair and return value object associated with that key. HashMap uses linked list in case of collision and object will be stored in next node of linked list. Also HashMap stores both key+value tuple in every node of linked list

Working of get method:

When we pass Key and Value object to put() method on Java HashMap, HashMap implementation calls hashCode method on Key object and applies returned hashcode into its own hashing function to find a bucket location for storing Entry object, important point to mention is that HashMap in Java stores both key and value object as Map.Entry in bucket. If more than one Entry object found in the bucket the it will call ke.equals method of each node in same bucket.