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

墨蓝 2022-03-19 11:50 77阅读 0赞

### 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可以正常修改。

### 数据结构-跳表 ###

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