HashMap in JAVA (Structure and Working) - Study24x7
Social learning Network
study24x7

Default error msg

Login

New to Study24x7 ? Join Now
Already have an account? Login

HashMap in JAVA (Structure and Working)

Updated on 13 February 2020
study24x7
Java Object oriented programmi
6 min read 7 views
Updated on 13 February 2020

It is part of the java collection from java 1.2 version. It is a collection that is used to store data in a key-pair where all keys are unique. It is inherited by the feature of Dictionary Legacy Classes. In HashMap we use the technique of hashing so it is called HashMap.AbstractMap class is inherited by the HashMap class where AbstractMap class implements the Map interface. In terms of performance, HashMap gives constant-time performance for most frequent operations – insertion and retrieval. 


Important points on HashMap

HashMap can’t store duplicate keys.

‣ We can store null as keys and value in HashMap.

‣ In HashMap order for insertion is not maintained, for maintaining the order of insertion we use LinkedHashMap.

‣ It is not Thread-safe which means it is non-synchronized.

‣ It implements the cloneable interface that means we can make the object of Hash by using the clone feature 


How to declarer the HashMap 


HashMap<K,V> hashmap=new HashMap<K,V>();

Where,

K : represents the Key data type like String, Integer etc.

V : represents the value data type like we can use String, Object, ArrayList, Integer etc. 


Example: 

1. import java.util.Map; 

2. import java.util.HashMap; 

3. public class Main 

4. { 

5. public static void main(String[] args) { 

6. // Make the object of HashMap class 

7. HashMap<String,String> hashmap_ex=new HashMap<String,String>(); 

8. // Put the values in HashMap 

9. hashmap_ex.put("1_key","First value"); 

10. hashmap_ex.put("2_key","Second value"); 

11. hashmap_ex.put("3_key","Third value"); 

12. // Get the value from HashMap 

13. System.out.println("Value of I key: "+ hashmap_ex.get("1_key")); 

14. System.out.println("Value of II key: "+ hashmap_ex.get("2_key")); 

15. System.out.println("Value of III key: " +hashmap_ex.get("3_key")); 

16. // Get the map size 

17. System.out.println("Size of HashMap:"+ hashmap_ex.size()); 

18. // Update the key value 

19. hashmap_ex.put("1_key","Updated first value"); 

20. System.out.println("Value of the First key: "+ hashmap_ex.get("1_key")); 

21. } 

22. } 


Internal Structure of HashMap 


There are two factors on which HashMap internal performance depends.

➡ Load factor

➡ Initial capacity. 


What is the Initial capacity of HashMap..? 


As the name suggests the initial volume of HashMap, we can say that by default size of HashMap in terms of memory and buckets. The number of buckets in the hash table is the capacity of a HashMap. 24 is the default initial capacity of the HashMap i.e 16. When the capacity of the HashMap reaches the threshold it is doubled each time means the capacity is increased to 25-32, 26-64, 27-128..... 


What is the Load factor of HashMap..? 


In HashMap Load factor is the point value by if HashMap capacity reached then next memory size allocation done. As simple words, we can say increase the capacity of HashMap. The load factor always less than 1. By default load factor of HashMap is 0.75. 


How to calculate the Threshold of HashMap 


The threshold is the value by reaching the next memory allocation is done. 

Threshold = (Current Capacity) * (Load Factor) 

For example, if the HashMap is created with an initial capacity of 16 and a load factor of 0.75f, then the threshold will be, 


Threshold = 16 * 0.75 = 12 That means the capacity of the HashMap is increased from 16 to 32 after the 12th element (key-value pair) is added into the HashMap. 


HashMap is the most useful data structure in java because it gives almost constant time performance of o(1) for put and get operations. 


As we know HashMap stores information in the form of key-value pairs. Each key-value pair stored in an object of Entry<k,v> class. Entry<K, V> class is the static inner class of HashMap which is defined like below. 


static class Entry<K,V> implements Map.Entry<K,V>

final K key;

V value;

Entry<K,V> next;

int hash; 

}


As you see, this inner class has four fields. key, value, next and hash. 

➡ key: It stores the key of an element and its final. 

➡ value: It holds the value of an element. 

➡ next: It holds the pointer to the next key-value pair. It stored as a linked list. 

➡ hash: It holds the hashcode of the key. 



The image shows how HashMap stores information. As we can see it use an array of the object(node) internally, It is called a table. The process of storing data into HashMap involves two major things. Hashing and Indexing. 


What is Hashing ...? 


The concept of HashMap depends on the Hashing technique in which any object/variables change into a unique integer value, called as HashCode. Basically it is an algorithm or method. The two objects can hold the same HashCode.

 

The process to store the data into HashMap 


In the process of storing data into HashMap each keys values changes into HashCode which represent as table array values. On which we store the node with key and their value. In case of the same Hashcode first, we search the index of the table the traverse to the node and check for the key name if key same then the value is updated otherwise it added the next node the current node. Thus we can say In worst case HashMap behave like a Linklist. We store data into a HashMap by using the put method.


The process to get the data into HashMap 


In the process of getting the data from HashMap first, we change the key value into the HashCode and go the index of the bucket table. Then we traverse as Linklist the check the keys and return the matching key. We get the from HashMap by using the get method.





study24x7
Write a comment...
Related Posts