Collection
HashMap:
HashMap is an implementation of Map interface.
It is used to store key and value pair.
Key can’t be duplicated and Value can be duplicated.
Insertion order is not preserved.
Each key-value pair are stored as instance of [Link] instances
represented by Node.
Each node contains key, value, hash (hash of key) and next
(reference of next node).
Generated hash code of key object is also stored to avoid
calculating hash every time while comparison.
Internal implementation of HashMap
HashMap internally maintains an array i.e. bucket array or Node
array
Size of array is determined by initial capacity of HashMap. Default
is 16.
Each index position in the array is called bucket that can hold
multiple Node objects using a LinkedList.
It is possible that multiple keys may produce same hash that maps
to single bucket that is why, the Map entries are stored as
LinkedList.
But when entries in single bucket reach a threshold
(TREEIFY_THRESHOLD, default value is 8) then Map converts
the bucket’s internal structure from LinkedList to a RedBlackTree.
All Entry instances are converted into TreeNode instances.
Basically, when bucket length is too big, HashMap dynamically
replaces it with an ad-hoc implementation of TreeNode. This way,
rather than having a O(n) performance, we get a much better
O(log n).
Note that when nodes in a bucket reduce less than
UNTREEIFY_THRESHOLD (default is 6) the Tree again converts
to LinkedList. This helps balance performance with memory usage
because TreeNodes takes more memory than [Link]
instances. So, Map uses Tree only when there is a considerable
performance gain in exchange for memory wastage.
Put operation:
Internally, first calculates the hashcode of the key and then
ultimately hashcode is used to compute bucket index.
Once bucket index is located, HashMap stores the Node in it.
Collision Handling:
As we know that for unequal key objects can have same hashcode
value.
Node class has an attribute next that always points to next object
in chain.
So, all the nodes with equal keys are stored in same array index in
the form of LinkedList.
When a Node object needs to be stored at a particular index,
HashMap checks whether there is already a Node is present or
not.
If there is no Node already present then current Node object is
stored.
And if an object is already there on calculated index, it checks
reference of the current key and already existing key, if both are
equal then update value of existing Node with value of current
Node. And if references are not equal then compares the key with
equals method. If both are equal with equals method then update
the value otherwise checks next attribute of existing Node. If next
node is null store the current Node otherwise repeat it again.