HashMap为什么线程不安全

HashMap为什么线程不安全

请注意,本文编写于  1,074  天前,最后修改于  1,074  天前,其中某些信息可能已经过时。

线程不安全的HashMap

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

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

  1. 多线程环境下对键值对进行修改操作(put 和 remove)会出现丢失更新问题
  2. 多线程环境下进行 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

参考文章

  1. HashMap为什么是线程不安全的?
  2. 不正确地使用HashMap引发死循环及元素丢失

本文由 Sanarous 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可,转载前请务必署名
本文链接:https://bestzuo.cn/posts/hashmap-thread-unsafe.html
最后更新于:2019-07-18 18:46:59

切换主题 | SCHEME TOOL