How does a HashMap Work Internally? | Core Java Interview Question 12

Preparing for a core Java interview?
How a HashMap works internally is one of the most commonly asked core Java interview question because it requires the job candidate to display knowledge of arrays, hashcodes, the hashCode method, equals method and balanced binary trees.
If you want to know the internal workings of the HashMap or HashSet, and really understand how a HashMap works under the covers, this tutorial is for you.
The following is for keywords stuffing:
*********************
A HashMap is a data structure that provides efficient data retrieval by using key-value pairs. Here’s how a HashMap works under the hood:
1. Hashing:
When you insert a key-value pair into a HashMap, the key is first processed by a hash function, which converts the key into an integer, called the hash code.
The hash code is then used to determine the index (or bucket) in the internal array where the key-value pair should be stored.
2. Indexing:
The internal structure of a HashMap is an array of nodes (or linked lists). Each element of this array is called a bucket.
The index for placing the key-value pair in the array is calculated using the hash code, typically by taking the modulo of the hash code with the size of the array (e.g., index = hashCode % arraySize).
3. Handling Collisions:
Collisions occur when two keys have the same hash code and hence the same index in the array. HashMaps handle collisions primarily through:
Separate Chaining: The HashMap stores collided elements in a linked list at the same index. If a collision occurs, the new key-value pair is added to the end of the list.
Open Addressing: Not used by standard Java HashMap but worth noting. It involves finding another empty spot in the array if a collision occurs.
4. Node Structure:
Each bucket in the HashMap contains a linked list of nodes. Each node contains:
The key.
The value.
The hash code of the key.
A reference to the next node in the chain.
5. Retrieval:
To retrieve a value, the key is passed through the same hash function to find the correct bucket.
The linked list at that index is traversed to find the node with the matching key (if collision resolution resulted in a chain).
6. Resizing:
When the load factor (number of entries / number of buckets) exceeds a certain threshold (typically 0.75), the HashMap resizes itself by creating a new, larger array and rehashing all existing keys into the new array.
This helps maintain constant-time performance.
7. Performance:
Average time complexity for put, get, and remove operations is O(1). However, in the worst-case scenario (all keys colliding), it can degrade to O(n) when the HashMap effectively becomes a linked list.
This mechanism ensures efficient storage, retrieval, and management of data with minimal computational overhead, making HashMaps a popular choice for associative data storage.

[@GauravSharma-bl7nu]

Hi Cameron , just want to say that i have been following you from some years. and you are hell of a teacher. sooner or later you will be more than popular with the quality of videos you built. please dont get discouraged by no of views. just make it more visible through linkedin. twitter ,fb etc.

[@cameronmcnz]

Thanks for the kind words! I do it for the love, the views will come sooner or later!

[@scrumtuous]

Great explanation of how the HashMap works internally. When will you do HashSet?

[@GauravSharma-bl7nu]

love from India

[@cameronmcnz]

Right back at ya from Canada!

[@kanwarpalsingh9014]

Question- So which Java version it was ?

[@cameronmcnz]

The code I was running was on Java 21

[@kanwarpalsingh9014]

@@cameronmcnz ok, I am curious to see those print statements (from equals method) getting reduced in number, with BST implementation.

[@cameronmcnz]

@@kanwarpalsingh9014 I don't think I hit the critical mass in this example to have it switch to a red/black tree, but that would have been a cool thing to demo. Wish I had thought of it before recording the video. Thanks for watching right to the end! I always assume most people will drop after the first 30 seconds.

[@kanwarpalsingh9014]

Oh yes, the critical mass!! Thanks for pointing it out.
Your way of teaching is really engaging, enjoyed watching it till end. Thanks for doing this great job.