高效遍历链表，不用从头到尾遍历。
跳表是一种可以用来快速查找的数据结构，有点类似于平衡树。它们都可以对元素进行快速的查找。但一个重要的区别是：对平衡树的插入和删除往往很可能导致平衡树进行一次全局的调整。而对跳表的插入和删除只需要对整个数据结构的局部进行操作即可。
好处：在高并发的情况下，需要一个全局锁来保证整个平衡树的线程安全。而对于跳表，只需要部分锁即可。这样，在高并发环境下，就可以拥有更好的性能。而就查询的性能而言，跳表的时间复杂度也是 O(logn) 所以在并发数据结构中，JDK 使用跳表来实现一个 Map。
跳表的本质是同时维护了多个链表，并且链表是分层的
跳表内的所有链表的元素都是排序的。查找时，可以从顶级链表开始找。一旦发现被查找的元素大于当前链表中的取值，就会转入下一层链表继续找。这也就是说在查找过程中，搜索是跳跃式的。如上图所示，在跳表中查找元素 18。
查找 18 的时候原来需要遍历 18 次，现在只需要 7 次即可。针对链表长度比较大的时候，构建索引查找效率的提升就会非常明显。
跳表是一种利用空间换时间的算法。
使用跳表实现 Map 和使用哈希算法实现 Map 的另外一个不同之处是：哈希并不会保存元素的顺序，而跳表内所有的元素都是排序的。因此在对跳表进行遍历时，会得到一个有序的结果。所以，如果需要有序性，那么跳表就是不二选择。JDK 中实现这一数据结构的类是 ConcurrentSkipListMap
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/212229.html原文链接：https://javaforall.net
