JDK1.7及以下HashMap并发出现死循环根因分析

2019-10-01 本文已影响0人妖云小离

问题出现条件

JDK1.7及以下版本
并发使用HashMap
HashMap发生resize（扩容）

总结成一句话，有多个线程并发向该HashMap中添加hash冲突的元素，直至HashMap发生扩容。

HashMap初始容量

首先我们看HashMap的3种构造方法（JDK1.7）：

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

参数说明：

参数名	说明	默认值
initialCapacity	HashMap的初始容量	2^4=16
loadFactor	负载因子	0.75f

我们常用的Map<K,V> map = new HashMap<>();其实是第3个构造方法，从该构造方法上方的注释可以看出，initialCapacity默认是16，loadFactor默认是0.75f。从HashMap的静态变量也可找到对应值：

那loadFactor到底有什么用呢？请往下看。

HashMap何时扩容

扩容肯定发生在HashMap的塞不下的情况下，那这里面的玄机肯定藏在put方法里面：

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

我们看到几个关键的方法：

方法	说明
`hash()`	计算Key的hash值
`indexFor()`	计算Value在数组中存放的下标位置
`addEntry()`	执行插入操作

乍一看没有扩容相关的代码，其实是在倒数第二行的addEntry()方法里面(其他两个方法的分析)：

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

我们看到，如果HashMap当前size >= threshod ，且数组当前位置不为null时，会进行扩容！
其中resize(2 * table.length)可以看出，每次扩容为原来容量的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));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

我们看到，关键步骤为倒数3行和倒数1行：

步骤1. transfer()方法把当前数组转换为扩容后的新数组，大小就是入参传进来的，是原来大小的2倍；
步骤2. 重新计算threhold，（新容量*负载因子）与（最大容量+1）两个值取小；

对于步骤2，我们引申一下：我们看构造方法中，threhold = initialCapacity。可能大家会有疑问，说好的负载因子呢？其实在构造方法中，尚未对HashMap进行初始化，即还没有正真去创建桶。在put方法中，我们看到了inflateTable(threshold);方法，这才是初始化Map的方法，有兴趣的同学可以去研究一下。为了尽量避免resize，当你知道你最多会往HashMap塞N个对象的时候，一开始就申请N个容量的HashMap，内部会自动帮你计算转换成2的倍数。（为什么是2的倍数）。

HashMap扩容时数组转换(头插法)

接下来就是扩容的重头戏——transfer()方法：

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

我们可以看到，该算法有两个主要步骤：
（TODO 什么时候需要rehash）