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);
    }
    }
    };
    }
    }
  1. 接上题,上面代码为什么会出现死循环?
    答:

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

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

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

  3. ConcurrentHashMap 是怎样支持原子复合操作的?
    答:

    • ConcurrentHashMap 还实现了一个接口 ConcurrentMap,接口定义了一些条件更新操作
    • 如果使用同步容器,调用方必须加锁,而 ConcurrentHashMap 将它们实现为了原子操作
    • 实际上,使用 ConcurrentHashMap,调用方也没有办法进行加锁,它没有暴露锁接口,也不使用 synchronized
  4. 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` 等**。
  1. ConcurrentHashMap 是为高并发设计的,具体怎么实现的呢
    答:

    • Java 7,主要有两点:

      • 分段锁
      • 读不需要锁
    • 同步容器使用 synchronized,所有方法竞争同一个锁;而 ConcurrentHashMap 采用分段锁技术,将数据分为多个段,而每个段有一个独立的锁。每一个段相当于一个独立的哈希表,分段的依据也是哈希值,无论是保存键值对还是根据键查找,都先根据键的哈希值映射到段,再在对应的哈希表上进行操作

    • 采用分段锁,可以大大提高并发度,多个段之间可以并行读写默认情况下,段是 16,不过,这个数字可以通过构造方法进行设置:public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel);
    • concurrencyLevel 表示估计的并行更新的线程个数,ConcurrentHashMap 会将该数据转换为 2 的整数次幂,比如 14 转换为 1625 转换为 32
    • 在对每个段的数据进行读写时,ConcurrentHashMap 也不是简单地使用锁进行同步,内部使用了 CAS。对一些写采用原子方式的方法,实现比较复杂。实现的效果是,对于写操作,需要获取锁,不能并行,但是读操作可以,多个读可以并行,写的同时也可以读,这使得 ConcurrentHashMap 的并行度远高于同步容器
    • Java 8ConcurrentHashMap 的实现进一步做了优化。首先,HashMap 的改进类似,在哈希冲突比较严重的时候,会将单向链表转化为平衡的排序二叉树,提高查找的效率;其次,锁的粒度进一步细化了,以提高并行性,哈希表数组中的每个位置(指向一个单链表或树)都有一个单独的锁,具体比较复杂。
  2. 怎样理解 ConcurrentHashMap 的迭代安全?
    答:

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

    • ConcurrentHashMap 的迭代器创建后,就会按照哈希表结构遍历每个元素,但在遍历过程中,内部元素可能发生变化。如果变化发生在已遍历过的部分,迭代器就不会反映出来,而如果变化发生在未遍历过的部分,迭代器就会发现并反映出来,这就是弱一致性
    • 类似的情况还会出现在 ConcurrentHashMap 的另一个方法:public void putAll(Map<? extends K, ? extends V> m)(批量添加 m 中的键值对到当前 Map)。该方法并非原子操作,而是调用 put() 方法逐个元素进行添加的,在该方法没有结束的时候,部分修改效果就会体现出来。
  4. Java 中有并发版本的 HashSet 吗?
    答:没有,但可以通过 Collections.newSetFromMap 方法基于 ConcurrentHashMap 创建一个。