Java’s HashMap is not thread-safe. ConcurrentHashMap should be used for multithreading.

[HashMap] [HashMap] [HashMap]

  • After a multithreaded PUT operation, the GET operation causes an infinite loop.
  • When multiple threads put non-null elements, get returns NULL.
  • Multithreading put operation, causing element loss.

1. Why the endless loop? (Using a non-thread-safe HashMap with multiple threads, single threads do not appear at all.)

  • A HashMap uses a linked list to resolve Hash conflicts. Since it is a linked list structure, it is easy to form closed links. In this way, a loop will be generated as long as a thread performs get operations on the HashMap during the loop.
  • In the single-threaded case, it is not possible for a single thread to operate on the data structure of a HashMap to produce a closed loop.
  • That’s only going to happen if you have multiple threads running concurrently, and that’s when you put, ifsize>initialCapacity*loadFactor, the HashMap will rehash, and the structure of the HashMap will change dramatically. It is possible that both threads fired the rehash operation at the same time, resulting in a closed loop.

2, how to produce:

Storing data PUT () :

public V put(K key, V value) { ...... Int Hash = Hash (key.hashcode ()); int i = indexFor(hash, table.length); // If the key has been inserted, replace the old value (link operation) for (Entry<k,v> e = table[I]; e ! = null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; AddEntry (hash, key, value, I); // The key does not exist. return null; } </k,v>Copy the code

When we put an element into a HashMap, we first hash the key to its position in the array (that is, the index), and then we can put the element into its position.

If there are already other elements in the same place, the elements in the same place are stored in a linked list, with the new element at the head of the chain and the previous element at the end.

Check whether the capacity exceeds the addEntry limit:

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); Resize if (size++ >= threshold) resize(2 * table.length); } </k,v></k,v>Copy the code

If the size exceeds the threshold, resize, create a larger hash table, and migrate the data from the old hash table to the new hash table.

Resize the Hash table.

void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; . // Create a new Hash Table Entry[] newTable = new Entry[newCapacity]; // Transfer (newTable) data from the Old Hash Table to the New Hash Table; table = newTable; threshold = (int)(newCapacity * loadFactor); }Copy the code

When the table[] array is small, it is easy to generate Hash collisions, so the size and capacity of the Hash table are very important.

Generally, when there is data to be inserted into the Hash table container, the thredhold is checked to see if the capacity exceeds the specified thredhold. If so, the Hash table size needs to be increased. This process is called resize.

The HashMap#transfer() method is used to map the old data into the new hash table.

void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; // Take an element from OldTable and place it in NewTable for (int j = 0; j < src.length; j++) { Entry<k,v> e = src[j]; if (e ! = null) { src[j] = null; do { Entry<k,v> next = e.next; Int I = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e ! = null); } } } </k,v></k,v>Copy the code

The red-coded code is the culprit that causes CPU usage to spike when using hashMap by multiple threads, resulting in an infinite loop that blocks multiple threads. Also recommended: Java advanced video resources

3. Graph HashMap infinite loop:

Normal ReHash process (single thread) : Assume that our hash algorithm simply mod the table size (that is, the array length) with a key.

The top hash table is the old hash table, where size=2, so key = 3, 7, 5, after mod 2 all conflict in table[1]. The next three steps are to resize the Hash table to 4 and then rehash all
,value>.

 

 

Concurrent Rehash (multithreading)

1) Suppose we have two threads.

do { Entry<k,v> next = e.next; Int I = indexFor(e.hash, newCapacity); // < int I = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e ! = null); </k,v>Copy the code

And our thread two execution is done. So we have something like this:

 

 

Note that since e of Thread1 points to key(3) and next points to key(7), it points to the reassembled list of thread 2 after thread 2 rehash. We can see that the order of the linked list is reversed. Here thread one becomes a HashMap after thread two.

2) Thread one is scheduled back to execute.

  • First performnewTalbe[i] = e;
  • And then thee = nextThat causes e to pointkey(7).
  • And the next cyclenext = e.nextAnd that leads to next pointingkey(3).

 

 

3) Everything is fine.

The thread resumed work. Remove key(7) and place it first in newTable[I], then move e and next down. There are already other elements in the same place, so all elements in the same place are stored in a linked list, with the new ones at the head and the previous ones at the end.

 

 

4) Circular links appear.

E.ext = newTable[I] causes key(3). Next points to key(7).

Note that key(7).next already points to key(3), and the circular list appears.

 

 

So, when our thread calls hashtable.get (11), the tragedy occurs — Infinite Loop.

Here’s why HashMap loops can occur in multiple threads, but in a real production environment, you wouldn’t use a thread-unsafe HashMap.