Explanation:
HashMap class is from java.util package and it implements the Map interface in Java. HashMap is used to store data in the form of key-value pairs. Below is the hierarchy of the HashMap class.
HashMap is basically an array of buckets where every bucket can store a node or a list of nodes (where nodes have same hashcodes). A node consist of a key, a value, the hash code and the reference to the next node in the list if any exists. HashMap uses a technique known as Hashing to calculate the hashcode. Hashing is a process of converting an object to an integer which represents the same object. The main advantage of using hashing is it improves the search speed and helps in indexing.
Hashing is used to calculate the hashcode and also the index at which the node will be stored in the hashmap.
Important points about HashMap:
- HashMap also implements Cloneable and Serializable interfaces.
- It does not allow duplicate keys to be stored but allows duplicate values.
- Keys stored inside hash map should be unique and hence it allows one null key but allows multiple null values.
- The order in which the key-value pairs are inserted is not guaranteed.
- HashMap is unsynchronized i.e. it is not thread safe.
Internal structure of HashMap:
Every node in the hashmap can be represented as a node shown below.<K,V> indicates the key and the value stored as a node in hash map. hashVal is the hash code calculated and next is the reference to the next node in the list present in a bucket.
Terms related to HashMap implementation:
- Initial capacity: Initial capacity defines the number of nodes or the number of key-value pairs a hashmap can store when it is first created. The default initial capacity is 16.
- Load factor: Load factor is % value of capacity after which the capacity of the hash map is increased. Default value of load factor is 0.75 which is 75% of the capacity. It means after 75% of the hashmap is filled the capacity of the hashmap is increased (which is known as re-hashing).
- Threshold: It is the product value of initial capacity and load factor i.e 16*0.75=12. Threshold value of 12 means re-hashing takes place after 12 key-value pairs are inserted in the hashmap.
- Re-hashing: It is the process in which the capacity of the hashmap is doubled after the size of the hashmap reaches the threshold value. For example, if the initial capacity is 16, then after inserting 12 key value pairs (which is the threshold value) the capacity of the hashmap becomes 32. Now, when the capacity is 32, the threshold value will be 32*0.75=24. Then after 24 key-value pairs are inserted re-hashing takes place and again the capacity is doubled i.e. 64 and so on.
Different hashmap constructors:
- HashMap(): This creates a hashmap with default capacity of 16 and a default load factor of 0.75.
- HashMap(int initialCapacity): This creates a hashmap of specified initial capacity and default load factor 0.75.
- HashMap(int initialCapacity, float loadFactor): This creates a hashmap of specified initial capacity and specified load factor.
- HashMap(Map m): This creates a hashmap same as that of map passed to the constructor. The created hashmap will have same initial capacity and load factor as that of map m.
Code implementation:
public class HashMapDemo {
public static void main(String[] args) {
// hashmap with default capacity 16 and default load factor 0.75
Map<Integer, String> map1 = new HashMap<Integer, String>();
// put method used to add a key-value pair to the map
map1.put(1, "hetal");
map1.put(2, "rachh");
map1.put(3, "hetal rachh");
map1.put(null, "key is null");
map1.put(4, null);
map1.put(5, null);
System.out.println("**** Map1 contents are ****");
// print the map
map1.entrySet()
.forEach(entry -> System.out.println("Key = " +
entry.getKey() + " Value = " + entry.getValue()));
// get the number of elements present in the map
System.out.println("Size of map1 = " + map1.size());
// get the value based on the key
System.out.println("Value with key 3 = " + map1.get(3));
// hashmap with initial capacity 20 and default load factor 0.75
Map<Integer, String> map2 = new HashMap<Integer, String>(20);
map2.put(11, "hetal");
map2.put(22, "rachh");
map2.put(33, "hetal rachh");
System.out.println();
System.out.println("**** Map2 contents are ****");
// iterate over the map using entrySet()
for (Map.Entry<Integer, String> e : map2.entrySet()) {
System.out.println("Key = " + e.getKey() + " Value = " +
e.getValue());
}
System.out.println();
// remove entry with key=11
map2.remove(11);
System.out.println("**** Map2 contents are after removing entry with
key=11 ****");
for (Map.Entry<Integer, String> e : map2.entrySet()) {
System.out.println("Key = " + e.getKey() + " Value = " +
e.getValue());
}
// containsKey is used to check if the map2 contains an entry with
// key=33
if (map2.containsKey(33)) {
System.out.println("Value with key=33 is " + map2.get(33));
}
// getOrDefault method returns the default value specified if the key
// passed is not found in map
System.out.println("Value returned for key=11 is " + map2.getOrDefault(11,
"Default value"));
System.out.println();
// hashmap with default capacity 5 and load factor 0.5
Map<Integer, String> map3 = new HashMap<Integer, String>(5, 0.5f);
map3.put(1, "hetal");
map3.put(2, "rachh");
// capacity is doubled when 3rd element is put in the map (i.e. when the
// size reaches to 50% of capacity)
map3.put(3, "hetal rachh");
System.out.println("**** Map3 contents are ****");
map3.entrySet()
.forEach(entry -> System.out.println("Key = " +
entry.getKey() + " Value = " + entry.getValue()));
// isEmpty is used to check if the map is empty or not
System.out.println("Is map3 empty = " + map3.isEmpty());
// clear map map3
map3.clear();
System.out.println("Is map3 empty after calling clear() = " +
map3.isEmpty());
System.out.println();
Map<String, String> temp = new HashMap<String, String>();
temp.put("key1", "value1");
temp.put("key2", "value2");
temp.put("key3", "value3");
temp.put("key4", "value3");
// hashmap with default capacity and load factor as of temp map
Map<String, String> map4 = new HashMap<String, String>(temp);
System.out.println("**** Map4 contents are ****");
map4.keySet().forEach(key -> System.out.println("Key = " + key + " Value =
" + map4.get(key)));
// containsValue is used to check if one or more key is mapped to this
// value
System.out.println("map4 containsValue value3 = " + temp.containsValue("value3"));
}
}
Code output:
**** Map1 contents are ****
Key = null Value = key is null
Key = 1 Value = hetal
Key = 2 Value = rachh
Key = 3 Value = hetal rachh
Key = 4 Value = null
Key = 5 Value = null
Size of map1 = 6
Value with key 3 = hetal rachh
**** Map2 contents are ****
Key = 33 Value = hetal rachh
Key = 11 Value = hetal
Key = 22 Value = rachh
**** Map2 contents are after removing entry with key=11 ****
Key = 33 Value = hetal rachh
Key = 22 Value = rachh
Value with key=33 is hetal rachh
Value returned for key=11 is Default value
**** Map3 contents are ****
Key = 1 Value = hetal
Key = 2 Value = rachh
Key = 3 Value = hetal rachh
Is map3 empty = false
Is map3 empty after calling clear() = true
**** Map4 contents are ****
Key = key1 Value = value1
Key = key2 Value = value2
Key = key3 Value = value3
Key = key4 Value = value3
map4 containsValue value3 = true
Performance complexity of Hashmap:
Time complexity of ‘get’ and ‘put’ operations in hashmap has constant time complexity O(1), if the function to calculate the hash is coded properly and the buckets are distributed evenly across the hashmap.
In the worst case scenario i.e when multiple nodes are present in the same bucket, ‘get’ operation can have O(n) time complexity since it will require iterating over all the nodes in the bucket (having the same hash code).
Here is the link to the above code on my github profile, HashMap in Java.
I hope this post helped you to understand the basics of Hashmap. In the next post I will be discussing the internal working of hashmap and the applications of hashmap. Stay tuned..
Data structures and algorithms in Java 