Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”
This article also participated in the “Digitalstar Project” to win a creative gift package and creative incentive money
Code shrimp is a sand carving and funny boy who likes listening to music, playing games and writing as well as most of his friends. The days are still very long, let’s refuel our efforts together 🌈
🔥 Foreword — > Featured column
Self-introduction, to everyone recommend their column 😁, welcome small partners to collect attention 😊
Force link algorithm problem solving area
The small white to learn Java
MybatisPlus column
App crawler Column
PC side crawler column
Big factory interview question column
JDK7 HashMap
The JDK7HashMap has an infinite loop problem in multithreaded environments.
If thread A and thread B perform A put operation on A HashMap at the same time and the HashMap has just reached the capacity expansion condition, the HashMap needs to be expanded
Resize (); transfer(); transfer(); transfer(); 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;
// Iterate over the rehash for each list in the array
for (Entry<K,V> e : table) {
while(null! = e) {// Save the next node
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// Get the corresponding index position in the new array
int i = indexFor(e.hash, newCapacity);
/ / stern interpolatione.next = newTable[i]; newTable[i] = e; e = next; }}}Copy the codeLet’s suppose we have a linked list C — >D, and the index position of C and D is still the same, 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.next;) Thread B rehashes C and D into the new array, so the new array will be D — >C according to the header method
After B completes execution, thread A continues to execute
Because A get to e = C, next = D, C to rehash so, after that to get the D, C found D.n ext = C, D can also to rehash, so at this time because D – > C, at this time will get C, found that citigroup ext = null, but C is not null, So C rehashes the end of the list C — > D — >C, and since e is NULL, it exits the loop, and an infinite loop occurs. C – > D > C.
You can think about these words or draw them on your scratch paper and look at the picture below! = =
Graphic illustration:
==B The operation is complete ==
==A continues ==
Because A gets e = C and next = D, C can rehash
D. ext = C, so D can also rehash
C is not null, C is not null, so C rehash
At this point, e = NULL, so we exit the loop, and we have an infinite loop. C – > D > C.
JDK8 HashMap
Data overwriting occurs in 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;
}
Copy the code-
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, Since the hash collision judgment has been performed before, the judgment will not be performed at this time, but the insertion will be directly performed. As A result, the data inserted by thread B will be overwritten by thread A, making the thread unsafe.
-
Line 38: + + size is unsafe, or thread of A and B, the two threads simultaneously put operation, assuming that the current HashMap zise of size 10, when the thread A execution to 38th lines of code, from main memory size has A value of 10 + 1 after preparation for operation, but due to run out of time so we have to yield the CPU, Thread A takes the CPU again and writes size=11 back to main memory. Then thread A takes the CPU again and writes size=11 back to main memory. When thread B is done with the PUT operation, it writes size=11 back to main memory. Thread A and thread B both performed A put operation, but the value of size only increased by 1, so the thread is unsafe again due to data overwriting.
💖 finally
I am aCode pipi shrimp, a prawns lover who loves to share knowledge, will update useful blog posts in the future, looking forward to your attention!!
Creation is not easy, if this blog is helpful to you, I hope you can key three even oh! Thank you for your support. See you next time
