当前位置： 首页 >> 数据结构与算法 >> 跳表原理与实例

---

跳表原理与实例

2020-07-04 18:38:19 星期六  阅读：2127

---

之前提到的二分查找，只能用数组来实现，因为数组可以随机访问，而链表通过下标访问时间复杂度会很糟糕。其实通过改造后的链表也支持二分查找，我们称改造后的链表叫跳表。可以实现快速插入、删除和查找操作。具体的改造方式是给链表增加多级索引。 实际上，随着数据量的增大，索引的级数可以无限增加。这样就是实现不用遍历原始链表就可以实现快速访问链表的功能。 如下图（图片来自极客时间），需要找到索引为10的数值，只需要从二级索引依次往下面遍历就可以。实际上，随着数据量的增大，索引的级数可以无限增加。这样就是实现不用遍历原始链表就可以实现快速访问链表的功能。  *图片来自《极客时间-数据结构与算法之美专栏》* ####跳表的特性 1、根据下标访问元素的时间复杂度是O(logn），这跟二分查找是一样的时间复杂度。 2、动态的数据结构，支持动态插入、删除。 3、因为需要存储索引，所以相比数组需要额外的内存空间。其空间复杂度是O(n)，也就是说原始链表大小为100MB，则改造后的跳表占用内存翻倍（其实也就是牺牲空间换时间的理念） 4、对于插入删除操作，时间复杂度也是O(logn)，因为对于有序单链表只需要找到插入点即可，而找到插入点可以用上述提到的多级索引遍历，时间复杂度是O(logn)。 5、跳表索引动态更新。如果不更新跳表的索引，随着原始链表的数据插入操作，可能某些索引里面包含很多的数据，这会导致索引退化成链表，如下图。所以需要某种手段来维护索引与原始链表大小之间的平衡。 ####实例 为什么Redis要用跳表来实现有序集合？而不是红黑树？ Redis中的有序集合支持的核心功能为 ``` 插入一个数据； 删除一个数据； 查找一个数据； 按区间查找数据（比如查找100-200之间的数据） 迭代输出有序序列。 ``` 对于上述操作，红黑树都能完成，时间复杂度也一样，但是按区间查找数据这个红黑树的效率没有跳表高。 Redis使用跳表来实现有序集合，应该还有其他原因： `跳表更容易代码实现（虽然跳表也不简单），代码可读性也更高；` `跳表更加灵活，有效平衡执行效率和内存消耗；` 当然跳表也不能完全代替红黑树，原因如下： 很多编程语言中Map类型都是通过红黑树来实现的，我们直接拿来用。但是跳表并没有一个现成的实现，如果在开发中需要用到，还得自己实现。