HashMap同步问题

一、HahMap 的同步问题

    我们都知道 HashMap 是线程不安全的，多线程环境下，会造成数据脏读，其实 HashMap 还有可能发生死循环（循环链表），从而导致内存，CPU 飙升（100%）的情况，下面我们就来分析一下：

该问题的出现主要是 resize() 方法造成的，下面是  resize() 核心代码：

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

resize()方法的本质就是创建新的Entry数组，将原Map中的元素重新计算位置，加入到新的Map中。虽然死锁的成因是扩充时调用resize()方法，但真正的产生是发生在倒数第三行的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;
                //计算节点在新的Map中的位置
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

下面是出现该问题的大致流程（图片来自大神的博客）

1、假设hash算法就是简单的用key mod Entry数组的长度。注意e和next的指向，当并发resize()时，这两个指针对于死锁产生起着至关重要的作用。根据方法执行情况，原Map中的链表元素在新的Map中将顺序颠倒，如上图所示，经过一次resize()后key为7的节点排在了key为3的节点之前。
2、并非所有情况下都会产生死锁，这也需要线程在某一时刻的巧合。下面模拟死循环产生的过程：

do {
  Entry<K,V> next = e.next; //假设线程 A 执行至此被挂起，执行线程 B
  int i = indexFor(e.hash, newCapacity);
  e.next = newTable[i];
  newTable[i] = e;
   e = next;
} while (e != null);

    

假设现在有两个线程，线程A 和 线程B， 线程A因为某些原因被挂起（在代码的 Entry<K,V> next = e.next; 这一行挂起），此时记录 e指向key为3的节点，next指向key为7的节点。线程B 正常执行，执行结果如下：

然后，线程A被唤醒，在线程A的空间中 e指向key为3的节点，next指向key为7的节点，开始执行：

    a)执行：newTalbe[i] = e

    b)执行：e = next，e指向了key(7)

     下一次循环 next = e.next 的结果就是 next指向key(3)

线程A继续执行，执行结果如下：

再执行 e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 于是环形链表就这样出现了。

对于多线程导致 HashMap 出现死循环的问题，最好的办法就是在高并发的情况下规避使用不安全的HashMap，方案如下：

1.使用HashTable和调用Collections工具类的synchronizedMap()方法达到线程安全的目的。但由于synchronized是串行执行，在访问量很大的情况下效率很低，不推荐使用。

2.使用JUC包下的ConcurrentHashMap类，这个类很好的解决了多线程环境下的并发问题

JDK1.8 之后改进了 HashMap ，当链表的长度超过 8 时，就会将链表转为 红黑树，同时改成了尾插，理论上不会出现环形链表。但是还是会有脏读的情况出现（未测试）。为了避免不必要的异常，在高并发的情况还是使用 ConcurrentHashMap。