hashmap扩容时死循环问题

时间：05-13来源：作者：点击数：

废话不多说，大家都知道，hashmap不能用于多线程场景中，多线程下推荐使用concurrentHashmap！

但为什么多线程下不能使用hashmap那，主要原因就在于其的扩容机制。

文章是综合他人博客，自己加点写成的。（such as 我没画图，网上找的图。。）

故事的起源从hashmap的数据存放开始说起，默认hashmap大小是16.当数据过大时，毫无疑问，hashmap需要扩容去支持存放更多的数据。

源码如下 ——–Put一个Key,Value对到Hash表中：

public V put(K key, V value)
{
    ......
    //计算Hash值
    int hash = hash(key.hashCode());
    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++;
    //该key不存在，需要增加一个结点
    addEntry(hash, key, value, i);
    return null;
}

这里添加一个节点需要检查是否超出容量，出现了一个负载因子。

void addEntry(int hash, K key, V value, int bucketIndex)
{
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    //查看当前的size是否超过了我们设定的阈值threshold，如果超过，需要resize
    if (size++ >= threshold)
        resize(2 * table.length);//扩容都是2倍2倍的来的，
}

至于为什么扩容都是2的幂次方这个问题，建议自行搜索。。

既然新建了一个更大尺寸的hash表，然后把数据从老的Hash表中迁移到新的Hash表中。

void resize(int newCapacity)
{
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    ......
    //创建一个新的Hash Table
    Entry[] newTable = new Entry[newCapacity];
    //将Old Hash Table上的数据迁移到New Hash Table上
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

好，重点在这里面的transfer()!

void transfer(Entry[] newTable)
{
    Entry[] src = table;
    int newCapacity = newTable.length;
    //下面这段代码的意思是：
    //  从OldTable里摘一个元素出来，然后放到NewTable中
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

do循环里面的是最能说明问题的

当只有一个线程的时候：

图是网上找的，话我就凑合着说了，图上的hash算法是自定义的，不要纠结这个，是简单的用key mod 一下表的大小（也就是数组的长度）。不是那个实际的hash算法！

最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table[1]这里了。

接下来的三个步骤是Hash表扩容变成4，然后所有的

do {
    Entry<K,V> next = e.next; // <--假设线程一执行到这里就被调度挂起了
    int i = indexFor(e.hash, newCapacity);
    e.next = newTable[i];
    newTable[i] = e;
    e = next;
} while (e != null);

而我们的线程二执行完成了。于是我们有下面的这个样子。