持续创作，加速成长！这是我参与「掘金日新计划 · 6 月更文挑战」的第16天，点击查看活动详情
1. SkipList跳表介绍与应用跳表是一种方便我们进行搜索的数据结构，其由多层长度不同的链表连接成，如下图所示：
在跳表中，每次搜索都是从最上层开始，向右搜索，如果没有找到，就进入下层搜索，直至搜索到目标或者最后一个元素。
当元素很多事，这种分层搜索的思想能高效的缩短我们搜索的路径长度，理论上的时间复杂度与二分查找近似。上图中红色的路线是查找2指向的地址空间的查询路线。
跳表的数据结构使用的非常广泛，可以用作有序map的底层数据结构，最为我们熟知的可能就是Redis中的跳表结构。
不过，由于Redis的主线程是单线程的，所以不需要考虑并发安全问题，但是在我们日常使用的过程中，并发安全问题不可避免，在Java中也提供了并发安全的跳表结构，所以我们这对增删改三个操作来讨论并从原理上实现一个并发安全的跳表结构，以供大家学习参考。
2. 并发安全的修改节点跳表结构常常用来当作kv存储的底层结构，所以其修改操作一般就是针对v的修改，并发安全的修改操作往往借助CAS操作来完成，CAS操作的底层是乐观锁的机制，在进行修改操作以前，会记录修改前的数值，修改操作生效时会对比这个值，如果相同，CAS操作才能生效，反之进行失败重试。各种语言都给我们提供了方便实用的CAS包。
3. 并发安全的增加节点对于跳表的数据结构而言，节点的增加是分层进行的，首先，最底层的链表储存有所有的节点，所以在这一层一定会新增一个节点，而上层链表是否需要增加节点是由随机数决定的，并不能在插入操作的瞬间就决定出来。以之前的跳表结构为例，如果想增加k值为4的节点，我们就需要优先锁定其前面的所有节点，如下图所示：
红色部分圈起来的是所有需要锁定的节点，锁定之后，先插入最底层的节点，之后随机从下往上确定是否需要继续差插入节点。插入过程结束后，解锁锁定的红色节点。
4. 并发安全的删除节点在跳表中，节点的删除是从上往下进行的，并且在锁定被删除节点的同时，还需要锁定其前面的节点。我们以单链表为例来说明这个问题：
如下所示的链表，在不锁定前置节点的情况下，如果我们需要并发删除B与C节点，可能会出现以下问题：
- 原始的链表
- 将C节点的前置节点B的指针指向D，之后只需删除B指向C的指针，C节点就删除了
- 在删除B指向C的指针，以移除C的操作之前，可能插入删除B的第一步操作（A的指针指向C）
- 再之后，删除A指向B的节点，理论上的删除操作就已经结束了，但是我们会发现，原本需要删除的C并没有被删除，出现了并发的问题。
为了解决上面出现的问题，我们就需要同时锁定删除节点的上一个节点。推广到跳表的结构中也是一样的，在删除一个节点时，我们需要自上而下的目标节点，在删除某一节点的同时，锁定其前一个节点。
以删除节点3为例，我们需要首先锁定蓝色框中的两个节点，在完成删除操作之后，锁定之后删除红色框中的两个节点，以保证并发的安全性。