How HashMap works in Java

HashMap works on principle of hashing (i.e. key-value pair is stored using hashCode value).

We have put() and get() method for storing and retrieving data from hashMap.

When we pass an both key and value to put() method to store it on hashMap, hashMap's implementation calls hashcode() method on that key object to identify a bucket location for storing the value object.

HashMap stores both key+value in the bucket. This is essential for the retrieving logic.

---

Note:

1. hasCode() of key is used to identify bucket.


2. Bucket is used to store "Key+Value" pair.


3. HashMap stores bucket in a linked list.

---

What will happen if two different HashMap key objects have same hashcode?
Collision Occurs

Since hashcode() is same, bucket location would be same and collision occurs in hashMap.

Since HashMap use a linked list to store in bucket, "Key and Value" object will be stored in next node of linked list.

---

Collision Resolution

We can find the bucket location by calling the hasCode function on the key object.

After finding bucket location, we will call keys.equals() method to identify correct node in linked list and return associated value object for that key in HashMap.

---

What happens to HashMap in Java if the size of the Hashmap exceeds a given threshold defined by load factor?

OR

What is re-hashing?

If the size of the map exceeds a given threshold defined by load-factor e.g. if load factor is 0.75, hashMap will act to re-size the map once it filled 75%.

Java Hashmap does that by creating another new bucket array of size twice of previous size of hashmap, and then start putting every old element into that new bucket array and this process is called rehashing because it also applies hash function to find new bucket location.

---

Race condition on HashMap in Java

Race condition exists while resizing hashmap in Java. If two threads, at the same time, find that Hashmap needs resizing, they both try resizing the hashMap.
In the process of resizing of hashmap, the element in bucket(which is stored in linked list) get reversed in order during the migration to new bucket, because java hashmap doesn't append the new element at tail, instead it appends the new element at head to avoid tail traversing.
If race condition happens then you will end up with an infinite loop.

---

Using immutable, final object with proper equals() and hashcode() implementation would act as perfect Java HashMap keys and improve performance of Java hashMap by reducing collision.
Immutability also allows caching the hashcode of different keys which makes overall retrieval process very fast and so String and various wrapper classes e.g Integer provided by Java Collection API can be very good HashMap keys.

---

In terms of usage HashMap is very versatile and mostly used as cache. For performance reasons, we need caching a lot, HashMap comes as very handy there.