跳表原理及复杂度分析

跳表是什么

链表结合多级索引，实现了一种类二分查找的操作。利用的是空间换时间的思想。

跳表的时间复杂度

假设有 n 个节点，首先按每两个节点抽出一个索引为例，那么第 k 级索引的索引数为 n/2^k。最高级索引数有 2 个，则 n / 2^k = 2，k = logn - 1。加上最后一层，高度 h 为 h = logn。每一层需要遍历的元素个数如图分析可知是 3 个，则跳表的查询时间复杂度为 O(logn)。

跳表的空间复杂度

原始链表大小为 n，每两个节点抽一个，总共节点总和 n/2 + n/4 + n/8... + 4 + 2 = n - 2。所以，跳表的空间复杂度是 O(n)。

高效的动态插入和删除

插入和删除的时间复杂度也为 O(logn)。

索引的维护

通过随机函数生成 K 值，然后在第一层到第 K 层都加上这个节点。

注：Redis 里的有序集合就是通过跳表来实现的，不用红黑树是因为红黑树不适合范围查找，跳表代码更容易实现。