Skip to main content

Posts

Showing posts from March, 2013

How does HashMap work in Java? (HashMap internals)

HashMaps are probably one of the most used and definitely one of the least understood Java classes. In this post let's look at the source code of HashMap.java to understand how is data inserted and retrieved from a HashMap.

We know that HashMaps work on the principle of 'hashing' and put(key, value) is used to store a key and corresponding value and get(key) is used to retrieve the value for given key.

Below image shows how HashMap stores the data. The blue squares represent the 'bucket' or indexes in the array, determined on the basis of hash value for each key. (We will see later, exactly how the hash value is calculated) At each index of the array, is stored a linked list which has nodes of the type 'Map.Entry'. Each node stores the key/value pair.


Why is the linked list needed? Because two unequal objects can have same hash value (read more about equals and hashcode here). Remember that a HashMap will store values as long as different keys are used so …