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 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 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 = e.next) {
               Object k;
               if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                   V oldValue = e.value;
                   e.value = value;
                   e.recordAccess(this);
                   return oldValue;
               }
           }
   
           modCount++;
           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 = e.next) {
               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. HashTable.java 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!


Comments

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

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) iter.next();

if (item.isFormField()) {

//For regular…

java.lang.IllegalArgumentException: Malformed \uxxxx encoding

I was getting this exception during build while running ant. Googling didn't help much and I was flummoxed because the same code was running fine till now.

My code reads a text file and does some operations on the basis of values read. It was only when I saw the text files I understood the error. I had copied the text in wordpad and saved it as .txt file. Wordpad had put lot of formatting information before and after the content. Also there was "\par" after every line, which was giving this error.

So moral of the story: if you get this exception check your properties file (or any other file that your code might be reading.)

Easiest way to print Timestamp in Java

Rather than using Calendar.getTime() we can use java.sql.Timestamp class to get the time stamp which gives date and time till millisecond precision.

System.out.println(new Timestamp(System.currentTimeMillis()));

Above will give you current timestamp in this format: 2010-07-27 16:37:45.39