## hashmap为什么线程不安全

hashmap为什么线程不安全

---

jdk1.7中线程不安全

  jdk1.7中造成线程不安全是因为在多线程的情况下扩容可能会导致出现环形链表或者数据丢失，那么是为什么呢，让我们深入源码探究

  问题出在HashMap的扩容函数中，根源在transfer函数中，jdk1.7中HashMap的transfer函数如下：

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);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

  如何理解该扩容函数呢？我们以单线程扩容为例说明，有如下HashMap需要扩容，我们所做的是，把数组长度扩充为两倍，然后把数据拷贝到新数组里，这里是一个双层循环，来对每一个下标的链表进行遍历，

这里我们一步一步往下走，临时变量e=1 next =2
接下来几行代码的意思其实就是为数据在新数组里找到他的下标，我们这里假设都存到下标2的位置

 if (rehash) {
 e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);

这里我们需要注意的是Jdk1.7采用的是头插法

e.next = newTable[i];
newTable[i] = e;
  e = next;

我们继续往下走，把e头插到下标为2的位置，e=next = 2；

我们继续下一次循环， next = e.next = 3 e = 2；把e头插到下标为2的位置，e=next=3

继续，next = e.next = null e = 3， 吧e头插到下标为2的位置，e=next=null退出循环。

我们可以看到，链表原来的顺序是1234，经过扩容复制之后，变成了4321，头插法把元素顺序颠倒了，这也是导致出现环形链表和丢失的原因，下面我们来看看多线程情况会出现的问题

扩容造成死循环

  假设这时有两个线程A和B，当他们发现需要扩容的时候，同时进行扩容操作，然而线程A在进行到第五行代码的时候发生了阻塞，此时e = 1，next = 2，然后线程b成功完成扩容操作，如下图

然后线程A恢复，开始继续扩容，hashmap的操作是内存可见的，所以此时旧数组已经不存在了，e = 1 ， next = 2，开始一步一步往下走，将e头插入数组，e = next = 2

进入下一步循环 next = e.next = 1 e = 2，将e头插入数组，e = next = 1；

进入下一步循环 next = e.next = null ，将e头插入数组， e = next = null 退出循环，由上一层可以知道 2.next = 1 形成环形链表，当轮循该链表时会产生死循环。

扩容造成数据丢失

  假设这时有两个线程A和B，当他们发现需要扩容的时候，同时进行扩容操作，然而线程A在进行到第五行代码的时候发生了阻塞，此时e = 1，next = 2，然后线程b成功完成扩容操作，如下图

然后线程A恢复，开始继续扩容，hashmap的操作是内存可见的，所以此时旧数组已经不存在了，e = 1 ， next = 2，开始一步一步往下走，将e头插入数组，e = next = 2

继续下一轮循环， next = e.next = null 将e头插入数组 e = next = null，退出循环

可以看到此时 3丢失了。

jdk1.8中线程不安全

---

  我们知道在jdk1.8中，对头插法进行了修改，采用尾插法，所以不会造成环形链表和数据丢失，那么在哪里会线程不安全呢，我们来看一下放入元素的put方法的源码

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null) // 如果没有hash碰撞则直接插入元素
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            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;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            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;
    }

注意第六行代码，如果没有产生hash碰撞会直接插入元素，如果这是线程A和线程B同时进行put操作，刚好hash值相等，但是是两条不等的数据，并且该位置没有数据，假设此时A还未插入数据时挂起，然后线程B正常执行，在该位置插入数据。此时线程A恢复，这个时候，线程A不需要进行hash判断了，他会直接往该位置插入元素，这时候，就会产生数据覆盖，线程不安全。