疫苗：Java HashMap的死循环

　　在淘宝内网里看到同事发了贴说了一个CPU被的线上故障，并且这个事发生了很多次，原因是在Java语言在并发情况下使用HashMap造成Race Condition，从而导致死循环。这个事情我4、5年前也经历过，本来觉得没什么好写的，因为Java的HashMap是非线程安全的，所以在并发下必然出现问题。但是，我发现近几年，很多人都经历过这个事（在网上查“HashMap Infinite Loop”可以看到很多人都在说这个事）所以，觉得这个是个普遍问题，需要写篇疫苗文章说一下这个事，并且给大家看看一个完美的“Race Condition”是怎么形成的。

　　问题的症状

　　从前我们的Java代码因为一些原因使用了HashMap这个东西，但是当时的程序是单线程的，一切都没有问题。后来，我们的程序性能有问题，所以需要变成多线程的，于是，变成多线程后到了线上，发现程序经常占了的CPU，查看堆栈，你会发现程序都Hang在了HashMap.get（）这个方法上了，重启程序后问题消失。但是过段时间又会来。而且，这个问题在测试环境里可能很难重现。

　　我们简单的看一下我们自己的代码，我们知道HashMap被多个线程操作。而Java的文档说HashMap是非线程安全的，应该用ConcurrentHashMap。

　　但是在这里我们可以来研究一下原因。

　　Hash表数据结构

　　我需要简单地说一下HashMap这个经典的数据结构。

　　HashMap通常会用一个指针数组（假设为table[]）来做分散所有的key，当一个key被加入时，会通过Hash算法通过key算出这个数组的下标i，然后把这个插到table[i]中，如果有两个不同的key被算在了同一个i，那么叫冲突，又叫碰撞，这样会在table[i]上形成一个链表。

　　我们知道，如果table[]的尺寸很小，比如只有2个，如果要放进10个keys的话，那么碰撞非常频繁，于是一个O（1）的查找算法，变成了链表遍历，性能变成了O（n），这是Hash表的缺陷（可参看《Hash Collision DoS 问题》）。

　　所以，Hash表的尺寸和容量非常的重要。一般来说，Hash表这个容器当有数据要插入时，都会检查容量有没有超过设定的thredhold，如果超过，需要增大Hash表的尺寸，但是这样一来，整个Hash表里的无素都需要被重算一遍。这叫rehash，这个成本相当的大。

　　相信大家对这个基础知识已经很熟悉了。

　　HashMap的rehash源代码

　　下面，我们来看一下Java的HashMap的源代码。

　　Put一个Key，Value对到Hash表中：

    public V put(K key， V value)
    {
        ......
        //算Hash值
        int hash = hash(key.hashCode());
        int i = indexFor(hash， table.length);
        //如果该key已被插入，则替换掉旧的value （链接操作）
        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++;
        //该key不存在，需要增加一个结点
        addEntry(hash， key， value， i);
        return null;
    }