弥补链表的缺陷 升维 空间换时间
– 如何给链表加速
-添加第一级索引，第二级索引 (log2n个级索引)
– 时间复杂度分析
– n/2,n/4,n/8第k级索引节点的个数就是n/(2^k),假设索引有h级，最高级的索引有2个。n/(2^h)=2,从而求得h=log2(n)-1
– 增加和删除的时候，要更新索引，所以增加和删除的时间复杂度就会编程logn了
– 跳表的空间复杂度分析
– 每2个节点抽1个，每层索引节点 n/2,n/4n/8…8,4,2 空间复杂度是O(n)
参考于 https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html(redis设计与实现)
– redis为了满足自身的功能需要，修改了
– 允许重复的score值，多个不同的member的score值可以相同。
– 进行对比操作时，不仅要检查score值，还要检查member;当score值可以重复时，单靠score值无法判断一个元素的身份，所以需要连member域都一并检查才行。
– 每个节点都带有一个高度为1层的后退指针，用于从表尾方向表头方向迭代；当执行zrevrange或zrevrangebyscore类以逆序处理有序集的命令时，就会用到这个属性。
这个修改版的跳跃表由 redis.h/zskiplist 结构定义：
typedef struct zskiplist {
// 头节点，尾节点
struct zskiplistNode *header, *tail;
// 节点数量
unsigned long length;
// 目前表内节点的最大层数
int level;
} zskiplist;
跳跃表的节点由 redis.h/zskiplistNode 定义：
typedef struct zskiplistNode {
// member 对象
robj *obj;
// 分值
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 这个层跨越的节点数量
unsigned int span;
} level[];
} zskiplistNode;
redis> ZADD s 6 x 10 y 15 z
(integer) 3
redis> ZRANGE s 0 -1 WITHSCORES
1) "x"
2) "6"
3) "y"
4) "10"
5) "z"
6) "15"
在底层实现中， Redis 为 x 、 y 和 z 三个 member 分别创建了三个字符串， 值分别为 double 类型的 6 、 10 和 15 ， 然后用跳跃表将这些指针有序地保存起来， 形成这样一个跳跃表
http://leetcode-cn.com/problems/lru-cache (LRU缓存机制)运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。获取数据 get(key) 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。写入数据 put(key, value) – 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4