This content originally appeared on Level Up Coding - Medium and was authored by Prachi Jamdade
Hey All 👋,
I’m back with another interesting topic which is “HashMap”. In this article, we are going to learn about hashmaps and what is the internal working of hashmaps.
This is a very important question for interviews. I was asked about the working of hashmap in one of my past interviews and used them in many solutions.
For all the problem solvers out there, HashMap is one of the favorite data structures to solve coding problems. Even I’m also one of them 😆. Hashmaps can make problem-solving much easier and quicker. Let’s find out the reason for this 😉
In this world of programming, Hashing is a method of storing key-value pairs and this is achieved by making use of HashMaps in Java. Since I code in Java, I'll talk about the working of HashMaps in Java.
What is HashMap ?
HashMap class is a part of the Java Collections Framework which is used for storing elements in key-value pairs. All the keys in a hashmap are unique. And it allows retrieving value by key.
Suppose you want to store the employee details such as employee id and employee name then you can easily store them using a hashmap. The employee id serves as the key and the employee name as the value which can be mapped to the employee id.
Some important points to remember about hashmap :
- Used for storing key-value pairs using a hashtable
- Only unique keys are allowed
- Hashmap doesn't guarantee the ordering of elements
What if we try to store multiple keys with the same value in a HashMap ?
Well, the answer is No! You can’t store multiple keys with the same value in HashMap. If you try to do so, then overriding will happen, i.e, the old key-value pair will be replaced with the new key-value pair.
Internal Working of a HashMap :
A hashmap uses a hashtable, however, it is internally implemented using two data structures namely an array and a linked list. Whenever you declare a hashmap, internally, it will create an array of buckets. The buckets are referred to as nodes or you can say a linked list. A node can represent :
- Hashcode
- Key
- Value
- Address of the next node
Now, when you insert values in a key using put() method of the HashMap class, the hashcode will be generated by the put() method. Hashcode makes the process of receiving values faster and easier. And this hashcode is further computed and it will generate the index for storing the value.
The value of our key will be stored at the index given by the hashcode in the form of a Linked list.
To make retrieval of the key-value pairs more efficient, Java 8 introduced Binary Search Tree (BST) to use in place of a linked list.
Now, let’s see how the index is calculated for storing the value.
Index Calculation in HashMap :
Hashcode of the key may be very large to create an array. Hashcode generated may be in the range of integer and if we create arrays for such a long range, then it could be memory consuming task.
index = hashCode(key) & (length-1)
The expression hashcode & (length-1) does a bit-wise AND on hashcode using length-1, which is like a bit-mask, to return only the low-order bits of hashcode, thereby making for a super-fast variant of hashcode % length.
In Hashmap put (insertion), remove (deletion) and get (search) operations are performed at constant time i.e, time complexity is O(1) with the assumption that key-value pairs are well distributed across the buckets.
Collision in a HashMap :
A Hash Collision is a situation where for two or more distinct records, the hash function returns the same bucket position in the HashTable. This is the main disadvantage of using hashmap.
HashMap uses these two methods to handle collision:
- Separate Chaining
- Open Addressing
Data Structures used for Separate Chaining are -
- Linked List
- Self Balancing Binary Search Tree
- Dynamic Sized Array
In chaining, all key-value pairs mapping to the same index will be stored in the linked list of that index. Similarly, binary search trees can also be used for chaining.
Collision is a very important topic to learn about. I’ll share one dedicated article on this.
This is all I’ve learned about HashMap till now. If you find this article useful then give it a clap.
Happy Learning!!!
How a HashMap Works Internally was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Prachi Jamdade
Prachi Jamdade | Sciencx (2022-06-28T11:27:27+00:00) How a HashMap Works Internally. Retrieved from https://www.scien.cx/2022/06/28/how-a-hashmap-works-internally/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.