Java 线程总结(九)

Java 线程总结(九) —— ConcurrentHashMap

1、ConcurrentHashMap，它是 HashMap 的并发版本，与 HashMap 相比，它有如下特点：

并发安全。

直接支持一些原子复合操作。

支持高并发、读操作完全并行、写操作支持一定程度的并行。

与同步容器 Collections.synchronizedMap 相比，迭代不用加锁，不会抛出 ConcurrentModificationException。

弱一致性。

2、HashMap 不是并发安全的，在并发更新的情况下，HashMap 的链表结构可能形成环，出现死循环，占满 CPU。死循环出现在多个线程同时扩容哈希表的时候，不是同时更新一个链表的时候，那种情况可能会出现更新丢失，但不会死循环。具体参考 Java HashMap 的死循环。

使用 Collections.synchronizedMap 方法可以生成一个同步容器，可以避免该问题。在 Java 中，HashMap 还有一个同步版本 Hashtable，它与使用 synchronizedMap 生成的 Map 基本是一样的，也是在每个方法调用上加了 synchronized。然而同步容器存在以下问题：

每个方法都需要同步，支持的并发度比较低。

对于迭代和复合操作，需要调用方加锁，使用比较麻烦，且容易忘记。

3、ConcurrentHashMap 没有以上那些问题，它同样实现了 Map 接口，也是基于哈希表实现的。除了 Map 接口，ConcurrentHashMap 还实现了一个接口 ConcurrentMap，接口定义了一些条件更新操作。

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

如果使用同步容器，调用方必须加锁，而 ConcurrentMap 将它们实现为了原子操作。实际上，使用 ConcurrentMap，调用方也没有办法进行加锁，它没有暴露锁接口，也不使用 synchronized。

4、ConcurrentHashMap 是为高并发设计的，其主要思路有两点：

分段锁

读不需要锁

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

采用分段锁，可以大大提高并发度，多个段之间可以并行读写。默认情况下，段是 16个，不过，这个数字可以通过构造方法进行设置:
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)
concurrencyLevel 表示估计的并行更新的线程个数，ConcurrentHashMap 会将该数转换为2的整数次幂，比如 14 转换为 16，25 转换为 32。

在对每个段的数据进行读写时，ConcurrentHashMap 也不是简单的使用锁进行同步，内部使用了 CAS、对一些写采用原子方式，实现比较复杂，实现的效果是，对于写操作，需要获取锁，不能并行，但是读操作可以，多个读可以并行，写的同时也可以读，这使得 ConcurrentHashMap 的并行度远远大于同步容器。

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

但是迭代器是否会反映别的线程的修改，就需要视情况而定了。这是因为 ConcurrentHashMap 的弱一致性。类似的情况还会出现在 ConcurrentHashMap 的另一个方法：public void putAll(Map<? extends K, ? extends V> m) 该方法并非原子操作，而是调用 put 方法逐个元素进行添加的，在该方法没有结束的时候，部分修改效果就会体现出来。

6、ConcurrentHashMap 的弱一致性
ConcurrentHashMap 的迭代器创建后，就会按照哈希表结构遍历每个元素，但在遍历过程中，内部元素可能会发生变化，如果变化发生在已遍历过的部分，迭代器就不会反映出来，而如果变化发生在未遍历过的部分，迭代器就会发现并反映出来，这就是弱一致性。

7、ConcurrentHashMap 通过分段锁、CAS 等技术实现了高并发；实现了 ConcurrentMap 接口，支持原子条件更新操作；不会抛出 ConcurrentModificationException，实现了弱一致性。

8、Java 中没有并发版的 HashSet，但可以通过 Collections.newSetFromMap 方法基于 ConcurrentHashMap 构建一个。HashMap/HashSet 基于哈希，不能对元素排序，对应的可排序的容器类是 TreeMap/TreeSet，并发包中可排序的对应版本不是基于树，而是基于 Skip List（跳跃表）的，类分别是 ConcurrentSkipListMap 和 ConcurrentSkipListSet。

参考博客

Java编程的逻辑 - ConcurrentHashMap