Java 并发容器（二）：ConcurrentHashMap

1. ConcurrentHashMap 的特点

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

2. 写一个 HashMap 死循环 Demo

//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 中的具体定义

  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 创建一个