HashMap in Java

Reading time: 35 minutes | Coding time: 5 minutes

HashMap is an efficient and important data structure that stores a mapping between data with the speciality of constant time searching, retrival, insertion and deletion. It is an important member of the Java Collection data structure library and is used by us in many programming scenarios.

In Java, HashMap is a Map based collection class that is used for storing Key and value pairs which is denoted as HashMap<Key, Value>. It does not maintain order of elements and is similar to the Hashtable class except that it is unsynchronized and permits null values.

HashMap is a implementation of Java's Map interface.

The so called "Hash" actually is a technique of by using certain algorithm to convert an object to a string or list of code that uniquely (in the most of cases) exist in the world. HashMap stores data with entry<key, value> format.

• "key" here is a string or list of code generated by hash algorithms
• value is the associated input data

Points to note

1. HashMap does not allow dupicate key values. It means in a HashMap, all the key must be unique or the previous key-value will be replaced by new key-value entry.

2. Java allows one null key and mutiple null values exist in a HashMap.

3. HashMap is not thread-safe container. It means if there are mutiple threads using a HashMap at the same time, it will probably cause some errors like dirty read and phantom read.

4. The data stored in HashMap is unordered, it does not guarantee a specific order to store the elements.

5. Once you initialize a HashMap, the default size of this HashMap is 16 and the default load factor is 0.75. It means if there are more than 16 * 0.75 elements stored in this HashMap, the system will expand its size from 16 to 32.

Declear And Initialize a HashMap

Map<Integer, Integer> map = new HashMap<>();

Here I delear a Map with its key and value. The type of its key and value are Integer. Then, I initialize this map with HashMap constructure. So, the "map" here is an object of HashMap. I can also change the type of the key and value, like this:

Map<String, Integer> stringMap = new HashMap<>();

Popular Functions

• put(Object key, Object value): It is used to insert and entry into the map.

• get(Object key): The input value is key, and it will return a corresponding value from the HashMap.

• isEmpty(): It can be used to test whether a HashMap is empty or not. If the HashMap is empty, it will return "true". If the map is not empty, it will return false.

• remove(Object key): It is used to delete an entry with specifical key in the HashMap.

• containsKey(Object key): It will return "true" if there is a key has the same value with the input key in the HashMap. Or it will return false.

• containsValue(Object value): It will return "true" if the input value exists in the HashMap. Or it will return false.

Let's see the following codes:

	public static void main(String[] args) {
		//Declare a HashMap
		Map<Integer, String> hashMap = new HashMap<>();
		
		//call put function and add key-value element into this HashMap
		hashMap.put(1, "The key is 1");
		hashMap.put(2, "The key is 2");
		hashMap.put(3, "The key is 3");
		hashMap.put(4, "The key is 4");
		hashMap.put(5, "The key is 5");
		
		//out put all the element in the HashMap
		System.out.println(hashMap);
		
		
		//find and output an element in the hashMap with key=3;
		System.out.println(hashMap.get(3));
		
		//check if hashMap contains an element with key=100
		//if hashMap contains an element with key=100, output "hashMap has an element with key=100"
		//else output "can't find an element with key=100, add key=100 value="The key is 100" into hashMap"
		if(hashMap.containsKey(100)) {
			System.out.println("hashMap has an element with key=100");
		}else {
			System.out.println("can't find an element with key=100, add key=100 value=\"The key is 100\" into hashMap");
			hashMap.put(100, "The key is 100");
		} 
	}

The corresponding output of these codes are:
{1=The key is 1, 2=The key is 2, 3=The key is 3, 4=The key is 4, 5=The key is 5}
The key is 3
can't find an element with key=100, add key=100 value="The key is 100" into hashMap

Source Code analyze (JDK 1.7)

    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;
         }

As you can see, in JDK 1.7, when the system executing "put" function in HashMap, it will check if "key == null", if "key == null", then the system will create a element in HashMap with key equals to null. There might one element's key equals to null and mutiple element's value are null.

Then, it will re-generates the hashcode using hash(int h) method by passing user defined hashcode as an argument.

Based on the hash, it will generate a "i" which is the position in table[i]. The system use table[i] to store the corresponding element. "table" here is an Entry array.

Source Code analyze (JDK 10.0.2)

     final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 
                       boolean evict) { 
            Node<K,V>[] tab; Node<K,V> p; int n, i; 
            if ((tab = table) == null || (n = tab.length) == 0) 
                n = (tab = resize()).length; 
            if ((p = tab[i = (n - 1) & hash]) == null) 
                tab[i] = newNode(hash, key, value, null); 
            else { 
                Node<K,V> e; K k; 
                if (p.hash == hash && 
                    ((k = p.key) == key || (key != null && key.equals(k)))) 
                    e = p; 
                else if (p instanceof TreeNode) 
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 
                else { 
                    for (int binCount = 0; ; ++binCount) { 
                        if ((e = p.next) == null) { 
                            p.next = newNode(hash, key, value, null); 
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 
                                treeifyBin(tab, hash); 
                            break; 
                        } 
                        if (e.hash == hash && 
                            ((k = e.key) == key || (key != null && key.equals(k)))) 
                            break; 
                        p = e; 
                    } 
                } 
                if (e != null) { // existing mapping for key 
                    V oldValue = e.value; 
                    if (!onlyIfAbsent || oldValue == null) 
                        e.value = value; 
                    afterNodeAccess(e); 
                    return oldValue; 
                } 
            } 
            ++modCount; 
            if (++size > threshold) 
                resize(); 
            afterNodeInsertion(evict); 
            return null; 
        }

Comparison across JDK1.7, JDK1.8 and JDK10

Compare with JDK1.7, JDK1.8 and JDK10 have some huge improvements in HashMap such as:

• They use Node to represent each element in the HashMap.

• Java 8 hash elements use balanced trees rather than linked lists after a certain threshold is reached.

• The above point means HashMap starts with storing Entry objects in linked list but when the size of a hashmap becomes larger than a certain threshold, the hash will change from using a linked list to a balanced tree, which will improve the worst case performance from O(N) to O(log N).