ConcurrentSkipListMap详解编程语言

今天发现了一个新的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特性

特性

1. 继承自AbstractMap，支持键值对
2. key是有序的链表结构
3. 支持线程安全

数据结构

Node

Index

方法

get()

put()

remove()