这篇文章讨论了java.util.concurrent包中的ConcurrentSkipListMap类以及该类实现的接口ConcurrentNavigableMap。

Java中的ConcurrentSkipListMap

ConcurrentSkipListMap是一个线程安全的可伸缩Map，以排序方式存储其元素。默认情况下，map是根据其键的自然顺序排序的，或者根据在映射创建时提供的Comparator进行排序，具体取决于所使用的构造函数。

Java ConcurrentSkipListMap类实现了SkipList的并发变体，从而为containsKey，get，put和remove操作及其变体提供了预期的平均log(n)时间成本。插入，删除，更新和访问操作可以安全地由多个线程同时执行。在Java 1.6中添加了ConcurrentSkipListMap。

SkipList数据结构

根据https://en.wikipedia.org/wiki/Skip_list –跳过列表是一种数据结构，可以在有序元素序列中进行快速搜索。通过维护子序列的链接层次结构，使快速搜索成为可能，每个连续的子序列跳过的元素比上一个要少。

如我们所见，为了更快地进行搜索，跳过列表要求元素按有序顺序排列，这就是为什么在Java ConcurrentSkipListMap中对元素进行排序的原因。

Java中的ConcurrentNavigableMap

Java中的ConcurrentSkipListMap实现了ConcurrentNavigableMap接口，其中ConcurrentNavigableMap依次扩展了ConcurrentMap和NavigableMap接口。

• ConcurrentMap –一个提供线程安全性和原子性保证的Map。因此，存在诸如putIfAbsent()，remove()之类的方法，其中的操作是原子执行的。

• NavigableMap –扩展了SortedMap的导航方法，返回给定搜索目标的最接近匹配项。因此，它具有诸如lowerEntry(K)，floorEntry(K)，lowerKey(K)，floorKey(K)，ceilingKey(K)之类的方法，用于将最匹配的键返回给所传递的键。

在Java 1.6中添加了ConcurrentNavigableMap接口。

Java ConcurrentSkipListMap构造函数

• ConcurrentSkipListMap()–构造一个新的空映射，根据键的自然顺序进行排序。

• ConcurrentSkipListMap(Comparator <？super K>比较器)–构造一个新的空映射，根据指定的比较器排序。

• ConcurrentSkipListMap(Map <？扩展K ，?扩展V> m)–构造一个新映射，该映射包含与给定映射相同的映射，并根据键的自然顺序进行排序。

• ConcurrentSkipListMap(SortedMap <K，？extended V> m)–构造一个新地图，该地图包含与指定排序后的地图相同的地图，并使用相同的顺序。

ConcurrentSkipListMap Java示例

public class SkipMapDemo {
  public static void main(String[] args) {
    // Creating ConcurrentSkipListMap
    ConcurrentNavigableMap<String, String> cityTemperatureMap = new ConcurrentSkipListMap<String, String>();

    // Storing elements
    cityTemperatureMap.put("Delhi", "24");
    cityTemperatureMap.put("Mumbai", "32");
    cityTemperatureMap.put("Chennai", "35");
    cityTemperatureMap.put("Bangalore", "22" );
    cityTemperatureMap.put("Kolkata", "28");

    Set<Map.Entry<String, String>> cityTempSet = cityTemperatureMap.entrySet();
    cityTempSet.forEach((m)->System.out.println("key " + m.getKey() 
				 + " value " + m.getValue()));
  }
}

输出：

key Bangalore value 22
key Chennai value 35
key Delhi value 24
key Kolkata value 28
key Mumbai value 32

如我们所见，这些元素按其键排序，并且使用自然顺序，因为在创建ConcurrentSkipListMap时未传递任何比较器。

ConcurrentSkipListMap不允许为空

Java中的ConcurrentSkipListMap类不允许使用空键或者空值。添加空键或者值会导致抛出NullPointerException。

例如在上面使用的示例代码中，如果我们尝试添加空键，结果将如下所示。

cityTemperatureMap.put(null, "28");

Exception in thread "main" java.lang.NullPointerException
	at java.base/java.util.concurrent.ConcurrentSkipListMap.doPut(ConcurrentSkipListMap.java:597)
	at java.base/java.util.concurrent.ConcurrentSkipListMap.put(ConcurrentSkipListMap.java:1345)

ConcurrentSkipListMap示例中的导航方法

public class SkipMapDemo {

  public static void main(String[] args) {
    // Creating ConcurrentSkipListMap
    ConcurrentNavigableMap<Integer, String> numberMap = new ConcurrentSkipListMap<Integer, String>();

    // Storing elements
    numberMap.put(1, "ONE");
    numberMap.put(2, "TWO");
    numberMap.put(5, "FIVE");
    numberMap.put(8, "EIGHT" );
    numberMap.put(10, "TEN");
    numberMap.put(16, "SIXTEEN");

    System.out.println("** reverse order view of the map **");

    //Returns a reverse order view of the mappings
    ConcurrentNavigableMap<Integer, String> reverseNumberMap = numberMap.descendingMap();

    Set<Map.Entry<Integer, String>> numSet = reverseNumberMap.entrySet();
    numSet.forEach((m)->System.out.println("key " + m.getKey() 
         + " value " + m.getValue()));
    System.out.println("** First entry in the the map **");
    //Returns a key-value mapping associated with the least key in this map
    Map.Entry<Integer, String> mapEntry = numberMap.firstEntry();
    System.out.println("key " + mapEntry.getKey() + " value " + mapEntry.getValue());

    System.out.println("** Floor entry Example **");
    //Returns a key-value mapping associated with the greatest key less than or equal to the given key
    mapEntry = numberMap.floorEntry(7);
    System.out.println("key " + mapEntry.getKey()  + " value " + mapEntry.getValue());

    System.out.println("** Ceiling entry Example **");
    //Returns a key-value mapping associated with the least key greater than or equal to the given key
    mapEntry = numberMap.ceilingEntry(7);
    System.out.println("key " + mapEntry.getKey()  + " value " + mapEntry.getValue());
  }
}

输出：

** reverse order view of the map **
key 16 value SIXTEEN
key 10 value TEN
key 8 value EIGHT
key 5 value FIVE
key 2 value TWO
key 1 value ONE
** First entry in the the map **
key 1 value ONE
** Floor entry Example **
key 5 value FIVE
** Ceiling entry Example **
key 8 value EIGHT