索引
文章
《Java高并发程序设计 第2版》第144-146页。
新得
Java内部又一个跳表为数据结构的Map，ConcurrentSkipListMap，听名字就知道，这种Map是为了在高并发情况下使用的。
这种Map的数据结构是跳表。本文我就主要记录一下什么是跳表。
看了这个书之后，对跳表有了一定的了解。跳表的结构其实就是在链表的基础上扩充了下，使用空间换时间。并且跳表中的元素是有序的。
我们知道的链表是一根链，跳表其实就是好几条链表，然后这些链表之间是有关系的。比如一个跳表有3层链，则代表这个跳表有3层。第1层的元素最少，第1层是第2层的子集。第2层元素个数稍多，第2层是第3层的子集。第3层是满元素。然后这3层链不是完全独立的3条，其中1、2层之间，2、3层之间是有指针关联起来的。
有了上述的这种跳表，就可以加速元素的查找过程。比如下图，从上到下总共4层。
如果我们只有普通的一条链表的话（也就是最底下的那条链），那只能从左向右一个个查找元素。效率是很低的，有了跳表之后，就可以做到根据上层元素少的链表来跳过一些元素的目的。甚至如果上层链表包含我们需要的数据，还可以直接在上层链表就查找出数据，不一定需要到最底层。
总结
可以看出，跳表内看似维护了一个网状的数据结构，但其实只是链表的扩充，是多条链表组合在一起。每条链表都是有序的，高层链表是底层链表的子集。这样可以在查找过程中跳过一些元素，不用全部遍历，达到提高效率的目的。
原创文章，作者：geekgao，如若转载，请注明出处：https://www.geekgao.cn/archives/2611
微信 
支付宝