jdk8之前版本中HashMap存在的问题剖析

一、put时存在丢失元素的问题

put方法逻辑说明

将新插入的元素放置到链表头部，原来的链表头部作为新元素的next节点

put关键代码块

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];   // 步骤1
    table[bucketIndex] = new Entry<>(hash, key, value, e);   // 步骤2
    size++;
}

Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k;
    hash = h;
}

丢失元素分析

当多线程put && key不相同 && key的hash值存在冲突（hash值相同或者hash值除以数组长度后的余数相同）时,即往同一个链表中插入时，由于没有加同步锁，假若线程a,b执行的步骤如下：
线程a 步骤1
线程b 步骤1
线程a 步骤2
线程b 步骤2

那么线程a put的元素将会丢失

二、resize时存在死循环的问题

resize方法逻辑说明

分析代码可以看出，扩容时会将结点倒序（原来的1个链表会拆分成2个，并且都会倒序）

resize关键代码块

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));    // 步骤1
    table = newTable;   // 步骤2
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

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;
        }
    }
}

死循环分析

假若hashmap中的一个槽位x上已经有一个链表，元素依次为(1,1)->(2,2)->(3,3)->(4,4)>(5,5)->(6,6) ，其中1在槽位x上，
理论上扩容后
槽位x : (5,5)->(3,3)->(1,1)
槽位2x : (6,6)->(4,4)->(2,2)

线程a,线程b 现在都要插入一个元素(7,7)时，检测发现都需要扩容，假若线程a,b执行的步骤如下：

线程a 步骤1 步骤1全部执行完成，这个时候newTable已经完成，元素已经倒序过来了 (5,5)->(3,3)->(1,1) && (6,6)->(4,4)->(2,2) ，可以看到(3,3)的next节点为(1,1)
线程b 步骤1 步骤1进行中， 遍历旧链表 (1,1)->(2,2)->(3,3) 接着再往后遍历时就又到(1,1),从而进入了死循环
线程a 步骤2
线程b 步骤2

参考文章
https://blog.csdn.net/maohoo/article/details/81531925

jdk8之后依旧还是存在死循环的问题

看代码情况只可能是两个红黑树节点的父亲节点相互引用才可以导致无法走出这个for语句。
[当另外一个线程put元素后，可能需要左旋或者右旋造成的临时状态]

final TreeNode<K,V> root() {
    for (TreeNode<K,V> r = this, p;;) {
        if ((p = r.parent) == null)
            return r;
        r = p;
    }
}

参考文章

https://blog.csdn.net/qq_33330687/article/details/101479385