HashMap(JDK7)在多线程下形成环形链表的原因

HashMap(JDK7)在多线程下形成环形链表的原因 一、HashMap结构

大家都知道在JDK7中HashMap是用数组+链表的方式存储元素的。

二、初始化

HashMap的构造器有4个，其中三个是以容量（initialCapacity，容量是用来计算数组table的大小的）和负载因子（loadFactor）为参数，另外一个构造器是以Map为参数。无参构造器调用的是参数为容量和负载因子的构造器，默认容量为16，负载因子为0.75f。默认的阈值（threshold）为容量大小。

public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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();
}

三、添加元素

当没有元素的时候，会先根据threshold对其膨胀（inflateTable），膨胀的作用就是新建一个长度适当的数组。数组的长度计算逻辑是：如果参数值toSize大于等于最大容量2的30次方，则长度为2的30次方，否则返回大于或等于toSize的最小的2的N次方的数。例如，toSzie是7，则长度就会为8，刚好是2的3次方。

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 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;
}
private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

实际添加元素的代码为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大于等于阈值并且新添加的元素所在的数组位置上不是空则需要扩容。扩容是将所有元素转移到另一个长度为原来两倍的newTable。

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

五、 转移元素

此时可能会形成环形链表，环形链表也就是在transfer（转移元素）的时候形成的。

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry e : table) {
        while(null != e) {
            Entry 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;
        }
    }
}

如果元素散列到数组的同一位置，则采用头插法，将原来table中的链表中的元素，遍历插入到新table链表头部。

六、形成环形链表实例

代码示例：

public class HashMapDemo {
    static private class Node {
        Integer key;
        Node(Integer key){
            this.key=key;
        }
        @Override
        public int hashCode() {
            return key%3;
        }
    }
    public static void main(String[] args) {
        circleDemo();
    }
    public static void circleDemo(){
        final HashMap map=new HashMap<>(2);
        map.put(new Node(1), 1);
        map.put(new Node(2), 2);
        map.put(new Node(5), 5);
        for(int i=0;i<2;i++){
            Runnable task=new Runnable() {
                @Override
                public void run() {
                    map.put(new Node(4),4);
                }
            };
            new Thread(task).start();
        }
    }
}    

注意：这里用2，5是因为2，5 mod3值相等，所以当数组的长度>=3时，都会被散列到table[2]的位置，这样才能模拟出环形链表。

执行步骤：

1. main线程中新建一个hashMap，此时阈值为2。

2. 往hashMap中添加第一个元素Node(1)后，table.length为2，阈值为1。

3. 添加Node(2)后，table.length为2，阈值为1。

4. 添加Node(5)时，因为 size>=threshold且 Node(5)被散列到table[0]且，table[0]是Node(2)不为空，所以此时要扩容，扩容时capacity为原来的2倍，所以扩容后table.length为4，threshold为3。
   此时hashMap结构为：
   

5. 多线程扩容形成环
   ①、线程Thread-0添加Node(4,4)，因为此时size=3 >= threshold=3 且 table[bucketIndex]为1，bucketIndex=1，所以要扩容，转移元素。
   当线程执行到 e = 5(这里用5代替entry对象)，next=2是停住
   
   此时该线程的newTable中只有newTable[1]有元素1。
   ②、下来执行线程Thread-1添加Node(4,4)，此时同样需要扩容，转移元素。该线程转移完元素后，停在transfer方法的末尾，此时2已经指向了5，newTable结构为：
   
   ③、下来继续执行Thread-0
   当前状态是 e=5, next=2
   将 newTable[2]赋值为e，即newTable[2]=5，e=2此时结构为
   
   再次循环 e=2，next=5(2的next=5是在线程Thread-1中转移的时候建立的关系，应为原来是5–>2，因为采用头插法，转移完后变为2–>5)，
   执行 newTable[2]=e, 后的结构为
   
   e=5
   再次循环
   e=5，next=null，newTable[2]=2
   执行完 e.next = newTable[2]后就会出现环，此时的结构为
   
   至此，环形链表出现。

总结

原因是由于不同线程在扩容的时候采用头插法插入，头插法扩容后会将原来的链表倒序。