1. Multithreaded PUT can cause element loss
public class ConcurrentIssueDemo1 {
private static Map<String, String> map = new HashMap<>();
public static void main(String[] args) {
Thread 1 => t1
new Thread(new Runnable() {
@Override
public void run(a) {
for (int i = 0; i < 99999999; i++) {
map.put("thread1_key" + i, "thread1_value" + i);
}
}
}).start();
Thread 2 => t2
new Thread(new Runnable() {
@Override
public void run(a) {
for (int i = 0; i < 99999999; i++) {
map.put("thread2_key" + i, "thread2_value"+ i); } } }).start(); }}Copy the codeNote ⚠️ : the above code may be thread unsafe, not directly run the thread unsafe situation.
Put source code analysis
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
/ / initialization
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// Hash the TAB position and assign the element at that position to p. If this position is empty, a new node is placed at that position
tab[i] = newNode(hash, key, value, null);
else {
// Append the list to the element that already exists in the TAB array index
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) {
// Create a new node and append it to the list
if ((e = p.next) == null) {/ / # 1
p.next = newNode(hash, key, value, null);/ / # 2
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 codeWhen two threads execute the put value and hash it to the same tab-array location, thread 1 executes #2 and overwrites thread 1’s put value after thread 2 executes #2.
2. If PUT and GET are concurrent, GET may be null
Scenario: Thread 1 performs PUT and resize because the number of elements exceeds threshold. Thread 2 performs GET, which may cause this problem
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
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 (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
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);
}
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>[])newNode[newCap]; #1table = newTab; #2
if(oldTab ! =null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> 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<K,V>)e).split(this, newTab, j, oldCap);
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;
elsehiTail.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;
}
}
}
}
}
return newTab;
}
Copy the codeWhen thread 1 executes to code #1, a new hash table is created with the newly calculated capacity, and #2 assigns the newly created empty hash table to the instance variable table. The table is empty. If thread 2 executes get at this point, it will get null.
3. In JDK7, HashMap concurrent put can create a loop linked list, resulting in an infinite loop of GET
Circular linked list the reason is that in the JDK1.7 expansion when the element from the old list to list when using the first method, lead to inconsistent elements before and after the expansion of the relative position, and add capacity may lead to the emergence of circular linked list in JDK1.8 fixes the problem, 1.8 use tail interpolation to the element with old chain table moved to the new list.
void resize(int newCapacity) { // Pass in a new capacity
Entry[] oldTable = table; // Reference the Entry array before expansion
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { // The size of the array before the expansion has reached the maximum (2^30)
threshold = Integer.MAX_VALUE; // Change the threshold to the maximum value of int (2^31-1) so that the capacity will not be expanded later
return;
}
Entry[] newTable = new Entry[newCapacity]; // Initialize a new Entry array
transfer(newTable); / /!!!!! Move the data to the new Entry array, which contains the most important repositioning
table = newTable; // The table property of the HashMap references the new Entry array
threshold = (int) (newCapacity * loadFactor);// Change the threshold
}
/** * Transfers all entries from current table to newTable. */
// The key is the transfer method, which rehashes elements from the old hash table to the new hash table
void transfer(Entry[] newTable, boolean rehash) {
Entry[] src = table; // SRC references the old Entry array
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { // Iterate over the old Entry array
Entry<K, V> e = src[j]; // Get each element of the old Entry array
if(e ! =null) {
src[j] = null;// Release the object reference of the old Entry array (after the for loop, the old Entry array no longer references any objects)
do {
Entry<K, V> next = e.next; / / # 1
int i = indexFor(e.hash, newCapacity); / / # 2!!!!! Recalculates the position of each element in the array
e.next = newTable[i]; / / tag [1]
newTable[i] = e; // Put the element on the array
e = next; // Access the element in the next Entry chain
} while(e ! =null); }}}Copy the codeJDK1.7 formation of circular linked lists
When two threads execute simultaneously expanding logic, when performing to the # 1 statement, thread 2 CPU time slice to thread 1, thread 1 logic, expansion and performed to the form of figure 2, and then thread 2 continue # 2 statements, end of a cycle, to reach the state of figure 3, changing the pointer to a state of the right key 👉 pointer, perform a cycle again, It reaches the state shown in Figure 4, and finally performs a loop to reach the state shown in Figure 5, where the circular linked list is formed.
Get causes an infinite loop because of the loop list
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if((tab = table) ! =null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) ! =null) {
if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
return first;
if((e = first.next) ! =null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
return e;
} while((e = e.next) ! =null);// The loop condition is always satisfied}}return null;
}
Copy the code