更多数据结构内容，请参考：数据结构 - 概要
简介
疑问中理解技术
跳表产生的背景
任何技术，都是为了解决特定问题而出现的。
跳表要解决的就是list这种数据结构查询速度过慢的问题。
与list常做对比的数据结构是数组。数组中元素的查找可以使用二分查找，可以使查找降低到O(logN)的时间复杂度度
但是对于list来讲，查找只能从头或尾部一个个遍历，时间复杂度是O(n)的。
二分查找的效率高，是因为每次对比后，都能排除一半的数据，使要搜索的元素集合大大减少。这类似于一种索引技术，而数组下标就是索引。
对于list来讲，可以通过额外存储一些数据，当做list的索引：即在原来list的基础上，再存储些数据，这些数据也都是用list存储的。通过逐层对比这些数据，实现缩小搜索范围的目的。这个在Redis 为什么用跳表而不用平衡树？中讲的比较清楚。
但是跳表并没有实现严格的二分。要实现严格的二分要调整已经存储的数据，会增加工作量。
跳表选择了一种变通做法，通过随机函数，决定新插入元素的层高。这种实现虽然不能保证查询效率是严格的O(logN)，但是平均值和绝大多数情况下，都能达到O(logN)的效率。
这是一种折中，但折中折中在没有降低太多查询性能的情况下，大大提升了插入效率。这个想法跟红黑树的实现有相似之处。 数据结构 - 红黑树
跳表与平衡树的比较
跳表会经常被用来跟平衡树，尤其是红黑树来比较。
这是因为跳表和红黑树能做的事几乎相同。
- 跳表实现比红黑树简单太多了
- 跳表的存储空间比红黑树大，但也大不了多少
- 查询效率而言，红黑树更稳定，但绝大多数情况下区别不大。
- 跳表数据存放是紧凑的，也就是顺序递增的数据是挨着的，这样就非常适合范围查找。红黑树的范围查找就不怎么样了
像redis中sorted set数据结构是用跳表来实现的。而JDK中的TreeMap使用红黑树来实现的。
只能说跳表和红黑树各有千秋。个人在选择其中一个实现时，需要结合自己的实际情况，如能力、时间和需求等。
为啥 redis 使用跳表(skiplist)而不是使用 red-black？ 文中讨论了redis为何使用的是跳表而非红黑树。里面一个共识就是，跳表实现起来比红黑树简单太多了(redis作者也把这个列为了一个因素)，又能满足需求。
网友评论