How HashMap works in Java

Learn how HashMap works internally in Java language. I am assuming that if you are interested in the internal working of HashMap, you already know the basics of HashMap. But if you are new to concept, follow official java docs. Here we will discuss hashmap internal implementation analysis.

Table of Contents

    1. Single statement answer
    2. What is Hashing?
    3. Entry class in HashMap
    4. How put() methods works internally?
    5. How get() methods works internally
    6. Key Notes
    7. [Update] Improvements in Java 8

1. Single statement answer

If anybody asks me to describe “How HashMap works?“, I simply answer: “On principle of Hashing“. As simple as it is. Now before answering it, one must be very sure to know at least basics of Hashing. Right??

2. What is Hashing?

Hashing in its simplest form, is a way to assigning a unique code for any variable/object after applying any formula/algorithm on its properties.

A true hash function must follow this rule –

“Hash function should return the same hash code each and every time when the function is applied on same or equal objects. In other words, two equal objects must produce the same hash code consistently.”

All objects in Java inherit a default implementation of hashCode() function defined in Object class. This function produces hash code by typically converting the internal address of the object into an integer, thus producing different hash codes for all different objects.

Read More : Working with hashCode and equals methods in java

3. Entry class in HashMap

A map by definition is : “An object that maps keys to values”. Very easy.. right?

So, there must be some mechanism in HashMap to store this key-value pair. The answer is YES. HashMap has an nested static class Entry, which looks like this:

static class Entry<K ,V> implements Map.Entry<K, V>
{
	final K key;
	V value;
	Entry<K ,V> next;
	final int hash;
	...//More code goes here
}

Surely Entry class has key and value mapping stored as attributes. key has been marked as final and two more fields are there: next and hash.

We will try to understand the need of these fields as we go forward.

4. How HashMap.put() methods works internally

Before going into put() method’s implementation, it is very important to learn that instances of Entry class are stored in an array. HashMap class defines this variable as:

/**
 * The table, resized as necessary. Length MUST Always be a power of two.
 */
transient Entry[] table;

Now look at code implementation of put() method:

/**
* Associates the specified value with the specified key in this map. If the
* map previously contained a mapping for the key, the old value is
* replaced.
*
* @param key
*            key with which the specified value is to be associated
* @param value
*            value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or <tt>null</tt>
*         if there was no mapping for <tt>key</tt>. (A <tt>null</tt> return
*         can also indicate that the map previously associated
*         <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
	if (key == null)
	return putForNullKey(value);
	int hash = hash(key.hashCode());
	int i = indexFor(hash, table.length);
	for (Entry<K , V> 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++;
	addEntry(hash, key, value, i);
	return null;
}

4.1. What put() method does

Let’s note down the internal working of put method in hashmap.

  1. First of all, the key object is checked for null. If the key is null, the value is stored in table[0] position. Because hashcode for null is always 0.
  2. Then on next step, a hash value is calculated using the key’s hash code by calling its hashCode() method. This hash value is used to calculate the index in the array for storing Entry object. JDK designers well assumed that there might be some poorly written hashCode() functions that can return very high or low hash code value. To solve this issue, they introduced another hash() function and passed the object’s hash code to this hash() function to bring hash value in the range of array index size.
  3. Now indexFor(hash, table.length) function is called to calculate exact index position for storing the Entry object.

4.2. How collisions are resolved

Here comes the main part. Now, as we know that two unequal objects can have the same hash code value, how two different objects will be stored in same array location called bucket.

The answer is LinkedList. If you remember, Entry class had an attribute "next". This attribute always points to the next object in the chain. This is exactly the behavior of LinkedList.

  1. So, in case of collision, Entry objects are stored in linked list form. When an Entry object needs to be stored in particular index, HashMap checks whether there is already an entry?? If there is no entry already present, the entry object is stored in this location.

    If there is already an object sitting on calculated index, its next attribute is checked. If it is null, and current entry object becomes next node in linkedlist. If next variable is not null, procedure is followed until next is evaluated as null.

  2. What if we add the another value object with same key as entered before. Logically, it should replace the old value. How it is done? Well, after determining the index position of Entry object, while iterating over linkedist on calculated index, HashMap calls equals method on key object for each entry object.

    All these entry objects in linkedlist will have similar hashcode but equals() method will test for true equality. If key.equals(k) will be true then both keys are treated as same key object. This will cause the replacing of value object inside entry object only.

    In this way, HashMap ensure the uniqueness of keys.

5. How HashMap.get() methods works internally?

Now we know how key-value pairs are stored in HashMap. Next big question is : what happens when an object is passed in get() method of HashMap? How the value object is determined?

Answer we already should know that the way key uniqueness is determined in put() method , same logic is applied in get() method also. The moment hashmap identify the exact match for the key object passed as an argument, it simply returns the value object stored in current Entry object.

If no match is found, get() method returns null.

/**
* Returns the value to which the specified key is mapped, or {@code null}
* if this map contains no mapping for the key.
*
* <p>
* More formally, if this map contains a mapping from a key {@code k} to a
* value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise it returns
* {@code null}. (There can be at most one such mapping.)
*
* </p><p>
* A return value of {@code null} does not <i>necessarily</i> indicate that
* the map contains no mapping for the key; it's also possible that the map
* explicitly maps the key to {@code null}. The {@link #containsKey
* containsKey} operation may be used to distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key) {
	if (key == null)
	return getForNullKey();
	int hash = hash(key.hashCode());
	for (Entry<K , V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
		Object k;
		if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
			return e.value;
	}
	return null;
}

Above code is same as put() method till if (e.hash == hash && ((k = e.key) == key || key.equals(k))), after this simply value object is returned.

6. Key notes on internal working of HashMap

  1. Data structure to store entry objects is an array named table of type Entry.
  2. A particular index location in array is referred as bucket, because it can hold the first element of a linkedlist of entry objects.
  3. Key object’s hashCode() is required to calculate the index location of Entry object.
  4. Key object’s equals() method is used to maintain uniqueness of keys in map.
  5. Value object’s hashCode() and equals() method are not used in HashMap’s get() and put() methods.
  6. Hash code for null keys is always zero, and such entry object is always stored in zero index in Entry[].

7. [Update] HashMap improvements in Java 8

As part of the work for JEP 180, there is a performance improvement for HashMap objects where there are lots of collisions in the keys by using balanced trees rather than linked lists to store map entries. The principal idea is that once the number of items in a hash bucket grows beyond a certain threshold, that bucket will switch from using a linked list of entries to a balanced tree. In the case of high hash collisions, this will improve worst-case performance from O(n) to O(log n).

Basically when a bucket becomes too big (currently: TREEIFY_THRESHOLD = 8), HashMap dynamically replaces it with an ad-hoc implementation of the treemap. This way rather than having pessimistic O(n) we get much better O(log n).

Bins (elements or nodes) of TreeNodes may be traversed and used like any others, but additionally support faster lookup when overpopulated. However, since the vast majority of bins in normal use are not overpopulated, checking for the existence of tree bins may be delayed in the course of table methods.

Tree bins (i.e., bins whose elements are all TreeNodes) are ordered primarily by hashCode, but in the case of ties, if two elements are of the same “class C implements Comparable<C>“, type then their compareTo() method is used for ordering.

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes. And when they become too small (due to removal or resizing) they are converted back to plain bins (currently: UNTREEIFY_THRESHOLD = 6). In usages with well-distributed user hashCodes, tree bins are rarely used.

So now we know how HashMap works internally in java 8.

I hope I have correctly communicated my thoughts by this article. If you find any difference or need any help at any point, please drop a comment.

Happy Learning !!

Leave a Reply

156 Comments
Most Voted
Newest Oldest
Inline Feedbacks
View all comments

About Us

HowToDoInJava provides tutorials and how-to guides on Java and related technologies.

It also shares the best practices, algorithms & solutions, and frequently asked interview questions.