1. 跳表
1.1 跳表基本思路
对于有序数据的存储，常见的数据结构有：
- 数组：空间复杂度O(n)，定位插入/删除时间复杂度O(n)，查找时间复杂度O(logn)
- 链表：空间复杂度O(n)，定位插入/删除时间复杂度O(1)，查找时间复杂度O(n)
- 二叉树：空间复杂度O(n)，定位插入/删除时间复杂度O(logn)，查找时间复杂度Olog(n)
由上可以看出跳表在定位插入时效率很高，但在查找时效率较低。为了提升其查找效率可以为链表加上多层索引，形成一种新的数据结构跳表，跳表在查找时可以通过索引跳过部分节点，提高查找效率。
如果每隔一个节点向上层生成一个索引，最终会生成logn层高的索引，查找过程每次都能剔除一半节点，相对单纯的链表即有快速插入的能力，又可以明显提升查询速度。
1.2 跳表的插入
但是如果在上述跳表基础上进行插入操作时可能会破坏每隔一个节点向上层生成一个索引的结构，需要重新遍历生成索引(O(n))，这显然是不合理的。
为了解决索引的生成问题跳表在插入时并不关心已有索引结构，而是通过随机数来决定新节点的索引高度：
int rnd = ThreadLocalRandom.nextSecondarySeed();
int level = 1, max;
while (((rnd >>>= 1) & 1) != 0)
++level;
1.3 空间复杂度
假设生成索引的概率为p，则：
节点层数为1概率：1-p
节点层数为2概率：(1-p) * p
节点层数为3概率：(1-p) * p^2
....
跳表中节点平均高度为
(1-p) + 2p(1-p) + 3p^2(1-p) + 4p^3(1-p) + ... + np^(n-1)(1-p) n->正无穷
=(1-p) * 1 / (1-p)^2
= 1 / (1 - p)
这也决定了跳表的空间复杂度为O(n)。
1.4 时间复杂度
一个存储n个节点，m个节点创建一个上层索引的跳表中：
第1层节点数量L1 = n
第2层节点数量L2 = n / m^2
第3层节点数量L3 = n / m^3
...
则最高层级Lmax = n / m^max = m
即 max = logn - 1
又因为在每一层的搜索中，搜索次数都小于等于m，所以最大搜索次数为m(logn - 1)，即最终的时间复杂度为O(logn)
关于跳表部分的更多参考资料：
Skip Lists: A Probabilistic Alternative to Balanced Trees
A Pragmatic Implementation of Non-Blocking Linked-Lists
https://juejin.im/post/57fa935b0e3dd90057c50fbc#heading-5
2.ConcurrentSkipListMap
ConcurrentSkipListMap就是基于上述跳表的思想实现的一个线程安全的有序Map结构。为了实现这一目标，需要对链表的一系列操作进行线程安全性的保证。
2.1 链表的并发插入与删除
对于链表的并发插入，直接使用CAS实现是没有问题的，因为在同一个区间（下图2-15）进行插入操作时都会受到首节点（2）的限制，只有成功将前驱节点指针指向新插入节点的线程才算完成插入操作。
但是链表的并发删除，使用CAS则会有问题，删除操作的区间存在重叠情况，仅仅依赖与前驱节点的CAS操作可能会破坏链表的结构。
同样的，并发的CAS插入和删除也会有类似问题，问题的原因在于：链表在并发插入时只需要锁定一个区间，而对于删除操作需要锁定两个区间（如下图）。
为了解决上述问题，在保留原有的插入逻辑的基础上，对节点的删除方式进行了调整：
-
在节点删除时并不对其进行物理删除，只是将要删除的节点value设置为空。
-
后续在对链表进行遍历时，如果第一次发现value为空的节点，在该节点后面插入删除标记，其他写入线程遍历到该标记后会不断尝试通过对左区间的原子操作对该节点进行物理删除，即标记插入的那一刻就保证右侧区间被锁定直到删除完成。
2.2 跳表的索引插入与删除
CSLMap中的索引对象如下：
static class Index<K,V> {
final Node<K,V> node;
final Index<K,V> down;
volatile Index<K,V> right;
}
在不考虑并发操作时，对于索引的插入可以通过：将查找节点时经过的路径进行存储，实现快速插入索引的目的，但对于并发操作时索引结构随时可能发生变化，CSLMap采用了对每一层从前驱索引开始进行遍历的方式进行插入，插入的方式和2.1中链表插入方式一致。
对于索引的删除则是在查找索引过程中实现的，当查找索引时发现node为null的索引时直接使用CAS替换来删除该索引，并没有使用2.1中对节点删除的方式，这样可能会导致索引删除失败（会在后续的查找中被修正）或者新增失败，猜测应该是索引结构出现小范围的缺失并不会产生太大影响。
3. CCSMap
A Faster, GC-friendly, Less memory Concurrent Map for MemStore