HashMap is a hash table implementation of Map interface in Java. A map contains a collection of key-value pairs where key maps to the value.
HashMap permits null values and null keys and it doesn’t permit duplicate keys.It is unordered so it doesn’t guarantee that the order will remain constant with time.
Hashmap provides constant time performance for operations like get or put, provided the elements are distributed evenly among the buckets.
The performance of HashMap depends on two factors ,the initial capacity and load factor. The initial capacity is the number of buckets in the HashMap and the initial capacity is the initial size of the HashMap.The load factor is a measure of how full the hash map is allowed to get before it is resized (capacity is increased).When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.
The default load factor is .75 because this can be changed while creating the HashMap.
Basic structure of HashMap
Initially in HashMap when multiple keys land in the same bucket then values along with their keys are placed in a linked list. Since Java 1.8 HashMap is converted to binary tree when the number of elements in a bucket reached a certain threshold.
How hashCode() and equals () method impacts HashMap?
The hashCode() method converts an object into an integer form(this is basically the hash code of the object) ,this process is called hashing.The performance of the hashmap depends on the hashCode() method implementation.In HashMap the hashCode() is used to calculate the bucket where the key-value pair should land .
The equals() method is used to check if two objects are equal or not. HashMap use this method to determine if the key of the key-value pair being inserted already exists or not.
A bucket is one element of HashMap array.It is used to store node,each node contains a key-value pair.A bucket can have multiple key-value pairs which are implemented as linked list.If the number of nodes in the bucket reached a certain threshold the linked list is converted to binary tree.
The hashCode() and equals() method determines where the key-value pair lands (in which bucket)
The put method in HashMap
The put method is used to insert key value pairs in a HashMap. Here’s the steps:-
- The hashCode() method is called to calculate the hashCode of the key . The hashCode determines the index that is the bucket where the key-value pair will be inserted.
- The hashCode() and equals() method is called to check if the key being inserted, already exists in the bucket .So, each of the keys in the linked list or the binary tree is checked to match the key being inserted.If the key already exists in the bucket then replace the value of the key with the new value else create a new node and insert the key-value pair in the Bucket.
The get method in HashMap
In get method the key is provided as the parameter and the value of the key is returned .
Here’s the steps:-
- The hashCode() method is called to calculate the hashCode of the key.
- Calculate the index which determines the index or the bucket which contains the key-value pair.Index is calculated based on the hashcode of the key.
- Search for the key in the bucket.Compare each key in the bucket with the key passed in the get method using the equals and hashCode method.If the key matches with any of the keys in the bucket return the value associated with the key else return null.
Performance of HashMap
Until Java 1.7 ,the worst cast scenario ,when multiple hash code values end up in the same bucket values are placed in a linked list which reduces hash map performance from O(1) to O(n)
Since Java 1.8 when the number of items reaches a certain threshold in the linked list,it is converted to binary tree and when the number of elements are less than a certain threshold(due to deletion) they are converted back to linked list.This improves the worst case performance from O(n) to O(log n) .
References:- Oracle Docs
I hope you enjoyed reading this article .Happy Coding 🙂