概述

可以先看前篇 HashMap源码分析

我们都知道HashMap线程不安全，源码的注释也写明，多线程访问必须加锁。

 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access a hash map concurrently, and at least one of
 * the threads modifies the map structurally, it <i>must</i> be
 * synchronized externally.

模拟场景

那到底为什么呢？到底会出现什么不安全的情况呢，我们写个例子看看。

public class HashMapTest {

    static Map<String, Integer> map = new HashMap<>();

    public static void main(String[] args) throws Exception{
        int num = 5;
        // 控制线程同时起跑
        final CountDownLatch startDownLatch = new CountDownLatch(1);
        // 控制线程都跑完任务
        final CountDownLatch stopDownLatch = new CountDownLatch(num);
        IntStream.range(0,num).forEach(i->{
            new Thread(()->{
                try {
                    // 每个线程到这些先等着
                    startDownLatch.await();
//                 每个线程往map里添加10000个相同的key
                    for (int j=0;j<10000;j++){
                        map.put("key"+j,j);
                    }
                } catch (Exception e) {
                    e.printStackTrace();
                }
                System.out.println("第"+(i+1)+"个线程执行完成了,size="+map.size());
                stopDownLatch.countDown();
            }).start();
        });
        Thread.sleep(1000);
        // 让所有等待的线程同时执行
        startDownLatch.countDown();
        // 当前线程等待，等待所有线程都执行完了才往下执行
        stopDownLatch.await();
        System.out.println("全部执行完成，size="+map.size());
    }
}

我们先把 HashMap换成 ConcurrentHashMap 看下正确的结果

static Map<String, Integer> map = new ConcurrentHashMap<>();

第3个线程执行完成了,size=10000
第1个线程执行完成了,size=10000
第5个线程执行完成了,size=10000
第2个线程执行完成了,size=10000
第4个线程执行完成了,size=10000
全部执行完成，size=10000

应该跟所有人的预料结果一模一样。想知道 ConcurrentHashMap的源码分析，可以阅读前篇 ConcurrentHashMap
现在换成 HashMap 看看会出现什么情况
以下结果为JDK1.8环境:
第一种情况

第2个线程执行完成了,size=12081
第5个线程执行完成了,size=12081
第3个线程执行完成了,size=12081
第4个线程执行完成了,size=12081
第1个线程执行完成了,size=12081
全部执行完成，size=12081

第二种情况

java.lang.ClassCastException: java.util.HashMap$Node cannot be cast to java.util.HashMap$TreeNode
    at java.util.HashMap$TreeNode.moveRootToFront(HashMap.java:1819)
    at java.util.HashMap$TreeNode.treeify(HashMap.java:1936)
    at java.util.HashMap$TreeNode.split(HashMap.java:2162)
    at java.util.HashMap.resize(HashMap.java:713)
    at java.util.HashMap.putVal(HashMap.java:662)
    at java.util.HashMap.put(HashMap.java:611)
    at com.cc.sf.hashMap.HashMapTest.lambda$null$0(HashMapTest.java:31)
    at java.lang.Thread.run(Thread.java:745)
java.lang.ClassCastException: java.util.HashMap$Node cannot be cast to java.util.HashMap$TreeNode
    at java.util.HashMap$TreeNode.moveRootToFront(HashMap.java:1819)
    at java.util.HashMap$TreeNode.treeify(HashMap.java:1936)
    at java.util.HashMap.treeifyBin(HashMap.java:771)
第2个线程执行完成了,size=2779
第5个线程执行完成了,size=9217
    at java.util.HashMap.putVal(HashMap.java:643)
    at java.util.HashMap.put(HashMap.java:611)
    at com.cc.sf.hashMap.HashMapTest.lambda$null$0(HashMapTest.java:31)
    at java.lang.Thread.run(Thread.java:745)
第4个线程执行完成了,size=16117
第1个线程执行完成了,size=16117
第3个线程执行完成了,size=16117
全部执行完成，size=16117

分析

1. size 变多了问题

我们的代码只执行了 put() 操作，看过前篇 HashMap源码分析，分析过源码，现在我们简单梳理下过程

看下源码 (JDK 1.8):

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // table为空 或者长度为0 先初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
     //将p赋值为对应桶位置的头结点
    //如果key对应的数组位置还是空着的 则直接new一个放进去
        if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // e为要插入的node
        Node<K,V> e; K k;
        // 如果头结点的hash 和key的hash一样  且key也一样 则该节点即为要插入的节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果该链表还是个红黑树 则按照红黑树的插入方法
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 正常链表
        else {
            // 死循环
            for (int binCount = 0; ; ++binCount) {
              // 是否为尾节点 是 则直接插入 并且退出循环
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 是否要转成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 不是尾节点 则 比对hash 和 key是一样 是 退出循环 e已经在上面赋值
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //p指向下一个节点
                p = e;
            }
        }
        // 如果e不为空 则替换e的value 并返回旧值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 是否触发扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

如果两个线程同时执行这个方法，且key都一样，则不管是哪种情况，都只会插入一个值，另外一个会被覆盖掉，但是最后的 ++size 都会执行到，所以虽然只插入了一个元素，但是却算多次插入。
有些读者可能会有疑问了，那实际元素到底是多没多呢？
答案是不确定。可能多了可能少了。
我们修改上面的例子 在最后加上打印出实际的元素总数:

AtomicInteger i= new AtomicInteger(0);
map.forEach((a,b)->i.incrementAndGet());
System.out.println("实际元素个数:"+i.get());

多次执行 搜集到如下两种情况

第2个线程执行完成了,size=14248
第3个线程执行完成了,size=14248
第1个线程执行完成了,size=14248
第4个线程执行完成了,size=14248
第5个线程执行完成了,size=14248
全部执行完成，size=14248
实际元素个数:9738

第1个线程执行完成了,size=12599
第4个线程执行完成了,size=13157
第5个线程执行完成了,size=16054
第2个线程执行完成了,size=16054
第3个线程执行完成了,size=16054
全部执行完成，size=16054
实际元素个数:13269

第一种比标准少了，第二种比标准多了。
真令人头大，怎么反复横跳呢？
不急，我们慢慢来，接着看扩容源码。

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 扩容再大 也不能大过最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 扩充为原来的2倍(左移 即为乘2)
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // threshold>0说明调用了设置该值的构造方法
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 初始化
    else { 
        // signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的resize上限
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 每个数组里面的Node链表都重新分配
        // 不是带着原下标 就是待在(原下标+oldCap)的下标
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 如果只链接一个节点，重新计算并放入新数组
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                    // 如果是红黑树 拆分处理
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { 
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // e.hash & oldCap，若为0则索引位置不变，不为0则新索引=原索引+旧数组长度
                        // 原索引
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

大概两步

1. 新建一个现有2倍长度的数组
2. 复制原数组里面的元素到新数组

比如第一个线程T1正在扩容，正在将原数组里的元素复制到新数组里面去，但是正好另一个线程T2插入一个key，T2当然直接插入到新数组里面去，里面的槽位大多数都是空的，因为T1才新创建，原数组的值T1还正在搬，会存在这种情况：T2判断了该key对应下标的table位置为null，正准备把这个值放进去的时候，T1先把原数组的值放进去，然后T2就把T1放进去的值覆盖了。

hashMap 并发问题

会变多的原因，应该跟红黑树有关，挖个坑，分享算法的时候补上。

报错的问题是因为已经转换成红黑树了，但是还是创建的链表节点。

头插法的死循环问题

应该都听说过JDK1.7 HashMap 因为链表拉链法使用头插法，会造成死循环问题。下面来一探究竟。
上源码：

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;
}
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);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    // 头插法，链表头部指向新的键值对
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

其实根源不是put元素的时候使用的头插入，而是扩容的时候，复制元素的时候，使用头插法复制：

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

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);
            // 将当前节点的 next 指向第一个节点
            e.next = newTable[i];
            // 将当前节点设置为第一个节点
            newTable[i] = e;
            e = next;
        }
    }
}

上面的代码应该都能看懂，核心就是后面加注释那那两句，遍历链表，复制到新数组使用的逆序插入，刷过算法题或者了解过的应该都知道，逆序打印一个链表。这样的操作在多线程环境下会造成死循环和数据丢失的问题。图解如下：

HashMap 扩容死循环

最后就形成循环链表，我们都知道遍历循环链表那就等同于死循环了。

总结

JDK1.8 HashMap 多线程环境下会存在转换异常，丢失数据，重复数据的问题
JDK1.7 HashMap 死循环，丢失数据的问题

后记

看到这里，不知道小伙伴都理解了没有，如果还存在疑惑，请在评论区提出。这是我自己的理解，自己作图，如果存在错误，也请指出，不胜感激。

量变引发质变，经常进步一点点，期待蜕变的自己。