An overview of the

In a hashMap, when a certain number of values are inserted, the hashMap rehashes and expands, and a deadlock occurs during expansion.

Expansion conditions

   public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        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);
        return null;
    }

Copy the code

This is the put method for the new element. If the new element does not exist in the table array through the hash index, the addEntry method is called

    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null! = table[bucketIndex])) { resize(2 * table.length);
            hash = (null! = key) ? hash(key) :0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

Copy the code

If size is greater than threshold (which is the initial value), the system will expand the capacity. The capacity must be a multiple of 2, because bitwise operations will be performed during index calculation

    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

Create a new Entry according to newCapacity and send it as a parameter to the Transfer method. The transfer method is to re-hash the Entry data in the original table and save it to newTable. Then table=newTable to complete the expansion. The place where the deadlock is sent is sent in the Transfer method

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

Now that we’ve come to the point, let’s look at how to send deadlocks.

If :table.length=2, the values are 3, 7, and 5, arranged as follows

After capacity expansion: table.length=4, the sequence is as follows

But this permutation is only the case without sending deadlocks, if the scenario with high concurrency, the result will be different.

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

Suppose: thread A, thread B

Entry<K,V> next = e.next;
Copy the code

When B executes the following code for the first time and suspends, then e=3, next=7, when B suspends, thread A completes the expansion of transfer, then 7.next=3, 3.next=null, and the expansion is shown as follows:

Then thread B continues and evaluates the index of e=3 to 3, completing the first loop:

Then the second loop, e=7,next=3

Why is next=3? After thread A completes capacity expansion, next of 7 is 3, so next=3 when Entry<K,V> next= e.next is executed

Next =null; if ==e.next = newTable[I]== (I = newTable[I]== (I = newTable[I]))

Note that no deadlocks have been sent yet. Deadlocks are created when fetching elements, such as calling a nonexistent element with index 3.