参考地址：https://www.cnblogs.com/skywang12345/p/3498556.html#p1

ConcurrentSkipListMap介绍

ConcurrentSkipListMap是线程安全的有序的哈希表，适用于高并发的场景。
ConcurrentSkipListMap和TreeMap，它们虽然都是有序的哈希表。但是，第一，它们的线程安全机制不同，TreeMap是非线程安全的，而ConcurrentSkipListMap是线程安全的。第二，ConcurrentSkipListMap是通过跳表实现的，而TreeMap是通过红黑树实现的。
关于跳表(Skip List)，它是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表的插入和删除的工作是比较简单的。

ConcurrentSkipListMap原理和数据结构

ConcurrentSkipListMap的数据结构，如下图所示：
ConcurrentSkipListMap - 图1
说明：
先以数据“7,14,21,32,37,71,85”序列为例，来对跳表进行简单说明。
跳表分为许多层(level)，每一层都可以看作是数据的索引，这些索引的意义就是加快跳表查找数据速度。每一层的数据都是有序的，上一层数据是下一层数据的子集，并且第一层(level 1)包含了全部的数据；层次越高，跳跃性越大，包含的数据越少。
跳表包含一个表头，它查找数据时，是从上往下，从左往右进行查找。现在“需要找出值为32的节点”为例，来对比说明跳表和普遍的链表。
情况1：链表中查找“32”节点
路径如下图1-02所示：
ConcurrentSkipListMap - 图2
需要4步(红色部分表示路径)。

情况2：跳表中查找“32”节点
路径如下图1-03所示：
ConcurrentSkipListMap - 图3
忽略索引垂直线路上路径的情况下，只需要2步(红色部分表示路径)。
下面说说Java中ConcurrentSkipListMap的数据结构。
(01) ConcurrentSkipListMap继承于AbstractMap类，也就意味着它是一个哈希表。
(02) Index是ConcurrentSkipListMap的内部类，它与“跳表中的索引相对应”。HeadIndex继承于Index，ConcurrentSkipListMap中含有一个HeadIndex的对象head，head是“跳表的表头”。

ConcurrentSkipListMap函数列表

**

  1. // 构造一个新的空映射，该映射按照键的自然顺序进行排序。
  2. ConcurrentSkipListMap()
  3. // 构造一个新的空映射，该映射按照指定的比较器进行排序。
  4. ConcurrentSkipListMap(Comparator<? super K> comparator)
  5. // 构造一个新映射，该映射所包含的映射关系与给定映射包含的映射关系相同，并按照键的自然顺序进行排序。
  6. ConcurrentSkipListMap(Map<? extends K,? extends V> m)
  7. // 构造一个新映射，该映射所包含的映射关系与指定的有序映射包含的映射关系相同，使用的顺序也相同。
  8. ConcurrentSkipListMap(SortedMap<K,? extends V> m)
  10. // 返回与大于等于给定键的最小键关联的键-值映射关系；如果不存在这样的条目，则返回 null。
  11. Map.Entry<K,V> ceilingEntry(K key)
  12. // 返回大于等于给定键的最小键；如果不存在这样的键，则返回 null。
  13. K ceilingKey(K key)
  14. // 从此映射中移除所有映射关系。
  15. void clear()
  16. // 返回此 ConcurrentSkipListMap 实例的浅表副本。
  17. ConcurrentSkipListMap<K,V> clone()
  18. // 返回对此映射中的键进行排序的比较器；如果此映射使用键的自然顺序，则返回 null。
  19. Comparator<? super K> comparator()
  20. // 如果此映射包含指定键的映射关系，则返回 true。
  21. boolean containsKey(Object key)
  22. // 如果此映射为指定值映射一个或多个键，则返回 true。
  23. boolean containsValue(Object value)
  24. // 返回此映射中所包含键的逆序 NavigableSet 视图。
  25. NavigableSet<K> descendingKeySet()
  26. // 返回此映射中所包含映射关系的逆序视图。
  27. ConcurrentNavigableMap<K,V> descendingMap()
  28. // 返回此映射中所包含的映射关系的 Set 视图。
  29. Set<Map.Entry<K,V>> entrySet()
  30. // 比较指定对象与此映射的相等性。
  31. boolean equals(Object o)
  32. // 返回与此映射中的最小键关联的键-值映射关系；如果该映射为空，则返回 null。
  33. Map.Entry<K,V> firstEntry()
  34. // 返回此映射中当前第一个（最低）键。
  35. K firstKey()
  36. // 返回与小于等于给定键的最大键关联的键-值映射关系；如果不存在这样的键，则返回 null。
  37. Map.Entry<K,V> floorEntry(K key)
  38. // 返回小于等于给定键的最大键；如果不存在这样的键，则返回 null。
  39. K floorKey(K key)
  40. // 返回指定键所映射到的值；如果此映射不包含该键的映射关系，则返回 null。
  41. V get(Object key)
  42. // 返回此映射的部分视图，其键值严格小于 toKey。
  43. ConcurrentNavigableMap<K,V> headMap(K toKey)
  44. // 返回此映射的部分视图，其键小于（或等于，如果 inclusive 为 true）toKey。
  45. ConcurrentNavigableMap<K,V> headMap(K toKey, boolean inclusive)
  46. // 返回与严格大于给定键的最小键关联的键-值映射关系；如果不存在这样的键，则返回 null。
  47. Map.Entry<K,V> higherEntry(K key)
  48. // 返回严格大于给定键的最小键；如果不存在这样的键，则返回 null。
  49. K higherKey(K key)
  50. // 如果此映射未包含键-值映射关系，则返回 true。
  51. boolean isEmpty()
  52. // 返回此映射中所包含键的 NavigableSet 视图。
  53. NavigableSet<K> keySet()
  54. // 返回与此映射中的最大键关联的键-值映射关系；如果该映射为空，则返回 null。
  55. Map.Entry<K,V> lastEntry()
  56. // 返回映射中当前最后一个（最高）键。
  57. K lastKey()
  58. // 返回与严格小于给定键的最大键关联的键-值映射关系；如果不存在这样的键，则返回 null。
  59. Map.Entry<K,V> lowerEntry(K key)
  60. // 返回严格小于给定键的最大键；如果不存在这样的键，则返回 null。
  61. K lowerKey(K key)
  62. // 返回此映射中所包含键的 NavigableSet 视图。
  63. NavigableSet<K> navigableKeySet()
  64. // 移除并返回与此映射中的最小键关联的键-值映射关系；如果该映射为空，则返回 null。
  65. Map.Entry<K,V> pollFirstEntry()
  66. // 移除并返回与此映射中的最大键关联的键-值映射关系；如果该映射为空，则返回 null。
  67. Map.Entry<K,V> pollLastEntry()
  68. // 将指定值与此映射中的指定键关联。
  69. V put(K key, V value)
  70. // 如果指定键已经不再与某个值相关联，则将它与给定值关联。
  71. V putIfAbsent(K key, V value)
  72. // 从此映射中移除指定键的映射关系（如果存在）。
  73. V remove(Object key)
  74. // 只有目前将键的条目映射到给定值时，才移除该键的条目。
  75. boolean remove(Object key, Object value)
  76. // 只有目前将键的条目映射到某一值时，才替换该键的条目。
  77. V replace(K key, V value)
  78. // 只有目前将键的条目映射到给定值时，才替换该键的条目。
  79. boolean replace(K key, V oldValue, V newValue)
  80. // 返回此映射中的键-值映射关系数。
  81. int size()
  82. // 返回此映射的部分视图，其键的范围从 fromKey 到 toKey。
  83. ConcurrentNavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
  84. // 返回此映射的部分视图，其键值的范围从 fromKey（包括）到 toKey（不包括）。
  85. ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey)
  86. // 返回此映射的部分视图，其键大于等于 fromKey。
  87. ConcurrentNavigableMap<K,V> tailMap(K fromKey)
  88. // 返回此映射的部分视图，其键大于（或等于，如果 inclusive 为 true）fromKey。
  89. ConcurrentNavigableMap<K,V> tailMap(K fromKey, boolean inclusive)
  90. // 返回此映射中所包含值的 Collection 视图。
  91. Collection<V> values()

源码分析暂时略过。。。。