今天发现了一个新的Java数据类型：ConcurrentSkipListMap，其中内部使用了跳表的数据结构。
在看ConcurrentSkipListMap之前先看，什么是跳表？
跳表
跳表是基于有序的单向链表，下面是一个有序的单向链表，每个结点有一个指针都指向下一个结点。
1.有序的单向链表：
如果我们需要检索“值6”的结点，需要从头往尾遍历检索，顺序是：
1 -> 2 -> 3 -> 4 -> 5 -> 6
所用到的复杂度为O(n)
2.跳表
如果一个有序的数组，就可以用二分法加快检索，既然链表也是有序的，那么有没有办法用上二分法呢？答案是可以的。
上述的链表的基础上，提取出“值1”、“值4”、“值7”出来作为中间索引结点。
每个结点有两个指针，一个指向下一个结点，一个指向下一层的结点。
同上面一样检索“值6”，借用二分法的原理：先在最上面的leve2一层中比较，找出是4 – 7之间的区间，再到level1下一层遍历寻找。
1 – > 4 -> 5 -> 6
时间复杂度就是O(log(n))，很明显这是一种空间换时间的算法，提取了“1”、“4”、“7”结点为索引结点，增加存储了索引结点的空间。
在此基础上还有继续优化的空间，可以再提取新的一层中间结点，再继续往下看：
不同于上面的中间结点，我们只是随机的提取一些结点作为索引结点，这其实就是ConcurrentSkipListMap的基本数据结构。
那么如何寻找需要的结点呢？
很简单：优先从左往右遍历，再到下一层继续从左往右走。
- 例子：寻找结点5
1 -> 4 -> 5
- 例子：寻找结点7：
1 -> 6 -> 7
ConcurrentSkipListMap特性
特性
- 继承自AbstractMap，支持键值对
- key是有序的链表结构
- 支持线程安全
数据结构
Node
Index
方法
get()
put()
remove()
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/19390.html