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()?

Solution 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.

Solution 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.

Solution 3

Assuming that you're following the rules for defining hashCode and equals, the scenario you described will not result in loss of data. At most, performance will degrade over time.

Solution 4

In the Java hashmap they could use several ways to do it. From my old CS 201 Data Structures class back during the dark ages:

1) Each bucket in the hash map can become the head of a linked list holding all the entries added that have the same hash value. A collision on adding means you add the new entry to the end of the linked list. Search means you have to linearly check all the ones in any linked list once you hash into the bucket for it.

2) If a collision occurs and the store is conceptually an array, you can just iterate starting at that point until you find an empty spot and add the new entry there. For search this means if you find the hash bucket is occupied, then you have to compare linearly from that point to the next empty spot in the array that backs the hash map.

In both cases, the performance degrades if there are multiple entries with the same hash. In the general case, this means that a hash function (used to generate the hash code) returns a small number of possible values, performance will degrade as the map fills up. The Java HashMap has taken advantage of 50 years of research on such things to be a good fit to the general case of general data going into a hashed map.

Note @dystroy made a comment about the rule that you can't have two entries in the map with that match according to the equals() method.

Solution 5

In Java 8, they overhauled the implementation of HashMap. Now the hash buckets are organized as either linked lists or balanced binary trees, depending on:

• the hash array size, and / or
• the number of entries in a given bucket.

This means that you no longer get catastrophically bad performance in cases where many entries land in the same hash bucket.

For more information, read this blog post:

• Performance Improvement for HashMap in Java 8

View more solutions