在一次面试经验中，被问及了ConcurrentHashMap，当时说的不好，回来翻书、上网总结了点东西，供大家学习和交流，话说面试真是可以学到一些东西，好了闲话少说，进入正题吧。

本文使用的jdk环境为1.7.0_67

1.多线程环境下的下HashMap为什么会导致程序死循环

众所周知

在多线程的环境，HashMap的put操作会导致程序死循环，例如如下代码：

/**
 * @Description: HashMap出现死循环.
 * @Author: ZhaoWeiNan .
 * @CreatedTime: 2017/6/7 .
 * @Version: 1.0 .
 */
public class Demo1 {

    public static void main(String[] args){

        final Map<String,String> map = new HashMap<>();
        //开启10000个线程，在map里面put值
        for (int i = 0 ; i < 10000 ; i ++){
            new Thread(new Runnable() {
                @Override
                public void run() {
                    map.put(UUID.randomUUID().toString(),"");
                }
            }).start();
        }
    }
}

很明显程序进入了死循环，cpu利用率一直高居不下，真希望买的股票是这个状态

分析原因

HashMap详细的原理就不给大家标示，大家可以去百度看看，以后有时间在为大家总结，这里简单说一下。
HashMap是由数组和链表组成的，贴一点HashMap的源码：

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
   //Entry<K,V>组成的数组table
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

//Entry<K,V>有以下属性
static class Entry<K,V> implements Map.Entry<K,V> {
        //key 键
        final K key;
        //value 值
        V value;
        //链表元素的尾，指向下一个元素
        Entry<K,V> next;
        //由hash算法得出的hash值
        int hash;

当加入元素时候，会使用hash算法算出这个key在table中的索引，然后看table该索引上是否存在元素，如果不存在，把该Entry<K,V>插入到table的这个索引位置上，如果存在元素，就说明发生了冲突，然后就从table该索引位置上的节点为头的链表上遍历比较，如果key的hash值和链表中节点的hash相等，并且key相等，就把value存到链表元素的value中，把原来的value返回出来，如果没有相等的，就在链表的最末端的节点后面新加一个节点。

 public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        //通过hash算法计算key的hash，hash算法源码就不给出了
        int hash = hash(key);
        //通过算出的hash值，算出key在数组table中的索引i
        int i = indexFor(hash, table.length);
        //遍历链表节点，去比较hash和key与节点 e.key 是否相等
        for (HashMap.Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                //如果有相等的节点，把 value 赋值到节点的value上，返回原来的节点e的value
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        //没有冲突或者相等的节点就新加一个节点
        addEntry(hash, key, value, i);
        return null;
    }

分析addEntry方法：

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            //当size大于初始化的threshold的时候，需要调用resize方法扩容
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

分析扩容方法resize,该方法主要做了扩容，并且创建了个新的Entry<K,V>数组table,并且调用transfer方法把老的数组table中的元素转存到新的数组table中去：

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方法，把老数组中的元素转存到新数组中去
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

再分析转存方法transfer，在这有循环，有链表的next节点赋值，可以猜测是因为单链表形成了环造成的死循环

void transfer(Entry[] newTable, boolean rehash) {
        //把旧的数据转存到新的table中
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                //在这有循环，有链表的next节点赋值，
                Entry<K,V> next = e.next;         //(1)
                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;
            }
        }
    }

分析执行过程：

//假设map只能放置两个元素，其中的threshold为1
Map<Integer,String> map = new HashMap<>(2);
//并且为了方便分析，
//假设hashMap，计算索引的方法为偶数的index为0，奇数的index为1
//现在添加两个元素
map.put(1,"A");
map.put(3,"B");

那么，现在map的存储情况如下：

画工粗糙，请见谅

当我们再次put 一组数据的时候，map.put(2,"C")时，由于计算出索引是0，所以添加的时候需要扩容，此时如果在多线程环境下，假设：线程1执行到transfer方法(1)位置处，线程2获得了cpu执行权，线程2进行了扩容，执行了转存方法transfer把旧的table变成新的table（在线程2的私有栈中）吗，在写到内存中

//先获取table中的元素e
    for (Entry<K,V> e : table) {
        while(null != e) {
            //进入while循环，获取节点e的next节点，直到next节点为null
            //循环结束
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            //计算出e节点在新table中的索引
            int i = indexFor(e.hash, newCapacity);
            //把节点e转存到新table中
            //冲突链表转存的方式为头插法
            //即的节点e的next节点作为节点e的头
            //换种方式讲，在新的table中，节点e变成了next
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }

执行过程如图：

画工粗糙请见谅

此时，线程1获取cpu执行权，按照上述过程进行数据转存执行过程如下，第一次进入循环中：

while(null != e) {
            //第一次进入循环时
            /*假设此时线程1读取的线程1栈中的数据
            冲突链的结构还是 k:1 v:A(e) -> k:3 v:B(next) -> null
            k:1 v:A 为当前节点e,e.next为节点k:3 v:B,节点k:3 v:B的next为null
            */
            Entry<K,V> next = e.next;
            //next 为 节点k:3 v:B
            ......
        }

第二次进入循环中：

for (Entry<K,V> e : table) {
        while(null != e) {
            //第二次进入循环
            /*假设此时线程1读取的线程是线程2写入到内存中的数据
              此时，节点e为 k:3 v:B，但是线程2中节点e k:3 v:B的next
              指向了节点 k:1 v:A，所以获取的next节点不为空，
              循环没有结束，
              其实，冲突链已经成了环，所以while无法结束，程序陷入了死循环。
            */
            Entry<K,V> next = e.next;
            ......
        }
    }

根据上述分析，HashMap在多线程情况下，put的时候，扩容条用转存方法transfer时，冲突链可能会形成环，导致while循环无法结束，所以导致文章开头所描述的情形，创建一万个线程，每个线程put一个随机UUID，执行过程中，有时会发生死循环的现象。
欢迎大家来交流，指出文中一些说错的地方，有错误的地方希望大家多多提出来，让我加深认识。
ConcurrentHashMap的实现原理与使用，放到下几篇文章里面说吧。
谢谢大家！