0%

Java 并发容器(二):ConcurrentHashMap

1. ConcurrentHashMap 的特点

  • ConcurrentHashMapHashMap并发版本,与 HashMap 相比,有如下特点:
    • 并发安全
    • 直接支持一些原子复合操作
    • 支持高并发,读操作完全并行,写操作支持一定程度的并行。
    • 与同步容器 Collections.synchronizedMap 相比,迭代不用加锁,不会抛出 ConcurrentModificationException 异常。
    • 弱一致性

2. 写一个 HashMap 死循环 Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//HashMap 不是并发安全的,在并发更新的情况下,HashMap 可能出现死循环,占满 CPU
public static void unsafeConcurrentUpdate() {
final Map<Integer, Integer> map = new HashMap<> ();
for(int i=0; i<1000; i++) {
Thread t = new Thread() {
Random rnd = new Random();
@Override
public void run() {
for(int i=0; i<1000; i++) {
map.put(rnd.nextInt(), 1);
}
}
};
}
}

3. 接上题,上面代码为什么会出现死循环

  • 死循环出现在多个线程同时扩容哈希表的时候,不是同时更新一个链表的时候,那种情况可能出现更新丢失,但不会死循环,具体过程比较复杂。
  • 关于 Java 7 的解释可以参考:http://coolshell.cn/articles/9606.html
  • Java 8 对 HashMap 的实现进行了大量优化,减少了死循环的可能,但在扩容的时候还是可能有死循环。

4. 接上题,怎样避免产生死循环

  • 使用 Collections.synchronizedMap 方法生成一个同步容器,替换第一行代码为:final Map<Integer, Integer> map = Collections.synchronizedMap(new HashMap<Integer, Integer> ());。同步容器有两个问题:

    • 每个方法都需要同步,支持的并发度比较低。
    • 对于迭代和复合操作,需要调用方加锁,使用比较麻烦,且容易忘记。
  • ConcurrentHashMap 没有这些问题,它同样实现了 Map 接口,也是基于哈希表实现的,替换第一行代码为:final Map<Integer, Integer> map = new ConcurrentHashMap<> ();

5. ConcurrentHashMap 是怎样支持原子复合操作的

  • ConcurrentHashMap 还实现了一个接口 ConcurrentMap,接口定义了一些条件更新操作。
  • 如果使用同步容器,调用方必须加锁,而 ConcurrentHashMap 将它们实现为了原子操作
  • 实际上,使用 ConcurrentHashMap,调用方也没有办法进行加锁,它没有暴露锁接口,也不使用 synchronized

6. ConcurrentMap 接口的定义是

  • Java 7 中的具体定义:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public interface ConcurrentMap<K, V> extends Map<K, V> {
    //条件更新,如果 map 中没有 key,设置 key 为 value,返回原来 key 对应的值
    //如果没有,返回 null
    V putIfAbsent(K key, V value);

    //条件删除,如果 Map 中有 key,且对应的值为 value,则删除,如果删除了,返回 true
    //否则返回 false
    boolean remove(Object key, Object value);

    //条件替换,如果 Map 中有 key,且对应的值为 oldValue,则替换为 newValue
    //如果替换了,返回 ture,否则 false
    boolean replace(K key, V oldValue, V newValue);

    //条件替换,如果 Map 中有 key,则替换值为 value,返回原来 key 对应的值
    //如果原来没有,返回 null
    V replace(K key, V value);
    }
  • Java 8 增加了几个默认方法,包括 getOrDefault()forEach()computeIfAbsent()merge() 等。

7. ConcurrentHashMap 是为高并发设计的,具体怎么实现的呢

  • 在 Java 7 中,主要有两点:

    • 分段锁
    • 读不需要锁
  • 同步容器使用 synchronized,所有方法竞争同一个锁;而 ConcurrentHashMap 采用分段锁技术:

    • 将数据分为多个段,而每个段有一个独立的锁
    • 每一个段相当于一个独立的哈希表,分段的依据也是哈希值,无论是保存键值对还是根据键查找,都先根据键的哈希值映射到段,再在对应的哈希表上进行操作。
  • 采用分段锁,可以大大提高并发度,多个段之间可以并行读写。默认情况下,段是 16 个,不过,这个数字可以通过构造方法进行设置:public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel);

    • concurrencyLevel 表示估计的并行更新的线程个数,ConcurrentHashMap 会将该数据转换为 2 的整数次幂,比如 14 转换为 16,25 转换为 32。
    • 在对每个段的数据进行读写时,ConcurrentHashMap 也不是简单地使用锁进行同步,内部使用了 CAS。对一些写采用原子方式的方法,实现比较复杂。
    • 实现的效果是,对于写操作,需要获取锁,不能并行;但是读操作可以,多个读可以并行,写的同时也可以读,这使得 ConcurrentHashMap 的并行度远高于同步容器。
  • Java 8 对 ConcurrentHashMap 的实现进一步做了优化。

    • 首先,与 HashMap 的改进类似,在哈希冲突比较严重的时候,会将单向链表转化为平衡的排序二叉树,提高查找的效率。
    • 其次,锁的粒度进一步细化了,以提高并行性,哈希表数组中的每个位置(指向一个单链表或树)都有一个单独的锁,具体比较复杂。

8. 怎样理解 ConcurrentHashMap 的迭代安全

  • 使用同步容器,在迭代中需要加锁,否则可能会抛出 ConcurrentModificationException 异常。
  • ConcurrentHashMap 没有这个问题,在迭代器创建后,在迭代过程中,如果另一个线程对容器进行了修改,迭代会继续,不会抛出异常

9. 怎样理解 ConcurrentHashMap 的弱一致性

  • ConcurrentHashMap迭代器创建后,就会按照哈希表结构遍历每个元素,但在遍历过程中,内部元素可能发生变化。

    • 如果变化发生在已遍历过的部分,迭代器就不会反映出来。
    • 而如果变化发生在未遍历过的部分,迭代器就会发现并反映出来,这就是弱一致性
  • 类似的情况还会出现在 ConcurrentHashMap 的另一个方法:public void putAll(Map<? extends K, ? extends V> m)(批量添加 m 中的键值对到当前 Map)该方法并非原子操作,而是调用 put() 方法逐个元素进行添加的,在该方法没有结束的时候,部分修改效果就会体现出来。

10. Java 中有并发版本的 HashSet 吗

  • 没有
  • 但可以通过 Collections.newSetFromMap 方法基于 ConcurrentHashMap 创建一个。
-------------------- 本文结束感谢您的阅读 --------------------