1. Learning Objectives

1. The HashMap thread is unsafe.

The reason:

  • In JDK1.7, HashMap#transfer() is called due to multiple threads extending HashMap. A thread is suspended during execution, but the data of another thread has been migrated. After the CPU resources are released, the suspended thread executes the original logic again. As a result, the data is changed, causing an infinite loop and data loss.
  • HashMap#putVal(); HashMap#putVal(); Assume that A and B are two threads to put in operation, and the hash function to calculate the insert subscripts are the same, when A thread A performed after the 6th line suspended due to run out of time slice, and thread B time slice after insert the elements in the subscript place, completed the normal insert, and then thread A time slice, Since the hash collision judgment has been performed before, the judgment will not be performed at this time, but the insertion will be directly performed. As A result, the data inserted by thread B will be overwritten by thread A, making the thread unsafe.

To improve:

  • HashMap#transfer() is not available in JDK1.8 because HashMap#resize() is directly used to transfer data.

2, HashMap thread is not safe:

  • The JDK1.7 HashMap thread is not all present: an infinite loop, data loss
  • JDK1.8 HashMap thread not all now: data overwrite

Second, the causes of unsafe HashMap thread, infinite loop, data loss and data coverage

1. Threads caused by JDK1.7 expansion are unsafe

The thread insecurity of HashMap occurs mainly in the expansion function, which calls jdk1.7hshmap #transfer() :

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 ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; }}}Copy the code

This code is a HashMap expansion operation, repositioning the subscript of each bucket and migrating the elements into the new array using header interpolation. Header interpolation reverses the order of the linked list, which is the key to creating an endless loop. Now that you understand the headplug method, move on to see how it can cause endless loops and data loss.

2. Capacity expansion causes infinite loops and data loss

Let’s say we have two threads A and B expanding the following HashMap:

After normal expansion, the result is as follows:

But when thread A executes line 11 of the transfer function above, the CPU time slice runs out and thread A is suspended. As shown in the following figure:

Thread A: e=3, next=7, e.next=null

When thread A’s time slice runs out, the CPU starts thread B and completes data migration in thread B

Next =null; next=null; next=null; next=null

Then thread A gets the CPU time slice and continues to execute newTable[I] = e, putting 3 into the corresponding position of the new array. After executing this loop, thread A’s situation is as follows:

Next =3, next=3, insert 7 into the new array, and continue the loop as follows:

There’s no problem at this point.

Next =3, e=3, next=null, so this cycle will be the last cycle.

Next =7, 3 and 7 are connected to each other. When newTable[I]=e is executed, 3 is inserted into the linked list by header method, as shown in the following figure:

Next =null. When e=null is executed, the next loop will not proceed. After the capacity expansion operation of thread A and thread B is completed, it is obvious that A ring structure appears in the HashMap after thread A finishes execution, and an infinite loop will appear when the HashMap is operated in the future.

In addition, it can be seen from the figure above that element 5 was inexplicably lost during expansion, which caused the problem of data loss.

3. Threads in JDK1.8 are unsafe

HashMap#transfer() is not available in JDK1.8 because HashMap#resize() is used to transfer data.

Why does JDK1.8 have data coverage? Let’s look at the following put operation code in JDK1.8:

Which judge whether there is the sixth line hash collision, assuming that A and B are two threads to put in operation, and the hash function to calculate the insert subscripts are the same, when A thread A performed after the 6th line of code to be suspended due to run out of time slice, and thread B time slice after insert the elements in the subscript place, completed the normal insert, Then thread A obtains the time slice. Since the judgment of hash collision has been made before, thread A will not judge at this time, but directly insert. As A result, the data inserted by thread B will be overwritten by thread A, making thread unsafe.

Also, there is the 38th lines have A + + code size, we think so, or the thread of A and B, the two threads simultaneously put operation, assuming that the current HashMap zise size of 10, when the thread A execution to 38th lines of code, from main memory size has A value of 10 + 1 after preparation for operation, Thread B happily gets the CPU from main memory and writes size=11 back to main memory. Thread A then gets the CPU again and continues to execute (size is still 10 at this point). Thread A and thread B both performed A put operation, but the value of size increased by 1.

3. How to make HashMap thread safe operation in multi-threaded situation?

Use the Collections. SynchronizedMap (map), packaged into synchronous map, principle is all of the synchronized methods in a HashMap.

For example: the Collections. SynchronizedMap# get ()

public V get(Object key) { synchronized (mutex) { return m.get(key); }}Copy the code

Four,

1. The HashMap thread is unsafe.

The reason:

  • In JDK1.7, HashMap#transfer() is called due to multiple threads extending HashMap. A thread is suspended during execution, but the data of another thread has been migrated. After the CPU resources are released, the suspended thread executes the original logic again. As a result, the data is changed, causing an infinite loop and data loss.
  • HashMap#putVal(); HashMap#putVal(); Assume that A and B are two threads to put in operation, and the hash function to calculate the insert subscripts are the same, when A thread A performed after the 6th line suspended due to run out of time slice, and thread B time slice after insert the elements in the subscript place, completed the normal insert, and then thread A time slice, Since the hash collision judgment has been performed before, the judgment will not be performed at this time, but the insertion will be directly performed. As A result, the data inserted by thread B will be overwritten by thread A, making the thread unsafe.

To improve:

  • HashMap#transfer() is not available in JDK1.8 because HashMap#resize() is directly used to transfer data.

2, HashMap thread is not safe:

  • The JDK1.7 HashMap thread is not all present: an infinite loop, data loss
  • JDK1.8 HashMap thread not all now: data overwrite

Five, the reference

Blog.csdn.net/swpu_ocean/… Coolshell. Cn/articles / 96…