HashMap为什么线程不安全

线程不安全的HashMap

HashMap 在日常开发中是十分常见的，也是我们使用 Map 存储键值对的首选类，关于 HashMap 的源码分析可以看这里。或者需要快速预览 HashMap 结构也可以看这里。由于从 JDK 1.8 开始对 HashMap 进行了优化，增加了红黑树这种数据结构，所以 JDK 1.8 的 HashMap 较为复杂，这里为了简化分析，采用 JDK 1.7 版本版本的 HashMap 进行举例说明。

HashMap 线程不安全主要体现在两个方面：

多线程环境下对键值对进行修改操作（put 和 remove）会出现丢失更新问题
多线程环境下进行 resize 扩容操作形成环形链表，导致 get 操作出现死循环，JDK 1.8 已经修复该问题

第一种情况下，我们可以先看一下 JDK 1.7 下 HashMap 的源码中的 put 操作：

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    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;
}

在 put 操作中有一个 addEntry 方法，这是核心方法，其源码如下：

void addEntry(int hash, K key, V value, int bucketIndex) {
    //获取头节点，此处在多线程环境下不安全
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

现在假如 A 线程和 B 线程同时对同一个数组位置调用 addEntry，两个线程会同时得到现在的头结点，然后 A 写入新的头结点之后，B 也写入新的头结点，那 B 的写入操作就会覆盖 A 的写入操作造成 A 的写入操作丢失。

同理可以看一下 remove 操作：

public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

final Entry<K,V> removeEntryForKey(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;

    while (e != null) {
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            modCount++;
            size--;
            if (prev == e)
                table[i] = next;
            else
                prev.next = next;
            e.recordRemoval(this);
            return e;
        }
        prev = e;
        e = next;
    }

    return e;
}

当多个线程同时操作同一个数组位置的时候，也都会先取得现在状态下该位置存储的头结点，然后各自去进行计算操作，之后再把结果写会到该数组位置去，其实写回的时候可能其他的线程已经就把这个位置给修改过了，就会覆盖其他线程的修改，也就是丢失修改问题。

第二种情况中，我们可以看一下 resize 操作的源码：

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

/**
 * Transfers all entries from current table to newTable.
 */
// 关键在于这个transfer方法，这个方法的作用是将旧hash表中的元素rehash到新的hash表中
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) { // table变量即为旧hash表
        while(null != e) {
            // #1
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // 用元素的hash值计算出这个元素在新hash表中的位置
            int i = indexFor(e.hash, newCapacity);
            // #2
            e.next = newTable[I];
            // #3
            newTable[i] = e;
            // #4
            e = next;
        }
    }
}

假设线程 1 (t1)和线程 2 (t2)同时 resize，两个线程 resize 前，两个线程及 HashMap 的状态如下：

堆内存中的 HashMap 对象中的 table 字段指向旧的 hash 表，其中 index 为 7 的位置有两个元素，我们以这两个元素的 rehash 为例，看看循环链表是如何形成的。

线程 1 和线程 2 分别 new 了一个 hash 表，用 newTable 字段表示。

Step1: t2 执行完 #1 代码后，CPU且走执行 t1，并且 t1 执行完成

这里可以根据上图推算一下，此时状态如下：

用 t2.e 表示线程 2 中的局部变量 e，t2.next 同理。

Step2: t2 继续向下执行完本次循环

Step3: t2 继续执行下一次循环

Step4: t2继续下一次循环，循环链表出现

然后我们在这个时候进行一个 get 操作，get 方法源码如下：

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    // 遍历链表
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        // 假设这里条件一直不成立
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

由上图可知，for 循环中的 e = e.next永远不会为空，那么，如果 get 一个在这个链表中不存在的 key 时，就会出现死循环了。更加具体的细节可以见参考文章[2]。

实现线程安全

那么如何在多线程环境下使用线程安全的 HashMap 呢？

可以有一下解决方法：

使用 Collections.synchronizedMap(Mao<K,V> m) 方法把 HashMap 变成一个线程安全的 Map
使用 Hashtable、ConcurrentHashMap 这两个线程安全的 Map