Shulou(Shulou.com)06/03 Report--

This article shows you how to analyze the Java8 HashMap expansion algorithm, the content is concise and easy to understand, can definitely brighten your eyes, through the detailed introduction of this article, I hope you can get something.

The HashMap expansion process of Java8 is mainly concentrated in the resize () method.

Final Node [] resize () {/ /... Omit the unimportant}

Among them, when the expansion of HashMap is completed, the original data needs to be transferred. As the capacity becomes larger, the location of some elements has to be changed, resulting in the following transfer process.

The transfer process is roughly as follows: take the value from the old array in turn, then take out the nodes from the linked list corresponding to the value, and put the module of the node into the lo linked list and the hi linked list respectively. When the nodes in the linked list are traversed, the lo linked list and the hi linked list are placed in different positions of the new array.

When I see line 15 below, I wonder why it is put in the lo linked list when (e.hash & oldCap) = = 0, otherwise it is the hi linked list?

Speaking of which, we need to review the process of storing new elements in HashMap. Looking at line 45 below, you can see that the insertion uses (n-1) & hash to calculate the position, that is, the array length-1, while the expansion shift is calculated using the array length n, so why?

For (int j = 0; j

< oldCap; ++j) { Node e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode)e).split(this, newTab, j, oldCap); else { // preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node 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; } } }}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // ...省略不重要的 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { // ...省略不重要的} 像我们看Java8的HashMap源码，应该都应该知道HashMap的底层数组长度都是2的n方的值 那么我们就假设一个底层数组长度为8的HashMap模拟进行插入元素和扩容移位的过程 长度n=8 ---->

0x1000

NMur1-> 0x0111

At this time, two elements are written, and the hash values of the two elements are hash2 = 0x0101 Personnal hash3 = 0x1101.

Hash2 & nmur1 = 0x0101

Hash3 & nmur1 = 0x0101

The results of the two hash models are consistent, so they will form a linked list in the same place.

What if we want to expand the capacity and shift at this time?

Hash2 & n = 0x0000

Hash3 & n = 0x1000

At this time, the results of the two are different, and the difference between 0x1000 is 8 in decimal, that is, the length of the array.

So that's why line 15 above only judges = = 0, because the result is only 0 and 1 (the length of the array is 2 to the n power, and only the highest bit except the symbol bit is 1).

The result of the two modules is equal to the length of the array, which is why lines 32 and 36 above are treated like that.

The above content is how to analyze the Java8 HashMap expansion algorithm, have you learned the knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.