Introduction of the opening
Recently, I have learned the problem of HashMap’s infinite loop in multi-threaded scenarios, but I found that most bloggers’ solutions for the recurrence of this problem are: simulating multi-threaded simulation of concurrency, and the recurrence of the problem basically depends on luck, and the theory cannot match the reality. As a serious programmer, luck is obviously unreliable, hence this article.
This paper will be divided into the following three parts
- HashMap dead-loop problem source-level explanation
- Multithreaded Debug based on IntelliJ IDEA
- 100% recurrence of Hashmap dead-loop problem
It is recommended that you try to reproduce yourself after learning 1,2 and 2.
Dead-loop problem with HashMap (JDK1.7)
In JDK1.7, multi-threaded calls to the put method of a HashMap cause the get method to loop in an infinite loop, resulting in 100% CPU usage.
HashMap infrastructure
static class Entry<K.V> implements Map.Entry<K.V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/** * Creates new entry. */
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
Copy the code
Put method source brief analysis
Before using multi-threaded Debug to reproduce the problem, let’s look at the main methods involved by reading the source code.
The put method is the main logic
Let’s start with the hashmap. put method, which has five major steps of logic.
- If the hash table is empty, initialize the hash table
- Process a node whose key is null
- Computes the hash && position
- The existing key replaces the old value
- A node is added for a key that does not exist
public V put(K key, V value) {
// The hash table is empty
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// key = null Special handling
if (key == null) {return putForNullKey(value);
}
// Compute the hash value based on the key
int hash = hash(key);
// Compute the array position based on the hash
int i = indexFor(hash, table.length);
// loop linked lists
for(Entry<K,V> e = table[i]; e ! =null; e = e.next) {
Object k;
// If the current key already exists, update value, return oldValue
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// Add a new node
addEntry(hash, key, value, i);
return null;
}
Copy the code
AddEntry Adds node logic
There are two logical steps:
- If capacity expansion is required, perform capacity expansion. After capacity expansion, the hash table changes and the hash and hash positions of nodes are recalculated
- Do not need to increase | | expansion is completed, use the new node interpolation.
void addEntry(int hash, K key, V value, int bucketIndex) {
// Determine whether capacity expansion is required
if ((size >= threshold) && (null! = table[bucketIndex])) {// Perform capacity expansion
resize(2 * table.length);
// Recalculates the positions in the hash and hash arrays
hash = (null! = key) ? hash(key) :0;
bucketIndex = indexFor(hash, table.length);
}
// Add a new node
createEntry(hash, key, value, bucketIndex);
}
Copy the code
Resize Expansion method logic
There are three logical steps:
- Create a new hash table. If the current hash table has reached the maximum value, reset the threshold and return
- Migrate original hash table data
- Recalculate the expansion threshold
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
// Limit the maximum value of the hash array
// MAXIMUM_CAPACITY = 1 << 30;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// Create a new hash array
Entry[] newTable = new Entry[newCapacity];
// Migrate the original hash array data to the new array
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
// Recalculate the expansion threshold
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
Copy the code
Transfer Transfer historical data method logic
The main purpose of the transfer method is to move the data from the original hash table to the new hash table. In multithreaded scenarios, there is a risk of loop formation due to the use of the header rule.
The main logic is:
- Loop through the nodes in the original hash table
- Loop into a new hash table using header interpolation
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// Loop through the old hash array
for (Entry<K,V> e : table) {
// Loop through the current list
while(null! = e) { Entry<K,V> next = e.next;// Rehash if needed
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// Calculates the new hash array position
int i = indexFor(e.hash, newCapacity);
// Use the header method for data relocatione.next = newTable[i]; newTable[i] = e; e = next; }}}Copy the code
A case study of an infinite loop
Current data scenario:
- HashMap capacity: 4, expansion factor: 0.75 (default)
- Data 1, 9, and 16 already exist
- Thread 1 and thread 2 perform the PUT operation at the same time to trigger capacity expansion and data migration
Step 1: Thread 2 enters the transfer logic loop, e=16, E.ext =9. After variable assignment, thread 2 runs out of execution time slice. Before thread 1 performs data migration, memory distribution is as follows
Step 2: Thread 1 completes data migration, but does not replace the original table. The memory distribution is as follows
E =16, e.ext =9, table[1] = null. After entering the first loop, the memory distribution is as follows
Step 4: Thread 2 continues with the reference status: e=9, e.ext =16 (thread 1 is migrating), table[1] =16. After entering the second loop, the memory distribution is as follows
Step 5: Thread 2 continues with the reference status e=16, e.ext =null, table[1] = 9. Next = 9,9. Next =16 (loop reference) memory distribution is as follows
Multithreaded Debug
An introduction to
Setting breakpoints for multithreading is also very simple
- To set breakpoints
- Open the Settings panel
- Select the breakpoint where you want multithreaded debug
- Set the breakpoint pause level to: thread
- To take effect
Check to see if this works, and now we can Debug the different threads separately
/** Test environment: JDK1.7 development tool: IDEA 2018.3 */
public class Main {
public static void main(String[] args) {
Runnable testRunnable = new Runnable() {
@Override
public void run(a) {
System.out.println("Current thread :"+ Thread.currentThread().getName()); }}; Thread testThread1 =new Thread(testRunnable);
testThread1.start();
Thread testThread2 = newThread(testRunnable); testThread2.start(); }}Copy the code
100% replay of the Hashmap infinite loop
/** Test method for Debug */
public class Main {
public static void main(String[] args) {
final HashMap testMap = new HashMap(4);
testMap.put(1.1);
testMap.put(9.9);
testMap.put(16.16);
Runnable testRunnable = new Runnable() {
public void run(a) {
System.out.println(Thread.currentThread().getName());
testMap.put(13.13); }}; Thread testThread1 =new Thread(testRunnable,"Test-Thread-1");
testThread1.start();
Thread testThread2 = new Thread(testRunnable, "Test-Thread-2");
testThread2.start();
}
// This method computes key values that can be chained
public static void computeNum(a) {
for (int i = 0; i < 10000; i++) {
int hashCode = hash(i);
if (hashCode % 4= =1 && hashCode % 4 == hashCode % 8) {
System.out.printf("hash:%d , i:%d", hashCode, i); System.out.println(); }}}/** * The hash method * copied from the 1.7 HashMap@param k
* @return* /
public static final int hash(Object k) {
int h = 0;
if (0! = h && kinstanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4); }}Copy the code
Refer to step 1 of the case
Refer to step 2 of the case
Refer to step 3 of the case
Refer to step 4 of the case
Refer to Step 5 of the case
conclusion
- In the subsequent 1.8 version, the header method has been cancelled, but because of the introduction of the concept of red black tree, it will also cause the problem of dead loop in the multi-threaded tree, the follow-up to the small series of ability to rise again to share with you.
- Don’t forget to consider these non-thread-safe constructs when using multithreading to optimize history code.
End
Thank you to see this, the above logic will inevitably have some omissions, if you have what do not understand, or found those wrong places, please feel free to communicate through messages, finally HOPE that we are getting better and better, skilled, bold, mutual encouragement!