算法技巧跳表（Skip List）（一）：介绍、ConcurrentSkipListMap源码分析

跳表(SkipList，全称跳跃表)是用于有序元素序列快速搜索查找的一个数据结构，跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，实现也比红黑树简单很多。

介绍

跳跃表(简称跳表)由美国计算机科学家William Pugh发明于1989年。他在论文《Skip lists: a probabilistic alternative to balanced trees》中详细介绍了跳表的数据结构和插入删除等操作。

图形化探究跳表，先回顾链表。链表的优势就是更高效的插入、删除。痛点就是查询很慢很慢！每次查询都是一种O(n)复杂度的操作。

能不能稍微优化一下，让它稍微跳一跳呢？答案是可以的，我们知道很多算法和数据结构以空间换时间，我们在上面加一层索引，让部分节点在上层能够直接定位到，这样链表的查询时间近乎减少一半。

在查询某个节点的时候，首先会从上一层快速定位节点所在的一个范围，如果找到具体范围向下然后查找代价很小，当然在表的结构设计上会增加一个向下的索引(指针)用来查找确定底层节点。平均查找速度平均为O(n/2)。但是当节点数量很大的时候，它依旧很慢很慢。我们都知道二分查找是每次都能折半的去压缩查找范围，要是有序链表也能这么跳起来那就太完美了。没错跳表就能让链表拥有近乎的接近二分查找的效率的一种数据结构，其原理依然是给上面加若干层索引，优化查找速度。

对于理想的跳表，每向上一层索引节点数量都是下一层的1/2，那么就有二分查找的性能。实际情况时不太可能有这种理想的情况。

特点和优势

跳表的核心思想是通过构建多层索引，每一层索引都是下一层索引的一部分，使得从顶层索引开始，可以快速定位到目标元素的前驱节点。通过这种索引结构，跳表可以在插入、删除和搜索操作中快速地定位到目标位置，从而提高了效率。

实现原理介绍

先基于JDK中java.util.concurrent包中ConcurrentSkipListMap源码，来介绍基于跳表（Skip List）数据结构相关时间

构造函数

• 默认构造函数

public ConcurrentSkipListMap() {
    this.comparator = null;
    initialize();
}

//初始化，设置head头节点，lever层级为1，后面会讲到HeadIndex
private void initialize() {
    keySet = null;
    entrySet = null;
    values = null;
    descendingMap = null;
    head = new HeadIndex(new Node(null, BASE_HEADER, null),
                              null, null, 1);
}

• 待指定比较器

public ConcurrentSkipListMap(Comparator