Java Hashmap tutorial

Java HashMap

HashMap is HashTable based implementation of Map. This is the reason why interviewer always ask for difference between HashMap and HashTable. HashMap is mostly equals to HashTable except below two differences.

  1. HashMap is unsynchronized while HashTable is synchronised.
  2. HashMap permits null while HashTable doesn’t.

Important Property of HashMap

DEFAULT_INITIAL_CAPACITY Default Initial Capacity(2 power n). Number of element HashMap can  contain.
MAXIMUM_CAPACITY Maximum Capacity of HashMap (2 power n).
LOADFACTOR Defines threshold of HashMap. When re-sizing will occur of HashMap.
DEFAULT_LOAD_FACTOR   Will be used when no load factor is defined in constructor of HashMap.
SIZE
 Number of key-value pair mapping, HashMap contains.

Creation of HashMap

When there is no parameter defined while creating HashMap default Initial Capacity(16) and Default load factor(0.75) will be used. This HashMap can contain up to 16 element and resizing of HashMap will occur when 13th element will be inserted. This is because load factor is 75%(.75) and this threshold will be crossed when you add 13th element(12+1).

You can also provide initial capacity and loadFactor. But initial capacity can not be more than maximum capacity (2 power 30) and load factor can not be zero or negative number.

Addition of element in HashMap

In order to add any element you need to provide 2 thing, key and value.

Key : key with which specified value will be associated. null is allowed.

Value : value to be associated with specified key.

First HashMap will generate hashcode for given key and then check if there is any value already associated with given key or not. If yes then it will return already associated value. Else it will add value in HashMap in with provided key.

Bullet Point

  1. HashMap doesn’t give any Guarantee in order of elements in Map(Means Order can change over time).
  2. HashMap provide Constant time performance for get & set operation(If proper Hashing algorithm is used).
  3. Time requires to Iterate collection is proportional to “Capacity“(Elements it can hold) & Size(Elements it is holding currently) of HashMap.
  4. In case iteration performance is more important then it is advisable to not set initial capacity too high and load factor too low. As performance is directly proportional to Initial Capacity and load Factor.
    • capacity is the number of buckets in the hash table.
    • initial capacity(Default Value is 16) is simply the capacity at the time the hash table is created.
    • The load factor(Default value .75) is a measure of how full the hash table is allowed to get before its capacity is automatically increased.
    • When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) .
  5. Use “Collections.synchronizedMap()” method to make Map synchronised.
  6. Iterators returned by HashMap class is “fail-fast“.
  7. HashMap is backed by an Array(Key) and LinkedList(Value).
  8. HashMap uses hashcode(Using Key) to identify exact location where object should be placed or retrieved in HashMap.
  9. In the end HashCode return the exact location(Index) in backing array.
  10. Backed Array have a fixed size. So whenever Array is full(Number of keys in this map reaches its threshold). A new Array with new capacity will be created and all element will be added to this new Array.
  11. HashCode will be used in both cases(Adding  and Retrieving Object) while equals() method may or may not be used in any case.
  12. Best candidate for Key in HashMap would be an Immutable Class with properly implement Equals and Hashcode method(Example: String Class).
  13. The better hashcode and equals method implementation is better performance of HashMap would be.
  14. In such way String and Wrapper classes of all Primitives will be great candidate for keys in HashMap.

What is ReHashing

Every HashMap has predefined size (Initial Capacity) and a logic to increment this size(Load Factor) whenever required(When threshold limit crossed).

Example :

Create HashMap with below configuration

Initial Capacity = 16 (Default Initial Capacity)

Load Factor : .75 (Default load factor)

Moment you add 13th element in given HashMap, Threshold limit is crossed for given HashMap and system will create a new backing keyset array(Size of this array will be double of previous array). System will have to again calculate exact bucket where elements from previous bucket should be placed and all elements from old HashMap will be copied to new HashMap. This whole process is called ReHashing because Hashcode is calculated for each element again.

Because overtime HashMap might be reHashed and order could get change.

Example of HashMap

Here in this example you will learn below points

  1. How to iterate a Map
  2. Different ways of iterating a Map
  3. When HashCode and Equals will get called. (Pay close attention to output of HashCode and equals method call)

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class HashMapExample {

	public static void main(String[] args) {

		Map<JBT, Integer> m1 = new HashMap<JBT, Integer>();

		JBT t1 = new JBT(1, 2);
		JBT t2 = new JBT(1, 3);
		JBT t3 = new JBT(2, 1);

		m1.put(t1, 1);
		m1.put(t2, 2);
		m1.put(t3, 3);
		System.out.println("Addition Done");

		/*
		 * Below you can find 3 different ways to iterate a Map. Uncomment
		 * different section and see the different in Output. Pay attention to
		 * when Hashcode and Equals is called
		 */

/*		Set s = m1.entrySet();
		for (Iterator i = s.iterator(); i.hasNext();) {
			Map.Entry me = (Map.Entry) i.next();
			System.out.println(me.getKey() + " : " + me.getValue());
		}
*/
/*		for (Map.Entry<JBT, Integer> entry : m1.entrySet()) {
			System.out.println("Key : " + entry.getKey() + " Value : "
					+ entry.getValue());
		}
*/
		for (Object key : m1.keySet()) {
			System.out.println("Key : " + key.toString() + " Value : "
					+ m1.get(key));
		}

	}
}

class JBT {
	JBT(int i, int j) {
		this.i = i;
		this.j = j;
	}

	int i, j;

	@Override
	public int hashCode() {
		System.out.println("Inside HashCode Method");
		int k = i + j;
		return k;
	}

	@Override
	public boolean equals(Object obj) {

		System.out.println("Inside Equals Method");
		if (i == ((JBT) obj).i && j == ((JBT) obj).j)
			return true;
		else
			return false;
	}

	@Override
	public String toString() {
		return String.valueOf(i).concat(String.valueOf(j));
	}

}
Series Navigation<< Collection in JavaInner Class >>
By | 2014-02-01T18:41:11+00:00 February 1st, 2014|Core Java|5 Comments

About the Author:

5 Comments

  1. Sujata Shroff August 25, 2014 at 10:04 am - Reply

    Thanks a ton Vivekanand. It is a very good work. Collection was the topic I used to think it is such a vast topic and thought I will never beable to grasp it. But you have made it so so so easy. Million thanks to you. You have helped me a lot. God bless you.

  2. Michael November 22, 2014 at 5:38 am - Reply

    Nice Post! Pls I stll dont understand these Points:

    1.HashMap is backed by an Array(Key) and LinkedList(Value).
    2.Iterators returned by HashMap class is “fail-fast“.

    3.When there is no parameter defined while creating HashMap default Initial Capacity(16) and Default load factor(0.75) will be used. This HashMap can contain up to 16 element and resizing of HashMap will occur when 13th element will be inserted. This is because load factor is 75%(.75) and this threshold will be crossed when you add 13th element(12+1).

  3. venkatesh December 12, 2014 at 5:06 am - Reply

    Thanks

  4. Omkar December 8, 2015 at 7:52 am - Reply

    Please add type arguments in the code…

Leave A Comment