This is the 58th installment of the Java Programmer’s Way to Progress column, and we’ll talk about why HashMap is thread-unsafe.
01, multi-threaded capacity expansion will be an infinite loop
As we all know, HashMap resolves hash conflicts by using the zipper method, in which key-value pairs of the same hash value are stored in a linked list when a hash conflict occurs.
In JDK 7, lists were stored in the header insertion mode, meaning that the next conflicting key/value pair is placed before the previous one (new elements in the same position are placed at the head of the list). The expansion may lead to circular linked lists, resulting in an infinite loop.
Resize method source code:
// newCapacity indicates the newCapacity
void resize(int newCapacity) {
// Small array, temporary over
Entry[] oldTable = table;
// Capacity before capacity expansion
int oldCapacity = oldTable.length;
// MAXIMUM_CAPACITY is the maximum capacity, 2 ^ 30 = 1<<30
if (oldCapacity == MAXIMUM_CAPACITY) {
// Adjust the capacity to Integer's maximum value 0x7FFFFFFf (hexadecimal) =2 to the 31th power -1
threshold = Integer.MAX_VALUE;
return;
}
// Initialize a new array.
Entry[] newTable = new Entry[newCapacity];
// Move elements from a small array to a large array
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// Reference the new large array
table = newTable;
// Recalculate the threshold
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
Copy the codeThe transfer method is used to transfer the elements of a small array into a new array.
void transfer(Entry[] newTable, boolean rehash) {
// New capacity
int newCapacity = newTable.length;
// Iterate over the small array
for (Entry<K,V> e : table) {
while(null! = e) {// Different values on the same key
Entry<K,V> next = e.next;
// Whether to recalculate the hash
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// Calculate the index of the element in the array based on the size of the array and the hash of the key
int i = indexFor(e.hash, newCapacity);
// New elements in the same position are placed at the head of the list
e.next = newTable[i];
// Put it on the new array
newTable[i] = e;
// The next element on the liste = next; }}}Copy the codeNote that the lines e.ext = newTable[I] and newTable[I] = e place the new element at the same position at the head of the list.
Let’s say it looks like this before expansion.
So the normal expansion would look something like this.
Assume that two threads are performing capacity expansion at the same time, and thread A is executing to newTable[I] = e; Thread A: e=3, next=7, e.next=null
Thread B starts execution and completes the data transfer.
At this point, next of 7 is 3 and next of 3 is null.
Then thread A gets the CPU time slice and continues to execute newTable[I] = e, putting 3 into the corresponding position of the new array. After executing this loop, thread A’s situation is as follows:
Execute the next loop, at this point e=7, the next of 7 in thread A was originally 5, but since the table is shared by thread A and thread B, and thread B completes smoothly, the next of 7 becomes 3, so the next of 7 in thread A is also 3.
With head insertion, it looks like this:
Ok, so next = 3, e = 3.
Proceed to the next loop, but this should be the last loop since thread B has null for next at 3.
Next =7; next=7; next=7; next=7;
When the dolls begin, element 5 becomes an abandoned baby
However, this issue was fixed in JDK 8 and the list will remain in the original order for expansion, as described in the HashMap expansion mechanism article.
02. Put causes elements to be lost in multiple threads
Normally, when a hash conflict occurs, a HashMap looks like this:
However, when multiple threads perform the PUT operation at the same time, if the calculated index positions are the same, the previous key will be overwritten by the next key, resulting in element loss.
Put:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// Step 1: If TAB is empty, create one
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// Step 2: calculate index and handle null
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// Step 3: The node key exists, overwriting the value directly
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
e = p;
// Step 4: Determine that the chain is a red-black tree
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// Step 5: The chain is a linked list
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// List length greater than 8 is converted to red black tree for processing
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// Key already exists overwriting value directly
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break; p = e; }}// Step 6
if(e ! =null) { // existing mapping for key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// Step ⑦ : Expand the capacity when the capacity exceeds the maximum
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Copy the codeThe problem occurs in step ② :
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
Copy the codeIf thread A executes TAB [I] = newNode(hash, key, value, null), thread A executes TAB [I] = newNode(hash, key, value, null)
Thread B then executes TAB [I] = newNode(hash, key, value, null).
Three gets killed.
03. Concurrent PUT and GET causes GET to null
When thread A performs PUT, the number of elements increases because the number exceeds the threshold. When thread B performs GET, this problem may occur.
Resize:
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null)?0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// If it exceeds the maximum value, it will no longer be expanded
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// If the value is not higher than the maximum value, the value is doubled
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// Calculate the new resize upper limit
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
}
Copy the codeTable = newTab; table = newTab; table = newTab;
In order to facilitate you to learn Java more systematically, the second brother has “Java Programmer progress” column open source to GitHub, you just need to gently star, you can fight strange upgrades with all your friends.
GitHub address: github.com/itwanger/to…
