preface

HashMap has some differences between JDK7 and JDK8, as shown below:

  1. JDK7HashMap is an array + linked list, while JDK8 is an array + linked list + red-black tree
  2. JDK7 uses head insert for capacity expansion, while JDK8 uses tail insert
  3. The Rehash of JDK7 is a full Rehash, while JDK8 is a partial Rehash.
  4. JDK8 is optimized for key hash calculation compared to JDK7.


If you are interested, you can learn my following article, which is very detailed!!

High-frequency questions: Handwritten HashMap

JDK7, 8 expansion source level detail

JDK7, 8HashMap get(), put() process detail


JDK7 HashMap

The JDK7HashMap has an infinite loop problem in a multi-threaded environment.

If thread A and thread B put A HashMap at the same time, and the HashMap just number reaches the capacity expansion condition, capacity expansion is required

JDK7HashMap scaling calls the resize() method, which calls the transfer() method to rehash all the elements of the old array into the new array. This is a problem in a multi-threaded environment ==)

void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; If (Entry<K,V> e: table) {while(null! = e) {// leave Entry<K,V> next = e.ext; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); Int I = indexFor(e.ash, newCapacity); int I = indexFor(e.ash, newCapacity); // newTable = newTable[I]; newTable[i] = e; e = next; }}}

Suppose there is a linked list C — >D, and the index position of C and D is still the same after the expansion, then they are still in the same linked list

Now thread A enters the transfer method to get C and its next node D(Entry<K,V> next = e.ext;) After that, thread A is suspended, while thread B goes through the normal process to rehash C and D into the new array. Then, according to the header interpolation method, the new array is D — >C

After B finishes executing, thread A continues executing

C = C; C = C; C = C; C = C; C = C; C = C; C = C; C = C In this case, C — > D — >C is the tail of the list. Since e = NULL at this time, the loop exits. At this time, an infinite loop appears. C – > D > C.


== You can think about these words or draw a picture on your scratch paper to see the following figure! = =


Illustrated demonstration:

==B Normal execution complete ==

==A continues to execute ==

Because A gets E = C and next = D, C can rehash





D. Ext = C, so D can also carry out rehash





C.next = null, but C is not null, so C rehash again

If e = NULL, exit the loop. An infinite loop occurs. C – > D > C.


JDK8 HashMap

Data overwrite will occur with JDK1.8 

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key ! = null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key ! = null && key.equals(k)))) break; p = e; } } if (e ! = null) { // existing mapping for key V oldValue = e.value; if (! onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
  • == Line 6 == : Assume that A and B are two threads to put in operation, and according to the key to calculate the hash values are the same, so get to index the subscript is also same, when A thread A execution after the sixth line suspended due to run out of time slice, and thread B time slice after insert the elements in the subscript place, completed the normal insert, and then thread A time slice, As A result, the data inserted by thread B is overwritten by thread A, which makes the thread unsafe.
  • Thread A and Thread B are still putting operations at the same time. Assuming that the size of the current HashMap is 10, when Thread A executes on line 38, it will get size of 10 from main memory and prepare to perform +1 operation. Thread B gets the CPU from the main memory and writes size=11 back to the main memory. Then thread A gets the CPU again and continues to execute (the value of size is still 10). After the put operation is completed, thread B gets the CPU again and continues to execute (the value of size is still 10). Write size=11 back to memory. Thread A and Thread B both perform A PUT operation, but the value of size is only increased by 1.

<br/>



The last

I am aCode pipi shrimp, a love of sharing knowledge of mantis shrimp lovers, in the future will continue to update the beneficial blog, look forward to your attention!!

Creation is not easy, if this blog post is helpful to you, I hope you can == a key three even oh! Thanks for your support. See you next time ~~~

== Share outline ==

Big factory interview topic column






Java from entry to the grave learning route directory index






Open source crawler example tutorial directory index

<font size=”5″> <font size=”5″>Hello World (low low ◡)

Welcome to pay attention to my public number, connotation more quality blog share, look forward to your joining! 😁.