Skip to main content

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 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 if those different keys result in same hash value they will reside at the same index in the table, in different nodes of the linked list.

Let's look at the default implementation of HashMap in Java.

       public V put(K key, V value) {
           if (key == null)
               return putForNullKey(value);
           int hash = hash(key.hashCode());
           int bucketIndex = (hash & (table.length-1));
           for (Entry e = table[i]; e != null; e = {
               Object k;
               if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                   V oldValue = e.value;
                   e.value = value;
                   return oldValue;
           Entry e = table[bucketIndex];
           table[bucketIndex] = new Entry<>(hash, key, value, e);

           return null;

       public V get(Object key) {
           if (key == null)
               return getForNullKey();
           int hash = hash(key.hashCode());
           int bucketIndex = (hash & (table.length-1));
           for (Entry e = table[bucketIndex]; e != null; e = {
               Object k;
               if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                   return e.value;
           return null;

       static int hash(int h) {
           // This function ensures that hashCodes that differ only by
           // constant multiples at each bit position have a bounded
           // number of collisions (approximately 8 at default load factor).
           h ^= (h >>> 20) ^ (h >>> 12);
           return h ^ (h >>> 7) ^ (h >>> 4);

Now let's analyze the code:

           int hash = hash(key.hashCode());
           int bucketIndex = (hash & (table.length-1));

('hash' function could be anything that ensures that hash value will be as unique as possible. You can implement your own HashMap with your own hash function. has got a different hash function.)

Note that get() and put() have lot of code in common because before putting any key/value pair it checks if it already exists. When you do get(key) the key is hashed and then bucketIndex is calculated using this hash value. The linkedList at this index will be traversed till a 'key' with matching hash value and also being  'equal' to the input parameter.

In above image K9, K19, K29 all give same hash value H9. So if you give get(K19), it will start traversing starting with K9. Same hashCode but "K9".equals("K19") is false, so it proceeds to "K19" where both conditions are satisfied.

Implementation of HashTable is similar except the fact that methods are synchronized.

A word about the keys. Immutable objects make best keys because this ensures that hash value will remain same when putting in the value and when retrieving it.String objects are the best because of this, also they implement equals and hashCode methods.

Once we understand, this seems so elementary!


Ashish Thakran said…
HashMap works on the principle of hashing. In order to understand the working of HashMap one has to understand hashing.
Below link can be useful to find out the algorithm to find duplicate or repeated elements in an array in java

How HashMap works in Java
vikas shukla said…
Very good post admin. Sufficient content is given here to understand every thing. For more information Please visit Java Internals
vikas shukla said…
Very good post admin. Sufficient content is given here to understand every thing. For more information Please visit Java Internals

Popular posts from this blog

How to upload to Google Cloud Storage buckets using CURL

Signed URLs are pretty nifty feature given by Google Cloud Platform to let anyone access your cloud storage (bucket or any file in the bucket) without need to sign in.

Official documentation gives step by step details as to how to read/write to the bucket using gsutil or through a program. This article will tell you how to upload a file to the bucket using curl so that any client which doesn't have cloud SDK installed can do this using a simple script. This command creates a signed PUT URL for your bucket. gsutil signurl -c 'text/plain' -m PUT serviceAccount.json gs://test_bucket_location
Here is my URL:…

File upload problem: UTF-8 encoding not honored when form has multipart/form-data

The problem that I was facing was something like this. I was using Apache Commons File Upload library to upload and download some file.

I had a form in which user can upload a file and another field 'name' in which she can give any name to the file being loaded.

When I submitted the form, the file was uploaded fine but the value in name field was garbled. I followed all the possible suggestions I found:

<%@page pageEncoding="UTF-8"%> set. <%@page contentType="text/html;charset=UTF-8"%gt; set after the first directive. <meta equiv="Content-Type" content="text/html;charset=UTF-8"> in the head. enctype="multipart/form-data" attribute in the form. accept-charset="UTF-8" attribute in the form.
in the Servlet:
before doing any operations on request object: request.setCharacterEncoding("UTF-8"); For accessing the value

FileItem item = (FileItem);

if (item.isFormField()) {

//For regular…

Uploading and Retrieving images on Google Cloud Storage

You would already be aware that there are multiple options given by Google Cloud Platform to store data. Here is Google documentation on when to use which option: Google recommends using Google Cloud Storage (GCS) to store static content like files/videos etc. There is something called 'Blobstore' as well which is also used to store such content but it is on the way to being deprecated. This page talks about using GCS to store images. Look at this page to understand basic requirements for setup of GCS. In the Cloud Store Browser below following buckets are already available. If you select any bucket, you would be able to see the objects created in it.  Here you can see the image file in the '' bucket. You won't be able to add/delete files or folder from the browser if you don't have proper access but through code (running with the service account) it should not be a problem. Objects on GCS are immutable so you can't edit an ob…