Skip to main content

How does a hash map work internally in Java?


Hash map work internally in Java


Image result for hash map internal working flow


























Basically, HashMap is an array of Entry class, a static inner class defined in HashMap is as below:
static class Entry implements Map. Entry {
final K key;
V value;
Entry next;
final int hash;
//getters and setters
}
Each element in Hashmap stores in it a key, its value, a reference to next entry in case hash value is the same for two entries, in that case, a linked list will be formed.
Default initial capacity of a HashMap is 16 i.e a HashMap is initialized with a default 16 sized array.
Now, let us see what happens when we put an element into HashMap.
Following is the code for put method in hashmap:
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 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;
}
private V putForNullKey(V value) {
for (Entry e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}

Lets decode the above lines of code;

1)As the HashMap allows values to be stored with null keys in the map, firstly we check if key is null or not.
2)If key is null,putForNullKey method is called and null key value is placed at 0th position of array.
for (Entry e = table[0]; e != null; e = e.next) {//As each element with same hashvalue forms linked list in a hashmap array, we iterate the element using a for loop.If e==null, we add the new element.

3)If key is not null, we need to find the index in the array where we will store our element and this is done using hashing.
int hash = hash(key.hashCode());//We calculate a unique hash corresponding to each element.
int i = indexFor(hash, table.length);//Passing the hash and array length we find the position in array to store the element.
static int indexFor(int h, int length) {
return h & (length-1);
}
As you can see we do & operation between array length and hash value and thus a location is found from 1to16, so suppose hash value is 00000000 00010000 & 00000000 00010000, will give an index of 16.
4)Next we check if an element entry exists at above found index if it doesnt exist we add the new element entry but if an entry element already exists at the index position , here comes the linkedlist into the picture.
5)In the if condition if (e.hash == hash && ((k = e.key) == key || key.equals(k))) , we compare the hash value and a comparison with the equals method written for the object or for the same references.
6)If the above condition is true, the old value is replaced with the new value.
7)If the 5th condition is false, we iterate the linked list until we find the exact key location and put the entry element.

Comments

Popular posts from this blog

What is JDK, JRE and JVM?

What are JDK, JRE, and JVM: JDK :- Java Development Kit (in short JDK) is Kit which provides the environment to Develop and execute(run ) the Java program. For eg. You(as Java Developer) are developing an accounting application on your machine, so what do you going to need into your machine to develop and run this desktop app? You are going to need  J-D-K  for that purpose for this you just need to go to the official website of sun or oracle to download the latest version of JDK into your machine. Hence, JDK is a kit(or package) which includes two things i) Development Tools(to provide an environment to develop your java programs) and ii) JRE (to execute your java program). JDK is only used by Java Developers. JRE: - Java Runtime Environment (to say JRE) is an installation package which provides an environment to only run(not develop) the java program(or application)onto your machine. For eg(continuing with the same example) after developing your accounting ap...

The Future of Java Developers in the Age of AI and ChatGPT

  In today's rapidly evolving tech landscape, AI tools like ChatGPT are becoming more integrated into the software development process. As a Java developer, whether you're just starting out or have years of experience, you might wonder: How can I stay relevant and succeed in the age of AI? In this post, we'll explore practical strategies to ensure you not only survive but thrive as a Java developer in this AI-driven world. 1. Embrace AI as a Tool, Not a Threat AI isn't here to replace you—it's here to help you. Tools like ChatGPT can automate repetitive tasks, assist with coding challenges, and even generate code snippets, allowing you to focus on more complex and creative aspects of development. For Freshers: Use AI tools to learn and understand Java more quickly. Let them assist you in writing code, but make sure you're also learning the logic and concepts behind it. For Experienced Developers: Integrate AI tools into your workflow to enhance productivity. L...

What are the best opportunities for java in 2021?

Firstly, Java is widely used for building enterprise-scale web applications. Java is known to be extremely stable and so, many large enterprises have adopted it. If you are looking for a development based job at a large organization, Java is the language that you should learn. It is widely used in Android App Development. So if anyone is willing to find a career in Android App Development, he/she should have an intermediate level of experience in Java. Some of the different domains where Java is used widely are as follows: Financial services:  It is used in server-side applications. Big Data:  Hadoop MapReduce framework is written using Java. Banking:  To deal with transaction management. Stock market:  To write algorithms as to which company they should invest in. Retail:  Billing applications that you see in a store/restaurant are completely written in Java. Android:  Applications are either written in Java or use Java API. Scientific and Research Communi...