数据结构与算法Java（四）跳表
1、定义：链表加多级索引的结构，提高查找效率，类似于二分查找
时间复杂度：查询，插入，删除都是O(logn）
空间复杂度：O(n)
图解：
2、问题：插入数据过多时，可能出现某2个索引结点之间的数据非常多，极端情况下，跳表会退化成单链表
跳表的解决方式是通过随机函数来维护平衡性。比如随机函数生成了值K，那我们就将这个节点添加到第一级到第k级索引中
3、思考题：为什么Redis要用跳表来实现有序集合，而不用红黑树
答:Redis有序集合的核心操作如下：插入/删除/查找一个数据；按照区间查找数据；迭代输出有序序列。其中增删查的操作红黑树也可完成，时间复杂度和跳表一样，1）但是对于按照区间查找这个操作，跳表可以做到O(logn)的时间复杂度定位区间的起点，然后再原始链表中顺序往后遍历即可，效率高；2）相对红黑树，跳表更容易实现；3）跳表更加灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗
参考资料：极客时间的《数据结构与算法之美》王争