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

This article mainly explains "how to understand the infinite loop of JAVA HASH MAP". The explanation content in this article is simple and clear, easy to learn and understand. Please follow the ideas of Xiaobian slowly and deeply to study and learn "how to understand the infinite loop of JAVA HASH MAP" together!

the symptom

Previously our Java code used HashMap for some reason, but the program was single-threaded and everything worked fine. Later, our program performance problems, so we need to become multithreaded, so, after becoming multithreaded to the line, found that the program often accounts for 100% of the CPU, look at the stack, you will find that the program Hang in the HashMap.get() method, restart the program after the problem disappeared. But it'll come back later. Also, the problem may be difficult to reproduce in a test environment.

A quick look at our own code shows that HashMap is manipulated by multiple threads. Java documentation says that HashMap is not thread safe and should be ConcurrentHashMap.

But here we can look at why.

Hash table data structure

I need to talk briefly about HashMap, a classic data structure.

HashMap usually uses an array of pointers (assumed to be table[]) to disperse all keys. When a key is added, it will calculate the index i of this array through the Hash algorithm, and then insert this into table[i]. If two different keys are counted in the same i, then it is called a conflict, also known as a collision, which will form a linked list on table[i].

We know that if the size of table[] is very small, such as only 2, if you want to put 10 keys, then collisions are very frequent, so an O(1) lookup algorithm becomes a linked list traversal, and the performance becomes O(n), which is a defect of Hash tables.

Therefore, the size and capacity of the Hash table are very important. Generally speaking, when there is data to be inserted into the Hash table container, it will check whether the capacity exceeds the set threadhold. If it exceeds, the size of the Hash table needs to be increased, but in this way, all the elements in the Hash table need to be recalculated. It's called rehash, and it costs a lot.

I believe everyone is familiar with this basic knowledge.

HashMap rehash source code

Next, let's take a look at the source code for Java's HashMap.

Put a Key,Value pair into the Hash table:

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 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++;//The key does not exist, and a node addEntry(hash, key, value, i);return null;}

Check whether the capacity exceeds the standard

void addEntry(int hash, K key, V value, int bucketIndex){Entry e = table[bucketIndex];table[bucketIndex] = new Entry(hash, key, value, e);//Check whether the current size exceeds the threshold we set. If it does, you need to resize (size++ >= threshold)(2 * table.length);}

Create a new hash table with a larger size and migrate data from the old Hash table to the new Hash table.

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

Source code for migration, note highlights:

void transfer(Entry[] newTable){Entry[] src = table;int newCapacity = newTable.length;//The following code means://Pick an element from OldTable and put it in NewTable for (int j = 0; j < src.length; j++) {Entry e = src[j];if (e != null) {src[j] = null;do {Entry next = e.next;int i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e;e = next;} while (e != null);}}}

Okay, this code is pretty normal. And there was nothing wrong with it.

Normal ReHash Process

I assumed that our hash algorithm simply mod the size of the table (i.e. the length of the array) with key. At the top is the old hash table, where the Hash table size=2, so key = 3, 7, 5, mod 2 after the collision in table[1] here. The next three steps are to resize the Hash table to 4, and then all the rehashing.

Rehash under concurrency

1) Suppose we have two threads.

Let's go back to this detail in our transfer code:

do {Entry next = e.next; //

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.