Shulou(Shulou.com)06/02 Report--

This article mainly introduces "how to avoid the problems of HashMap in the multithreaded environment". In the daily operation, I believe that many people have doubts about how to avoid the problems of HashMap in the multithreaded environment. The editor consulted all kinds of materials and sorted out simple and easy-to-use methods of operation. I hope it will be helpful to answer the doubts of "how to avoid the problems of HashMap in the multithreaded environment". Next, please follow the editor to study!

Before analyzing the concurrency problems of HashMap, let's briefly understand how the basic operations of put and get of HashMap are implemented.

Put and get operations of 1.HashMap

As we all know, the internal implementation of HashMap solves the hash conflict through the zipper method, that is, the structure of the linked list saves two values hashed to the same array location.

The main purpose of the put operation is to determine the null, execute HashMap's own hash function on the hashcode of key, get the bucketindex position, and overwrite the repeated key.

Analyze how the specific put operation is completed against the source code:

Several methods are involved:

Static int hash (int h) {h ^ = (h > 20) ^ (h > 12); return h ^ (h > 7) ^ (h > 4);} static int indexFor (int h, int length) {return h & (length-1);} after the data put is completed, how to get. Let's take a look at the operations in the get function:

Looking at the node data structure of the linked list, four fields are saved, including the hash value corresponding to key,value,key and the next node of the linked list:

Static class Entry implements Map.Entry {key V value;// storage value Entry next;// of final K key;//Key-value structure points to the next linked list node final int hash;// hash value} 2.Rehash/ and then hashes the internal array length

Hash table structure combines the advantages of array and linked list. In the best case, both search and insert maintain a small time complexity O (1).

However, combined with the implementation of HashMap, consider the following situation: if the capacity of the internal Entry [] tablet is very small, or if it is directly extreme to a scenario with a table length of 1, then all data elements will collide.

At this time, the hash table becomes a single linked list, and the time complexity of searching and adding is O (N), which loses the meaning of the hash table.

Therefore, in the operation of the hash table, the size of the internal array is very important, and a balanced number must be maintained so that the hash collision will not be too frequent and the space will not be too large.

This requires constant adjustment of the table capacity during the use of the hash table. Take a look at the addEntry () method in the put operation:

Void addEntry (int hash, K key, V value, int bucketIndex) {Entry e = table [bucketIndex]; table [bucketIndex] = new Entry (hash, key, value, e); if (size++ > = threshold) resize (2 * table.length);} the process of resize is the process of re-hashing table size, which is twice the current table capacity by default.

Void resize (int newCapacity) {Entry [] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity = = MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE; return;} Entry [] newTable = new Entry [newCapacity]; / / initialize a new array newTable transfer (newTable) that is twice the size of oldTable; table = newTable; threshold = (int) (newCapacity * loadFactor) } the key step is transfer (newTable), which transfers all elements of the current Entry [] table array to the new table

This transfer process will cause errors in the concurrent environment, causing the linked list in the array linked list to form a cyclic linked list, and the e = e.next operation will loop indefinitely and Infinite Loop will appear in the subsequent get operation.

The following is a detailed analysis of the performance of HashMap concurrency problems and how they occur.

3.HashMap may cause an infinite loop of get after multithreaded put

HashMap may cause get dead loop after multithreaded put in concurrent environment, which is characterized by CPU utilization of 100%.

Take a look at the transfer process:

Here is a quote from Cool Shell Chen Hao's blog post:

Rehash under concurrency

1) suppose we have two threads. I marked it in red and light blue.

Let's look back at this detail in our transfer code:

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

Note that because the e of Thread1 points to key (3), and next points to key (7), which points to the reorganized linked list of thread 2 after thread 2 rehash. We can see that the order of the linked list is reversed.

2) as soon as the thread is scheduled back for execution.

First, execute newTalbe [I] = e

Then e = next, causing e to point to key (7)

The next = e.next of the next loop causes the next to point to key (3)

3) everything is fine.

As soon as the thread goes back to work. Take off key (7), put it in the first one of newTable [I], and then move e and next down.

4) the circular link appears.

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

Note: at this point the key (7). Next has pointed to key (3), and the circular linked list appears.

So, when our thread called HashTable.get (11), the tragedy happened-- Infinite Loop.

Simulate this example for the above analysis

Here we perform a self-increment operation, iTunes + non-atomic operation in run, using AtomicInteger to avoid possible problems:

Public static void main (String [] args) {MapThread t0 = new MapThread (); MapThread T1 = new MapThread (); / / omit t2-t9 t0.start (); t1.start (); / / omit t2-t9} Note that concurrency problems do not necessarily occur and can be executed several more times

I have tested that the above code can easily generate an infinite loop, the console cannot be terminated, and there are threads in progress all the time.

This is a screenshot of the console of one of the endless loops. You can see that six threads are destroyed after successfully completing the put work, and four threads are not output, which are stuck in the put stage. If you are interested, you can go in and have a look at the breakpoint:

In the above code, if you turn on the comments, you won't have a similar problem with ConcurrentHashMap.

4. Multi-threaded put may result in element loss

Another possible concurrency problem with HashMap is the possibility of element loss.

Consider performing addEntry (hash, key, value, I) in multithreaded put operations, if hash collisions are generated

As a result, two threads get the same bucketIndex to store, and overwrite loss may occur:

5. Use thread-safe hash table containers

So here are a few suggestions on how to use a thread-safe hash table structure:

Using the Hashtable class, Hashtable is thread-safe

More advanced thread safety is achieved by using java.util.concurrent.ConcurrentHashMap,ConcurrentHashMap under concurrent packages

Or use synchronizedMap () synchronization method to wrap HashMap object, get thread-safe Map, and operate on this Map

At this point, the study on "how to avoid the problems of HashMap in a multithreaded environment" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.