Internal implementation of HashMap
This is one of the most commonly asked interview questions, “What is the Internal implementation of HashMap” OR “What are the data structures used in HashMap” OR “How HashMap maintains the uniqueness of keys”. In this tutorial, we will get answers for all these questions.
I have added the code snippets from HashMap.class file which is decompiled using jadclipe plugin. Check this blog for details.
Map Interface
First of all, lets see what does Map interface contains. Map interface has a inner interface named Entry which has following method definition.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
//Note : This source is generated from jadclipse plugin package java.util; public interface Map { public static interface Entry { public abstract Object getKey(); public abstract Object getValue(); public abstract Object setValue(Object obj); public abstract boolean equals(Object obj); public abstract int hashCode(); } public abstract int size(); public abstract boolean isEmpty(); public abstract boolean containsKey(Object obj); public abstract boolean containsValue(Object obj); public abstract Object get(Object obj); public abstract Object put(Object obj, Object obj1); public abstract Object remove(Object obj); public abstract void putAll(Map map); public abstract void clear(); public abstract Set keySet(); public abstract Collection values(); public abstract Set entrySet(); public abstract boolean equals(Object obj); public abstract int hashCode(); } |
As you can see, Map.Entry interface and five methods that needs to be implemented.
Map Implementation in HashMap
Lets have a look at HashMap class. In HashMap class, there is a static inner class named as “Entry” which implements the Map.Entry interface available in Map interface. Since HashMap implements Map, Map.Entry interface is also available for HashMap to implement its methods. Below code snippet shows the implementation of Map.Entry interface in a Entry class.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
... ... static class Entry implements Map.Entry { public final Object getKey() { return key; } public final Object getValue() { return value; } public final Object setValue(Object obj) { Object obj1 = value; value = obj; return obj1; } public final boolean equals(Object obj) { if(!(obj instanceof Map.Entry)) return false; Map.Entry entry = (Map.Entry)obj; Object obj1 = getKey(); Object obj2 = entry.getKey(); if(obj1 == obj2 || obj1 != null && obj1.equals(obj2)) { Object obj3 = getValue(); Object obj4 = entry.getValue(); if(obj3 == obj4 || obj3 != null && obj3.equals(obj4)) return true; } return false; } public final int hashCode() { return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()); } public final String toString() { return (new StringBuilder()).append(getKey()).append("=").append(getValue()).toString(); } void recordAccess(HashMap hashmap) { } void recordRemoval(HashMap hashmap) { } final Object key; Object value; Entry next; int hash; Entry(int i, Object obj, Object obj1, Entry entry) { value = obj1; next = entry; key = obj; hash = i; } } ... ... |
You can see, all the five methods are being implemented in the Entry class. There are three properties in this inner class – “key” and “value” of type Object, “next” of type Entry and “hash” of type int. Whenever new Entry object is created it consists for above four properties. Entry object is created via constructor –
|
1 2 3 4 5 6 7 |
Entry(int i, Object obj, Object obj1, Entry entry) { value = obj1; next = entry; key = obj; hash = i; } |
Whenever a HashMap object is created, it consists of an Array of Entry (Entry[]) and the variable name is “table”. Below is the snippet of declaration in HashMap class.
|
1 |
transient Entry table[]; |
By default, the HashMap object is created with the threshold value of 16 and with load-factor value of 0.75F. Please note, you can specify this value while creating hash map object. Below is the code snippet –
|
1 2 3 4 |
public HashMap() { this(16, 0.75F); } |
This internally calls the HashMap constructor with two parameters-
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public HashMap(int i, float f) { table = (Entry[])EMPTY_TABLE; hashSeed = 0; entrySet = null; if(i < 0) throw new IllegalArgumentException((new StringBuilder()).append("Illegal initial capacity: ").append(i).toString()); if(i > 1073741824) i = 1073741824; if(f <= 0.0F || Float.isNaN(f)) { throw new IllegalArgumentException((new StringBuilder()).append("Illegal load factor: ").append(f).toString()); } else { loadFactor = f; threshold = i; init(); return; } } |
You can see a table variable is initialized. Now lets see how does HashMap adds the element in it.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
public Object put(Object obj, Object obj1) { if(table == EMPTY_TABLE) inflateTable(threshold); if(obj == null) return putForNullKey(obj1); /* Generating the Hash Code */ int i = hash(obj); /*Generating the index position for adding the entry corresponding to specific location */ int j = indexFor(i, table.length); for(Entry entry = table[j]; entry != null; entry = entry.next) { Object obj2; if(entry.hash == i && ((obj2 = entry.key) == obj || obj.equals(obj2))) { Object obj3 = entry.value; entry.value = obj1; entry.recordAccess(this); return obj3; } } modCount++; addEntry(i, obj, obj1, j); return null; } |
As you can see in above implementation, Key and Value are passed as the parameters to “put” method, out of these only key is processed and it is compared with all the other keys in the table, see the for loop in the above code.
Before processing on key and values, hash code and index position is identified for the key value pair. Below are the methods for same-
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
final int hash(Object obj) { int i = hashSeed; if(0 != i && (obj instanceof String)) { return Hashing.stringHash32((String)obj); } else { i ^= obj.hashCode(); i ^= i >>> 20 ^ i >>> 12; return i ^ i >>> 7 ^ i >>> 4; } } static int indexFor(int i, int j) { return i & j - 1; } |
After identifying hashcode and index position the keys’ hashcode are compared and then the contents of keys’ are checked and “NO VALUES ARE COMPARED HERE“. If the key is null then it will send for processing at top, if the key is not null and no same key is present in the table array then it will add that key value pair in the table[]. See the below implementation of addEntry method which internally calls a createEntry method.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void addEntry(int i, Object obj, Object obj1, int j) { if(size >= threshold && null != table[j]) { resize(2 * table.length); i = null == obj ? 0 : hash(obj); j = indexFor(i, table.length); } createEntry(i, obj, obj1, j); } void createEntry(int i, Object obj, Object obj1, int j) { Entry entry = table[j]; table[j] = new Entry(i, obj, obj1, entry); size++; } |
For each key value pair a Entry object will be created and same will be added in table[] at specified location. Here specified location is the index position calculated in put method and along with key value data, hashcode is also passed to this method which will be set in the Entry object created for this new entry. Once the Entry object is created for new key and value pair, it will be added in the table[] and null will be returned from put method.
If the key is already present in the table[] then the value corresponding to that specific Entry will be updated with the new value and old value will be returned from put method. In this case new element is not added in the table[].
Lets see the simple example in debug mode and step wise execution of the flow. I have added step wise screenshot for each insertion of element in the hashmap. Take a loot at the “retValue” variable which will return the previous value if the key is already present else will return null in case the key is added for first time.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
package com.code2java; import java.util.HashMap; public class HashMapInternalImpl { public static void main(String[] args) { HashMap<String, String> hashMap = new HashMap<String, String>(); String retValue = ""; retValue = hashMap.put("Admin", "code2java"); System.out.println("Return Value : "+retValue); retValue = hashMap.put("admin", "code2java_1"); System.out.println("Return Value : "+retValue); retValue = hashMap.put("Admin", "code2java_2"); System.out.println("Return Value : "+retValue); retValue = hashMap.put("Admin", "code2java_3"); System.out.println("Return Value : "+retValue); retValue = hashMap.put("Admin", "code2java_4"); System.out.println("Return Value : "+retValue); retValue = hashMap.put("Admin", "code2java_5"); System.out.println("Return Value : "+retValue); retValue = hashMap.put("Admin", "code2java_6"); System.out.println("Return Value : "+retValue); System.out.println("HashMap size : "+hashMap.size()); } } |
Run the program in debug mode and go further pressing “F6”. You will see outputs like –
For the first time, new entry is created and is inserted in table. Since this is new key, retValue is null.
Second entry is also new, so it is added in table[] and now the length of table[] becomes 2.
Third entry contains the key that was already present in the table, so the value is modified and previous value is returned. Check the index position and the hashcode for this entry it is same that of first entry. The only change is in the value and everything else is same. Refer below screens for similar details.
In the remaining entries only value is changed and key, hashcode and index position remains same. This is internal implementation of hashmap and its working. Hope this will help.
Regards,
Nikhil Naoghare.