Official account: Java Xiaokaxiu, website: Javaxks.com

Author: bboyzqh, link: blog.csdn.net/zhuqiuhui/a…

One of the reasons for using ConcurrentHashMap when looking at Java concurrent containers and frameworks today is: Thread unsafe HashMap. A HashMap can cause an infinite loop when performing a put operation concurrently, because multithreading causes the Entry list of a HashMap to form a circular data structure that can be searched in an infinite loop. Correct the reason to see other blogs, are more abstract, so here in a graphical way to show, hope to support!

(1) When adding elements to HashMap, it will cause the expansion of HashMap container. The principle will not be explained any more, and the source code is directly attached as follows:

/** ** Add elements to the table. If the table is not long enough after inserting elements, */ void addEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex]; void addEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); */ 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); table = newTable; threshold = (int)(newCapacity * loadFactor); }Copy the code

(2) Referring to the above code, transfer method is introduced. (Introduction of key points) This is the root cause of the immortal loop when HashMap is concurrent. The following is a description of the principle of the immortal loop by combining the source code of Transfer. First list transfer code (this is JDK7 source so), as follows:

/** * Transfers all entries from current table to newTable. */ void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null ! = e) { Entry<K,V> next = e.next; ---------------------(1) if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } // while } }Copy the code

(3) Hypothesis:

Map<Integer> map = new HashMap<Integer>(2); // Only two elements can be placed, where the threshold is 1 (when the table is filled with only one element), that is, when the insert element is 1, the capacity will be expanded (as known from addEntry method) // Two elements 3 and 7 will be placed, and if the insert element 8 (after hash mapping, it is not equal to 1), the capacity will be expandedCopy the code

Suppose the placement result is shown as follows:

Now you have two threads, A and B, both of which perform the PUT operation, that is, add elements to the table, that is, both threads A and B see A snapshot of the state of the diagram above

The execution sequence is as follows:

Execution 1: Thread A suspends at (1) in the Transfer function (marked in the transfer function code). Now we’re on the stack of thread A

e = 3
next = 7
Copy the code

Execution 2: Thread B executes the while loop in the Transfer function, that is, it will change the original table into a new table (thread B’s own stack) and then write it into the memory. (Assuming both elements map to the same location under the new hash function)

Execution 3: Thread A disconnects and then executes (seeing the old table) from transfer code (1), currently e = 3, next = 7, as described above.

\1. Process element 3 and add element 3 to the new table in thread A’s stack (the new table is in thread A’s stack, which is thread private and does not affect thread 2).

Thread A copies element 7, e = 7, next = 3 because thread B changed its reference, next = 3

\3. Next = 3, next = null, exit the while loop. After executing the while loop, the contents of the new table are as follows:

\4. When the operation is complete, the search will fall into an infinite loop!

Everyone is welcome to correct!