JDK1.8源码分析：ConcurrentSkipListMap-有序并发容器Map

TreeMap，ConcurrentSkipListMap和ConcurrentSkipListSet

• 在集合框架中提供了TreeMap来实现Map的key有序，TreeMap不是线程安全的，如果多个线程对TreeMap进行结构性修改，如添加或删除操作，则需要进行同步。而在JUC包中提供了ConcurrentSkipListMap来实现一个并发、线程安全版本的TreeMap。
• TreeMap是基于红黑树实现的，而ConcurrentSkipListMap是基于跳表实现的线程安全的key有序Map。
• ConcurrentSkipListSet是基于ConcurrentSkipListMap实现的线程安全有序Set。在JUC包中并没有提供与HashSet对应的线程安全的ConcurrentHashSet，所以如果需要线程安全Set，则可以使用ConcurrentSkipListSet。ConcurrentSkipListSet内部包含一个ConcurrentSkipListMap引用，然后使用ConcurrentSkipListMap的putIfAbsent来添加数据，从而保证不重复添加数据。
• 和ConcurrentHashMap一样，ConcurrentSkipListMap的key和value也都不能是null。

常量操作时间复杂度和线程安全性保证

• ConcurrentSkipListMap由于是基于跳表实现的，而跳表是一种类似于树的链表，相关读写操作类似于对树节点进行操作，相关读写操作都是O(logN)复杂度的，包括put，get，containsKey，remove等方法。由于在多线程环境中，可能存在多个线程对该Map进行并发修改，所以如果需要获取当前Map的节点个数，即size方法的实现，则需要遍历整个Map或者说整个跳表，故实现复杂度为O(N)的，同时这个操作也不是原子操作，即在遍历统计过程中，其他线程可能会继续增删节点，所以结果不能保证完全准确。其他批量操作，包括putAll，equals，toArray，containsValue，clear，也不是原子操作的，主要原因是如果批量操作要完全实现互斥访问，则需要锁住这个跳表，这样会影响操作，降低性能。
• ConcurrentSkipListMap的put，get等操作，将键值对插入到Map，或者从Map中获取指定key对应的value时，在内部对应的操作是往跳表插入节点，从跳表查找指定key对应的节点。针对这些操作，在内部实现中主要是通过UNSAFE提供的CAS硬件级别的原子操作和自旋来实现线程安全。
• 所以如果没有key有序的需求，对于线程安全Map，一般使用ConcurrentHashMap性能更高，因为ConcurrentHashMap相关get，put，containsKey方法时间复杂度为O(1)的。

key的有序性

• ConcurrentSkipListMap主要是根据key来排序的，默认为自然序，如字符串的字典序，也可以在构造函数中提供自定义Comparator接口实现，提供自定义比较器来实现key的排序。所有的构造函数如下：

  // comparator为null，使用key的自然序，如字典序
  public ConcurrentSkipListMap() {
      this.comparator = null;
      initialize();
  }
  
  // 自定义comparator来实现key的排序
  public ConcurrentSkipListMap(Comparator<? super K> comparator) {
      this.comparator = comparator;
      initialize();
  }
  
  // 将指定map通过ConcurrentSkipListMap来包装，
  // 从而实现该map的key的排序和该map的线程安全性
  public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
      this.comparator = null;
      initialize();
      putAll(m);
  }
  
  // 将指定的有序map作为参数，内部使用该有序map的comparator，
  // 同时为该map提供线程安全特性
  public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
      this.comparator = m.comparator();
      initialize();
      buildFromSorted(m);
  }
  

迭代器

• ConcurrentSkipListMap的迭代器，由于是基于快照实现的，故是弱一致性的。同时迭代器遍历所返回的每个Map节点元素Map.Entry，即键值对，由于是基于快照实现的，不支持通过Entry.setValue来修改值。在性能方法，升序key的迭代器性能优于降序key。

  final class EntryIterator extends Iter<Map.Entry<K,V>> {
      public Map.Entry<K,V> next() {
          Node<K,V> n = next;
          V v = nextValue;
          advance();
          // 节点键值对快照，Immutable不可修改，即该Map.Entry不能修改
          return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
      }
  }
  

使用示例

• TreeMap，ConcurrentHashMap和ConcurrentSkipListMap的key的有序性、迭代器、Map.Entry修改value：

  /**
   * @author xyz
   * @date 16/2/2019 22:33
   * @description:
   */
  public class ConcurrentSkipListMapTest {
  
      public static void main(String[] args) {
          System.out.println("===TreeMap===");
          Map treeMap = buildNormalSortedMap();
          // 先打印
          printMapSortedKeyValue(treeMap);
          // 通过Map.Entry的setValue修改
          Iterator<Map.Entry<String, Object>> iterator = treeMap.entrySet().iterator();
          if (iterator.hasNext()) {
              modifyValueByMapEntry(iterator.next());
          }
          // 重新打印
          printMapSortedKeyValue(treeMap);
  
          System.out.println("===ConcurrentHashMap===");
          Map concurrentHashMap = buildConcurrentHashMap();
          printMapSortedKeyValue(concurrentHashMap);
          Iterator<Map.Entry<String, Object>> iterator1 = concurrentHashMap.entrySet().iterator();
          if (iterator1.hasNext()) {
              modifyValueByMapEntry(iterator1.next());
          }
          printMapSortedKeyValue(concurrentHashMap);
  
          System.out.println("===ConcurrentSkipListMap===");
          Map concurrentSortedMap = buildConcurrentSortedMap();
          printMapSortedKeyValue(concurrentSortedMap);
          Iterator<Map.Entry<String, Object>> iterator2 = concurrentSortedMap.entrySet().iterator();
          if (iterator2.hasNext()) {
              modifyValueByMapEntry(iterator2.next());
          }
          printMapSortedKeyValue(concurrentSortedMap);
      }
  
      public static ConcurrentSkipListMap<String, Object> buildConcurrentSortedMap() {
          ConcurrentSkipListMap<String, Object> map = new ConcurrentSkipListMap();
          initMap(map);
          return map;
      }
  
  
      public static TreeMap<String, Object> buildNormalSortedMap() {
          TreeMap<String, Object> map = new TreeMap<>();
          initMap(map);
          return map;
      }
  
      public static ConcurrentHashMap<String, Object> buildConcurrentHashMap() {
          ConcurrentHashMap<String, Object> map = new ConcurrentHashMap<>();
          initMap(map);
          return map;
      }
  
  
      private static void initMap(Map<String, Object> map) {
          List<String> unSortedKeys = Arrays.asList("1key", "3key", "2key", "4key");
          for (String key : unSortedKeys) {
              map.put(key, key);
          }
      }
  
      // 打印map的key，value
      public static void printMapSortedKeyValue(Map<String, Object> map) {
          for (Map.Entry entry : map.entrySet()) {
              System.out.println(entry.getKey() + ":" + entry.getValue());
          }
      }
  
      // 通过Map.Entry的setValue修改值
      public static void modifyValueByMapEntry(Map.Entry<String, Object> entry) {
          entry.setValue("hello world");
          System.out.println("Map.Entry modify ok");
      }
  }
  

• 执行结果如下：

  ===TreeMap===
  1key:1key
  2key:2key
  3key:3key
  4key:4key
  Map.Entry modify ok
  1key:hello world
  2key:2key
  3key:3key
  4key:4key
  ===ConcurrentHashMap===
  4key:4key
  3key:3key
  2key:2key
  1key:1key
  Map.Entry modify ok
  4key:hello world
  3key:3key
  2key:2key
  1key:1key
  ===ConcurrentSkipListMap===
  1key:1key
  2key:2key
  3key:3key
  4key:4key
  Exception in thread "main" java.lang.UnsupportedOperationException
  	at java.util.AbstractMap$SimpleImmutableEntry.setValue(AbstractMap.java:797)
  	at com.yzxie.easy.log.web.ConcurrentSkipListMapTest.modifyValueByMapEntry(ConcurrentSkipListMapTest.java:79)
  	at com.yzxie.easy.log.web.ConcurrentSkipListMapTest.main(ConcurrentSkipListMapTest.java:38)
  
  Process finished with exit code 1
  

• 可以看出ConcurrentSkipListMap和TreeMap的key都是有序的，ConcurrentSkipListMap在使用Map.Entry的setValue修改value时，抛异常，而ConcurrentHashMap和TreeMap可以正常修改。

数据结构-跳表

• 跳表相关数据结构的特性在之后详细分析。