Menu
After reading source code of java.util.HashMap#resize , I'm very confused with some part -- that is when some bin has more than one node.
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
Why I feel this part is no need to exist? Just use below code
newTab[e.hash & (newCap - 1)] = e;
is ok -- I think they have the same effect.
So why bother to have so many code in the else branch?
240
Using HashMap makes sense only when unique keys are available for the data we want to store. We should use it when searching for items based on a key and quick access time is an important requirement. We should avoid using HashMap when it is important to maintain the same order of items in a collection.
HashMap, like any other hash based collections, provides constant in time operations like put, get, remove, contains etc. Because, the logic is based on hashcode and the size of the HashMap doesn't affect the time it requires.
Advantages of HashMapAllows insertion of key value pair. HashMap is non synchronized. HashMap cannot be shared between multiple threads without proper synchronization. HashMap is a fail-fast iterator.
HashMap does not maintain any insertion order of its elements hence it is quicker than Map. In contrast to Map, HashMap can hold duplicate values. It's possible to implement the Map interface by utilizing its implementing classes.
At resize, every bin is split into two separate bins. So if the bin contained several linked items, you cannot move all of them into the single target bin based on the hash of the first item: you should recheck all the hashes and distribute them into "hi" and "lo" bin, depending on the new significant bit inside the hash ((e.hash & oldCap) == 0). This was somewhat simpler in Java 7 before the introduction of tree-bins, but the older algorithm could change the order of the items which is not acceptable now.
76
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
