Comics: HashMap with high concurrency

Last time we covered the basics of HashMap. For those of you who haven’t seen it, click on the link below:

Comics: What is a HashMap?

In this installment, we’ll take a look at the potentially fatal problems with HashMaps in high-concurrency environments.

The capacity of HashMap is limited. When the HashMap reaches a certain saturation after multiple element inserts, the probability of conflicts in Key mapping positions increases gradually.

At this point, the HashMap needs to expand its length, which is Resize.

There are two factors that affect the occurrence of Resize:

1.Capacity

The current length of the HashMap. As I mentioned in the last installment, the length of a HashMap is a power of two.

2.LoadFactor

HashMap load factor, default is 0.75F.

The criteria for measuring whether a HashMap is resized are as follows:

HashMap.Size >= Capacity * LoadFactor

Expansion and 1.

Creates a new empty array of entries twice as long as the original array.

2.ReHash

Iterating through the original Entry array, rehash all the entries into the new array. Why rehash it? As the length increases, the Hash rules change.

Let’s review the Hash formula:

Index = HashCode (Key) & (length-1)

If the array length is 8, the Hash operation is performed with 111B. The new array is 16 in length and Hash with 1111B. The Hash results are obviously different.

HashMap before Resize:

HashMap after Resize:

The Java code for ReHash is 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;if (rehash) { e.hash = null == e.key ? Zero:hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; }}}Copy the code

Note: The following content is very brain-burning, please sit firmly and hold well.

Suppose a HashMap has reached the critical point of Resize. Two threads, A and B, Put the HashMap at the same time:

When the Resize condition is reached, the two threads perform the first step of Rezie expansion respectively:

At this point, both threads have reached the ReHash step. Let’s review the code for ReHash:

If thread B is traversing the Entry3 object, the thread is suspended as soon as it completes the line in the red box. For thread B:

e = Entry3

next = Entry2

Thread A is rehashing unimpeded, and when the Rehash is complete, the result looks like this (e and Next in the figure, representing two references to thread B) :

Up until this point, everything looks fine. Thread B then resumes and continues with its own ReHash. Thread B was in the following state:

e = Entry3

next = Entry2

When we get to the above line, obviously I = 3, because thread A’s hash for Entry3 is also 3.

We continue to the two lines where Entry3 is placed at subscript 3 in thread B’s array, and e points to Entry2. Now e and next point to the following:

e = Entry2

next = Entry2

The overall situation is shown in the figure:

The next loop executes to the line in the red box:

e = Entry2

next = Entry3

The overall situation is shown in the figure:

Insert Entry2 into the head of thread B’s array using the following three lines:

The overall situation is shown in the figure:

The third loop starts with the code in the red box:

e = Entry3

next = Entry3.next = null

In the final step, the miracle comes when we execute the following line:

newTable[i] = Entry2

e = Entry3

Entry2.next = Entry3

Entry3.next = Entry2

The linked list has rings!

The overall situation is shown in the figure:

At this point, the problem hasn’t arisen directly. When Get is called to find a nonexistent Key and the Hash value of the Key is equal to 3, the program will go into an infinite loop because position 3 has a circular list!

This situation can not help but remind people of a classic interview question:

Comics algorithm: How to determine the linked list has a ring?

1. A Hashmap needs to be resized when too many elements are inserted

HashMap.Size >= Capacity * LOadFactor.

2.The HashmapResize consists of two steps: expansion and ReHash. ReHash may form a linked list ring in the case of concurrent operations.

— — the END — — –

If you like this article, please long click the picture below to follow the subscription number programmer Xiao Grey and watch more exciting content