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);
            }
            inti = 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 added

  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;Thread 1 is suspended after executing this statement
            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

Welcome to attention

Refer to the blog

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