introduce

Implementation principle of HashMap

While the previous article looked at the implementation of HashMap in JDK1.7, this article will focus on the cause of the HashMap deadlock

The formation of an infinite loop occurs when expanding and transferring elements

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];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}Copy the code

When this happens is in the Transfer function, and by default rehash is false

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

Normal transfer process

The example does not consider the capacity expansion threshold and assumes that the capacity expansion starts when four elements are addedThere are two main things that are interesting

  1. OldTable [I] will be placed in newTable[I] or newTable[I + oldtable.length]
  2. Linked lists are reversed when copied

    Abnormal transfer under concurrent conditions

    Suppose thread 1 is suspended after Entry<K,V> next = e.next, with e pointing to KEY3 and next pointing to KEY7

    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

    Thread 2 also executes the Transfer function and completes the execution. At this time, the state isThread 1 then executes the rest of the code, placing key3 at thread 1’s table[3]Next point e to key7, not null, enter the loop again, and point Next to key3 as shown below

Key7 is placed in thread 1’s table when the loop is finished, e points to KEY3, and next points to NULLIf e is not null, the loop can be executed again. Key3 is inserted again into the head node of table[3] in thread 1. At this point, e becomes null and the loop ends. Structure is as followsWhen the table of thread 1 or thread 2 is set as newTable, an infinite loop is formed when the get method is called on the chain

Welcome to attention

Refer to the blog

[1] juejin. Cn/post / 684490… [2] [3] www.javashitang.com/?p=1033 coolshell. Cn/articles / 96…