跳表
跳表（skiplist）是一种有序的数据结构，是在有序链表的基础上发展起来的。
在 Redis 中跳表是有序集合（sort set）的底层实现之一。
说到 Redis 中的有序集合，是不是和 Java 中的 TreeMap 很像？都是有序集合。
那么：
- 为什么会出现跳表这种数据结构呢？
- 跳表的原理是什么？Redis又是怎么实现的？
- 和同类中（二叉平衡树）相比，有什么优缺点呢？
为什么会出现跳表？跳表解决了什么样的问题？
跳表可以说是平衡树的一种替代品。它也是为了解决元素随机插入后快速定位的的问题。到这里，你可能会说 hash 表解决的不是很好吗？插入和查找都是 O(1) 的时间复杂度。是的，hash表是很好的解决了查找的问题，但若想要有序呢？这个时候 hash 表就不行了，二叉查找树可以解决这个问题。
但是由于二叉查找树在按大小顺序进行插入的时候，就会退化为链表。所以又出现了平衡二叉树，而根据算法不同，又分为AVL树、B-Tree、B+Tree、红黑树等。看到这里，是不是头都大了（天呐，这么多算法，这么复杂的实现）。
而跳表的出现就是为了解决平衡二叉树复杂的问题。所以它可以说是平衡树的一种替代品。它以一种较为简单的方式实现了平衡二叉树的功能。
跳表的原理是什么？Redis又是怎么实现的？
跳表的原理网上一搜一大堆，这里就不重复了，这里给出看起来不错的两篇文章：
http://copyfuture.com/blogs-details/6097031f2015d499a2321e23ea3f1324
https://lotabout.me/2018/skip-list/
Redis 中跳表由 redis.h/zskiplistNode（跳表节点）和 redis.h/zskiplist（跳表节点的相关信息，比如节点的数量、表头、表尾指针）两个结构定义。他们的具体结构如下：
/*
* 跳跃表节点
*/
typedef struct zskiplistNode {
// 成员对象
robj *obj;
// 分值
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;
/*
* 跳跃表
*/
typedef struct zskiplist {
// 表头节点和表尾节点
struct zskiplistNode *header, *tail;
// 表中节点的数量
unsigned long length;
// 表中层数最大的节点的层数（表头节点不计）
int level;
} zskiplist;
/*
* 有序集合
*/
typedef struct zset {
// 字典，键为成员，值为分值
// 用于支持 O(1) 复杂度的按成员取分值操作
dict *dict;
// 跳跃表，按分值排序成员
// 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
// 以及范围操作
zskiplist *zsl;
} zset;
一个完整跳表的示意图如下（出自《Redis设计与实现第二版》第五章：跳跃表）：
位于图片最左边的是 zskiplist 结构，该结构包含以下属性：
- header ：指向跳表的表头节点。
- tail ：指向跳表的表尾节点。
- level ：记录目前跳表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
- length ：跳表的长度，即跳表目前包含节点的数量。
位于 zskiplist 结构右方的是四个 zskiplistNode 结构，该结构包含以下属性：
- level ：层，节点中用 L1、L2、L3 等字样标记节点的各个层，L1 代表第一层，L2 代表第二层，以此类推。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则表示前进指针所指向节点和当前节点的距离，跨度越大，相距越远。在上面的图片中，连线上带有数字的箭头就代表前进指针，数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。
- backward ：后退指针，节点中用 Bw 字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
- score ：各个节点中的 1.0、2.0、3.0 是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。
- obj ：成员对象，各个节点中的 o1、o2、o3 是节点所保存的成员对象。
注：
- 表头节点不存储数据，所以图中省略了表头节点的部分属性。
- 由于跳表中查找元素的时间复杂度是 O(logn) ，所以有序集合（zset）中又定义了一个存储键值对的字典，所以有序集合中根据 key 查找分数的时间复杂度为 O(1)。
跳表和同类中（二叉平衡树）相比，有什么优缺点呢？
这里我就直接引用网上的资料了，如下（出自：http://copyfuture.com/blogs-details/6097031f2015d499a2321e23ea3f1324）：
上期思考问题
上篇思考问题： Java 中 HashMap 关于扩容和收缩的3个问题是怎么解决的呢？
（1）触发条件是什么？是手动触发还是自动触发。
（2）扩容或者收缩的规则是什么？具体过程是怎样的？
（3）当哈希表在扩容时，是否允许别的线程来操作这个哈希表？
首先，Java 中的 HashMap 没有收缩，只有扩容。
-
扩容的触发条件是：put时先添加元素，添加完元素之后，看当前size是否大于hash表总容量*扩容因子。若是，则扩容。 如下：
/** * The next size value at which to resize (capacity * load factor). * * @serial */ int threshold; final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { ... ++modCount; if (++size > threshold) resize(); // 重新调整大小。 afterNodeInsertion(evict); return null; } -
扩容的规则是：每次扩容二倍，如果超过最大值（1 << 30）则不扩容。具体代码如下：
/** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ static final int MAXIMUM_CAPACITY = 1 << 30; final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } ... } -
Java中的 HashMap 扩容是一次性的，是线程不安全的，不允许别的线程来操作 hash 表。所以 Java 有 Hashtable、ConcurrentHashMap 这些线程安全的 Hash 表。
本期思考问题
暂无
参考资料：
https://juejin.im/post/57fa935b0e3dd90057c50fbc
http://copyfuture.com/blogs-details/6097031f2015d499a2321e23ea3f1324
https://lotabout.me/2018/skip-list/
《Redis设计与实现（第二版）》