This topic is a foundation for learning ConcurrentHashMap and will be updated later.

We all know that in jdk1.7, our HashMap was composed of an array (bucket) and a linked list. Today we will take a look at why HashMap is dead in concurrent cases.

Analysis of the

We know that HashMap will be expanded when its capacity reaches a set threshold (0.75F), so expansion is designed to be a migration problem, while HashMap 1.7 is inserted using a header method.

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;//T1 The time slice expires and exits
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            inti = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; }}}Copy the code

For example, if two threads T1 and T2 join at the same time, such as Entry1 and Entry2, assume that the threshold is reached, then the two threads are simultaneously expanded (there will be two newtables here), t1. e and T1.next, as shown in the figure respectively, at this time, the time segment expires, and the CPU execution resources are released. T2 completes resize, as shown on the right, at which point the T1 thread wakes up and finds T1.e and T1.next, as shown on the right. They continue to execute the code

e.next = newTable[i];
newTable[i] = e;
Copy the code

NewTable =null,newTable[I]=e

Then loop e = Entry2, next=Entry1. And then I’m going to go ahead and do this.

For the last loop, e=Entry1,next=null. Go ahead and plug.

Here, a newTable ring link has been formed. When the program is searching for the key, it may not go out all the time, resulting in 100% CPU resource utilization.

conclusion

So the main reason is the use of header interpolation, which causes the program to loop forever in the concurrent case and never find the key (after the loop list). Therefore, in 1.8 HashMap was improved to use the tail interpolation method to ensure that the order does not cause an infinite loop. After all, in a multithreaded situation, it doesn’t cause an infinite loop, but it does cause semantically incorrect situations.