INTRODUCTION
In Java, you might have heard about the Map interface (which extends the Collection Interface). There are some implementation classes of map interface, out of which one such class is HashMap (present in java. util package). It is denoted as HashMap<K, V> where K stands for Key and V for value. In simpler terms, HashMap<K, V> is a data structure that stores elements in the form of a key-value pair. These key-value pairs are also termed as an Entry of HashMap. Keys are unique, and duplicate keys are not allowed. It stores values based on keys, and it can be accessed using keys. Hashmap allows multiple null values and only one null key.
HashMaps are non-synchronized, meaning that they are not thread-safe. If multiple threads access the hashmap at the same time, they will modify the map structurally. HashMaps are an unordered collection of key-value pairs. They do not maintain the insertion order. They are much faster in terms of retrieving data as compared to arrays and linked-list, with constant time performance for the basic operations. Its initial default capacity(number of elements that can be stored) of hashmap is 16, and the default load factor is 0.75. We will discuss the capacity and load factor a little later in the coming sections.
HIERARCHY
Check the hierarchy diagram above; the HashMap class extends the AbstractMap class and implements the Map, Serializable and Cloneable interfaces.
Check the hierarchy diagram above; the HashMap class extends the AbstractMap class and implements the Map, Serializable and Cloneable interfaces.
Declaration of Hashmap class :
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
K: type of Key
V: type of Value
Also check Java Tutorial for Beginners | An Overview of Java.
CONSTRUCTORS IN HASHMAP
There are four constructors of the hashmap, all of which have public access specifiers.
1. Hashmap()
It is the default constructor that creates an instance of a hashmap with the initial capacity of
16 and load factor 0.75.
HashMap<K,V> hm = new HashMap<K,V>(); // instance creation
Program to demonstrate default Hashmap Constructor :
import java.io.*;
import java.util.*;
public class Hashmap{
public static void main(String args[]) {
HashMap<String, Integer> hm = new HashMap<String, Integer>();
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
}
}
Output : {Red=1, Blue=2, Yellow=4, Green=3} [order of insertion is not preserved]
2. HashMap(int initialCapacity)
This constructor creates an instance of a hashmap with the specified initial capacity and
default load factor 0.75.
HashMap<K,V> hm = new HashMap<K,V>(int initialCapacity); // instance creation
Program to demonstrate above Hashmap Constructor :
import java.io.*;
import java.util.*;
public class Hashmap{
public static void main(String args[]) {
HashMap<String, Integer> hm = new HashMap<String, Integer>(5);
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
}
} Output : {Red=1, Blue=2, Yellow=4, Green=3}
3. HashMap(int initialCapacity, float loadFactor)
This constructor creates an instance of a hashmap with the specified initial capacity and the
specified load factor.
HashMap<K,V> hm = new HashMap<K,V>(int initialcapacity, float loadfactor);
Program to demonstrate above Hashmap Constructor :
import java.io.*;
import java.util.*;
public class Hashmap {
public static void main(String args[]) {
HashMap<String, Integer> hm = new HashMap<String, Integer>(5,0.75f);
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
}
}
Output :
{Red=1, Blue=2, Yellow=4, Green=3}
4. HashMap(Map map)
This constructor creates an instance of a hashmap with similar mappings as the given Map.
HashMap<K,V> hm = new HashMap<K,V>(Map m); //instance creation
Program to demonstrate above Hashmap Constructor :
import java.io.*;
import java.util.*;
public class Hashmap {
public static void main(String args[]) {
Map<String, Integer> hm = new HashMap<String, Integer>();
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
HashMap<String, Integer> hm1 = new HashMap<String, Integer>(hm);
System.out.println(hm1);
}
}
Output :
{Red=1, Blue=2, Yellow=4, Green=3}
{Red=1, Blue=2, Yellow=4, Green=3}
OPERATIONS OF HASHMAP
The hashmap includes basic operations like add, get, update and delete the elements, just like any other data structure. Following are the basic operations :
1. Add Elements
To insert the elements or an entry in a Hashmap, the put(K, V) method is used.
K: type of key
V: type of value
Program to demonstrate put method :
import java.io.*;
import java.util.*;
public class Hashmap {
public static void main(String args[]) {
Map<String, Integer> hm = new HashMap<String, Integer>();
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
}
}
Output :
{Red=1, Blue=2, Yellow=4, Green=3}
2. Remove Elements
The remove(K) method takes the key as the argument and deletes the entry for the given key if it is present on the map. We also have one more remove(K, V) method to delete the entry.
Program to demonstrate remove operation using remove ():
import java.io.*;
import java.util.*;
public class Hashmap {
public static void main(String args[]) {
Map<String, Integer> hm = new HashMap<String, Integer>();
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
hm.remove("Blue"); //remove Blue key
System.out.println(hm);
}
}
Output :
{Red=1, Blue=2, Yellow=4, Green=3}
{Red=1, Yellow=4, Green=3}
remove(K, V): This method takes key and value as the argument and removes the entry only if both the key and value match.
Program to remove the entry using remove(K, V) :
import java.io.*;
import java.util.*;
public class Hashmap {
public static void main(String args[]) {
Map<String, Integer> hm = new HashMap<String, Integer>();
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
hm.remove("Blue",3);
System.out.println(hm);;
hm.remove("Blue",2);
System.out.println(hm);
}
}
Output :
{Red=1, Blue=2, Yellow=4, Green=3}
{Red=1, Blue=2, Yellow=4, Green=3}
{Red=1, Yellow=4, Green=3}
3. Access elements and Traverse hashmap
3.1 Access one particular value associated with a key using get(K)
The value present in a hashmap can be accessed using the method get(K). The key must be passed in the argument, and the value stored in that key will be fetched.
Program to access the value using the get(K) method:
import java.io.*;
import java.util.*;
public class Hashmap{
public static void main(String args[]) {
HashMap<String, Integer> hm = new HashMap<String, Integer>();
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
System.out.println(hm.get("Green"));
}
}
Output :
{Red=1, Blue=2, Yellow=4, Green=3}
3
3.2 Access only the keys of elements
If you want to retrieve only the set of keys, the keySet() method will return just the set of keys in hashmaps.
Program to show usage of method keySet():
import java.io.*;
import java.util.*;
public class Hashmap{
public static void main(String args[]) {
HashMap<String, Integer> hm = new HashMap<String, Integer>();
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
System.out.println(hm.keySet());
}
}
Output :
{Red=1, Blue=2, Yellow=4, Green=3}
[Red, Blue, Yellow, Green]
3.3 Access only the values of elements
The values() method helps to obtain the set of values.
Program to show usage of values() :
import java.io.*;
import java.util.*;
public class Hashmap{
public static void main(String args[]) {
HashMap<String, Integer> hm = new HashMap<String, Integer>();
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
System.out.println(hm.values());
}
}
Output :
{Red=1, Blue=2, Yellow=4, Green=3}
[1, 2, 4, 3]
3.4 Access the entries of HashMap
The entrySet() method will return the set of entries(<K, V>) in a hashmap.
Program to show usage of entrySet() :
import java.io.*;
import java.util.*;
public class Hashmap{
public static void main(String args[]) {
HashMap<String, Integer> hm = new HashMap<String, Integer>();
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
System.out.println(hm.entrySet());
}
}
Output :
{Red=1, Blue=2, Yellow=4, Green=3}
[Red=1, Blue=2, Yellow=4, Green=3]
3.5 Traverse the HashMap
After knowing how to access the elements in a hashmap, let us see how to iterate or traverse the hashmap. The idea is to iterate over the set of entries using the for-each loop and then access the key and values in an entry using the getKey() and getValue() methods. We use Map.Entry(K, V) that allows us to access the entries of a map.
Program to traverse the entries of a hashmap :
import java.io.*;
import java.util.*;
public class Hashmap{
public static void main(String args[]) {
HashMap<String, Integer> hm = new HashMap<String, Integer>();
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
for(Map.Entry<String, Integer> e: hm.entrySet())
{
System.out.println(e.getKey()+","+e.getValue());
}
}
}
Output :
{Red=1, Blue=2, Yellow=4, Green=3}
Red,1
Blue,2
Yellow,4
Green,3
4. Update the value
If you want to update the value stored in a given key, you can either use put(K, V) or
replace() method.
Program to update the value using put():
import java.io.*;
import java.util.*;
public class Hashmap{
public static void main(String args[]) {
HashMap<String, Integer> hm = new HashMap<String, Integer>();
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
hm.put("Yellow",5); //updates the value of key Yellow
System.out.println(hm);
}
}
Output :
{Red=1, Blue=2, Yellow=4, Green=3}
{Red=1, Blue=2, Yellow=5, Green=3}
Program to update using replace(K,V):
import java.io.*;
import java.util.*;
public class Hashmap{
public static void main(String args[]) {
HashMap<String, Integer> hm = new HashMap<String, Integer>();
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
hm.replace("Yellow",6);
System.out.println(hm);
}
}
Output :
{Red=1, Blue=2, Yellow=4, Green=3}
{Red=1, Blue=2, Yellow=6, Green=3}
FEATURES OF HASHMAP
Hashmap is a Map-based collection class that contains the values based on a key. Let us discuss some key features of it :
- It is an unordered collection; that is to say, it does not maintain the keys and values in the same order in which they were inserted.
- It cannot have duplicate keys; however, it can have duplicate values.
- It allows one null key and multiple null values.
- HashMap uses an inner class Entry<K, V> to store data in nodes of a multiple singly linked list.
- Its initial default capacity is 16, and its load factor is 0.75
- They are not synchronised (not thread-safe) as multiple threads can modify their structure when accessing it. So, we must externally synchronise these concurrent modifications. We can use Collections.synchronizedMap(Hashmap) to synchronise it.
- It makes use of a technique called Hashing to transform a key into a shorter hash key which makes it easier to insert and retrieve data from a hashmap. We will learn about the working of Hashmap in detail in the coming sections.
INTERNAL STRUCTURE OF HASHMAP
Considering the internal structure of the hashmap, it has a Node<K, V> which represents the inner class Entry<K, V> that stores the mappings of the hashmap. Each key-value pair is stored in an object of Entry<K, V> class. This class is a static inner class of Hashmap. Each node has four fields in it, namely :
- Hash key (shorter key obtained post hashing)
- Key
- Value
- Node next (a reference to another Entry, just like a singly linked list)
Points to know about a node in a HashMap:
- The hash attribute stores the hashcode of the key.
- The Key attribute stores the key, and it is of final type.
- Value attribute holds the value of the element.
- Entry<K, V> next holds the pointer to the next key-value pair.
Declaration of inner class Entry<K,V> :
static class Entry<K,V> implements Map.Entry<K,V>{
int hash;
final K key;
V value;
Entry<K,V> next;
}
Concept of Buckets in HashMap
Buckets are the array of nodes or entries that store elements. Many nodes can have similar buckets. The hashmap stores the elements just like a singly linked list, and a list of entries are termed as Buckets. These nodes are connected through a linked list. The capacity of hashmap and the number of buckets have a relation :
The Capacity of HashMap = Number of buckets * Load factor
Structure of hashmap
Internal Working of a HashMap
Hashmap uses a technique called Hashing. It is a process to convert a given key into a hash-key using the hashCode() method. Hashing also involves the equals() method to check if the keys are equal. Hashing is used to index and retrieve items faster. The performance of a hashmap is based on the hashcode() method, so this method should be carefully chosen. Let us discuss the hashCode and equals method below.
1. hashCode(): This method generates the hashcode of an object and returns the memory reference of the object passed in the integer form. It returns a random integer unique to each instance. The result of this method is termed a hash.
Syntax: public int hashCode()
2. equals(): Hashmap uses this method to check if two objects are equal or not. If this method returns true, they are equal, else they are not.
Syntax: boolean equals (Object ob)
Program to show usage of equals() :
import java.io.*;
import java.util.*;
public class Hashmap{
public static void main(String args[]) {
HashMap<String, Integer> hm = new HashMap<String, Integer>();
HashMap<String, Integer> hm1 = new HashMap<String, Integer>();
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
hm1.put("Red",1);
hm1.put("Blue",2);
hm1.put("Green",3);
hm1.put("Yellow",4);
System.out.println(hm1);
System.out.println(hm.equals(hm1));
}
}
Output :
{Red=1, Blue=2, Yellow=4, Green=3}
{Red=1, Blue=2, Yellow=4, Green=3}
true
Collisions
Collisions occur when distinct keys produce the same hashcode value, and the element is already present at that index value. To avoid or reduce collisions, a good hash function should be used, ensuring the best distribution of values throughout the hashmap. When a collision occurs, we use the chaining technique, as shown in the 2nd example above, to distribute the values.
Calculating Index in Hashing
Indexes are generated in hashing to reduce the size of an array. If the hashcode of the key is used as an index, the integer value obtained might be large, and it can increase the size of the array.
The Index is calculated using the formula :
Index = hashCode(Key) & (n-1)
n = the size of array/bucket
(n = 16 in case of default)
Hashing for Put() operations
Let us consider an empty hashmap with the default capacity of 16 (n=16).
1. No Collision: Suppose you want to put the entry (“welcome”,15) in a newly created map.
- As per the concept of hashing, the hash will be generated first using the hashCode(key)
- Calculate hash = hashCode(“welcome”); [suppose it is 200]
- Calculate index = hash & (16-1), [evaluates to 8]
- Create a node/Entry object with hash, key, value, and reference pointer.
- Place this object at index value 8 if it is empty.
2. Collision: Sometimes, a scenario might come where the index will be the same, and collision can occur. Let’s try inserting (“wait”,16) in the hashmap now.
- Calculate hash = hashCode(“wait”); [suppose it is 120]
- Calculate index = hash & (16-1), [evaluates to 8]
- Create a node object with hash, key, value, and reference pointer.
- Place this object at index value 8 if no other value is placed there.
- If some value is placed there, like in our case, it is a state of collision.
- In case of collision, check through equals() if the keys are similar.
- If the equals() method returns true, replace the value with the current value.
- If the equals() method returns false, then point this new node object to the previous node through a linked list at the same index value. (Chaining method)
- In our case, since the keys, welcome and wait are different, we will place a new node using a link list.
Hashing for the Get() operation
Let us see how to use hashing to implement the get operation. The get(Key) is used to get the value at the given key.
Example: No Collision
Let’s say you want to find the value of a key ”welcome”, follow the below steps of hashing.
- Calculate hash = hashCode(“welcome”); [assume 200]
- Calculate index = hash & (n-1) , n=16 [index evaluates to 8]
- Check the index 8; if this key matches with the element’s key using the equals() method, then return the value.
- If the key does not match, then check the next element’s key and so on.
- In our case, the key matches, so the value of the key “welcome”, i.e. 15, will be returned.
Example: Collision
Let’s say you want to find the value of a key ”wait” :
- Calculate hash = hashCode(“wait”); [assume 120]
- Calculate index = hash & (n-1) , n=16 [index evaluates to 8]
- Check that index; if this key matches with the element’s key using the equals() method, then return the value.
- Here, it does not match, so check the next element (next node) in the list. The next key at this index is waiting. Recheck the keys; they match now, so the value of the key “wait” [i.e. 16] will be returned.
- If the next reference of the Node is null, return null, else move to the next node and repeat the key matching process.
PERFORMANCE OF HASHMAP
The performance of the hashmap is based upon two significant factors :
- Initial Capacity
- Load Factor
Initial Capacity: The initial number of buckets a hashmap has when its instance is created. Its default value is 16. That is, initially, the hash map can store 16 key-value elements.
Load Factor: It is a measure of how much percentage the hashmap is allowed to fill before its capacity increases. The default load factor value is 0.75, ranging between 0 to 1 usually.
Some other terms related to performance are :
Threshold: It is the product of the load factor and the capacity of the hashmap. Default threshold value is 0.75*16= 12. When 12 elements are filled in the hashmap, we need to stop inserting more elements into it. Rehashing will be done, which will double the capacity of the hashmap.
Rehashing: It is a way of doubling the capacity when the threshold value is reached. When the threshold value is crossed, the rehashing is done so that the bucket now has twice the capacity and the operation takes less time.
Time Complexity of HashMap
Talking about the time complexity, the performance of a HashMap operation depends upon the hash function implementation. If the hashcode implementation is good (no hash collision), then the best, worst and average time complexity is O(1). In a situation where the hashcode implementation is bad (hash which gives a collision), complexity would be O(n). Also, the iteration over a hashmap depends upon its capacity and the key-value pairs. If the capacity is high, the iterations will increase, which will increase the time complexity and affect the performance.
Performance Improvement
Regarding performance improvement in Hashmap, two factors that must be chosen appropriately are the optimised hash function and capacity. The hash function implementation should be such that the hashcode gives no to fewer collisions. Keeping the capacity high will increase the iterations and the time complexity, so both these factors must be carefully chosen.
The changes that have been done in JAVA 8 :
Some hashmap performance improvement changes have been done in JAVA 8 to handle the hash collisions. Before Java 8, the hashmap performance was low in the case of hash collisions which had an impact on the complexity. Due to collisions, both the keys and values were placed in a node, and in the worst case, the complexity was O(n) due to link list traversal. Changes are as follows:
- Initially, the hash map will store the entries in a singly linked list, but when the threshold value is reached, the self-balancing BST trees will be used instead of a linked list. The benefit of using BST is that we get the worst-case complexity is O(log n).
METHODS IN HASHMAP
| put(K key,V value) | Inserts an entry in the map. |
| putAll(Map map) | Inserts a specified map in the map. |
| putIfAbsent(K key, V value) | Inserts the entry only when the key is not present. |
| remove(K key) | Deletes the entry for the specified key. |
| remove(K key,V value) | Deletes the entry for the specified key and value. |
| clear() | Removes all the mappings from the map. |
| isEmpty() | Returns true if the map has no key-value mappings. |
| size() | Returns the number of key-value mappings. |
| keySet() | Returns a set of keys in a hashmap. |
| values() | Returns a set of values in a hashmap. |
| entrySet() | Returns a set of entries(K, V) in a hashmap. |
| get(K key) | Returns the value associated with the given key. |
| replace(K key, V value) | Replaces the specified key with the specified value. |
| replace(K key,V oldvalue,V newvalue) | Replaces the old value with a new value for the specified key. |
| containsKey(K key) | Returns true if the specified key exists in the hashmap. |
| containsValue(V value) | Returns true if the specified value exists in the hashmap. |
| hashCode() | Returns the memory address of the object in integer form |
| equals(Object O) | Compares the specified object with the map and returns true if same. |
| clone() | Returns a shallow copy of the hashmap instance. |
| getOrDefault(K key, V defaultValue) | Returns the value to which the given key is mapped or returns the default value if the key is not mapped. |
| void forEach(BiConsumer<? super K,? super V> action) | It will execute the given action for all the entries until they are all processed or throw an exception. |
| V merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction) | If the specified key is not mapped to any value or if the key is null, then map it with the given value. |
| void replaceAll(BiFunction<? super K,? super V,? extends V> function) | It will replace each entry value with the result of the function after it has been processed. |
| V compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) | Computes the mapping for- the specified key and its current mapped value. Returns null if there is no current mapping. |
| V computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction) | Computes the value using the given mapping function if the specified key is not already associated with a value (or is mapped to null) and enters it into this map unless null. |
| V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) | Computes a new mapping given the key and its current mapped value if the value for the specified key is present and non-null. |
Some examples of the other essential functions of hashmap that are defined above :
Program to show the size of the hashmap :
import java.io.*;
import java.util.*;
public class Hashmap{
public static void main(String args[]) {
HashMap<String, Integer> hm = new HashMap<String, Integer>();
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
System.out.println(hm.size());
}
}
Output :
{Red=1, Blue=2, Yellow=4, Green=3}
4
Program to show putAll() and putIfAbsent() method :
import java.io.*;
import java.util.*;
public class Hashmap{
public static void main(String args[]) {
HashMap<String, Integer> hm = new HashMap<String, Integer>();
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
HashMap<String, Integer> hm1 = new HashMap<String, Integer>();
hm1.putAll(hm); //putAll
System.out.println(hm1);
hm.putIfAbsent("Orange",7); //putIfAbsent
System.out.println(hm);
}
}
Output :
{Red=1, Blue=2, Yellow=4, Green=3}
{Red=1, Blue=2, Yellow=4, Green=3}
{Red=1, Blue=2, Yellow=4, Orange=7, Green=3}
Program to show containsKey() and containsValue() methods :
import java.io.*;
import java.util.*;
public class Hashmap{
public static void main(String args[]) {
HashMap<String, Integer> hm = new HashMap<String, Integer>();
hm.put("Red",1);
hm.put("Blue",2);
hm.put("Green",3);
hm.put("Yellow",4);
System.out.println(hm);
System.out.println(hm.containsKey("Green"));
System.out.println(hm.containsKey("Orange"));
System.out.println(hm.containsValue(3));
System.out.println(hm.containsValue(7));
}
}
Output:
{Red=1, Blue=2, Yellow=4, Green=3}
true
false
true
false
Synchronised HashMap
As already stated above, Hashmaps are unsynchronised, meaning they are not thread-safe. When simultaneously accessing the hashmap, multiple threads can change it structurally and then it has to be synchronised externally. External synchronisation can be done in the following way :
Map m = Collections.synchronizedMap(Hashmap map);
Wondering where to learn the highly coveted in-demand skills for free? Check out the courses on Great Learning Academy.
Engaging in the study of Java programming suggests a keen interest in the realm of software development. For those embarking upon this journey with aspirations towards a career in this field, it is recommended to explore the following pages in order to acquire a comprehensive understanding of the development career path:
