散列表和链表, 经常会被放在一起使用. 借助散列表, 我们可以把 LRU 缓存淘汰算法的时间复杂度降低为 O(1).

我们需要维护一个按照访问时间从大到小有序排列的链表结构. 因为缓存大小有限, 存空间不够, 需要淘汰一个数据的时候, 我们就直接将表头的节点删除.

当要缓存某个数据的时候, 先在链表中查找这个数据, 如果没有找到, 则直接将数据放到链表的尾部, 如果找到了, 我们就把它移动到链表的尾部. 因为查找数据需要遍历链表, 所以单纯用链表实现的 LRU 缓存淘汰算法的时间复杂度很高, 是 O(n).

一个缓存 (cache) 系统主要包含下面这几种操作:

往缓存中添加一个数据;
从缓存中删除一个数据;
在缓存中查找一个数据;

这三个操作都要涉及查找操作, 如果单纯的采用链表, 时间复杂度 O(n). 如果我们将散列表和链表两种数据结构组合使用. 可以将上面三个操作的时间复杂度都降到 O(1).

我们使用双向链表存储数据, 链表中的每个节点处理存储数据 (data), 前驱指针 (prev), 后继指针 (next) 之外, 还新增了一个特殊的字段 hnext, 这个 hnext 的作用如下:

因为散列表是通过链表发解决冲突的, 所以每个节点在两条链中. 一个链是双向链表, 另一个链是散列表中的拉链. 前驱和后继指针是为了将节点串在双向链表中, hnext 指针是为了将节点串在散列表的拉链中.

了解了这个散列表和双向列表的组合存储结构后, 我们再看下, 上面讲的缓存的三个操作, 是如何做到时间复杂度 O(1) 的.

我们来看下如何查找数据. 我们前面讲过, 散列表中查找树的时间复杂度接近 O(1), 所以通过散列表, 我们可以很快地在缓存中找到一个数据. 当找到数据之后, 我们还需要将它移动到双向链表的尾部.

接着我们再看下如何删除一个数据. 我们需要找到数据所在的节点, 然后将节点删除. 借助散列表, 我们可以在 O(1) 的时间复杂度里找到要删除的节点. 因为我们是双向链表, 双向链表可以通过前驱指针在 O(1) 的时间复杂度里获取前驱结点, 所以在双向链表中, 删除节点只需要 O(1) 的时间复杂度.

最后, 再看下如何添加一个数据. 添加数据到缓存稍微有点麻烦, 我们需要先看这个数据是否已经在缓存中. 如果已经存在. 需要将其移动到双向链表的尾部; 如果不在, 还要看缓存有没有满. 如果满了, 则将双向链表头部的节点删除. 然后再将数据放到链表的尾部; 如果没有满, 就直接将数据放到链表的尾部.

这个过程涉及到的查找操作都可以通过散列表来完成. 其他的操作, 比如删除头结点, 链表尾部插入数据等, 都可以在 O(1) 的时间复杂度内完成. 所以, 这三个操作的时间复杂度都是 O(1). 到这里, 我们就可以通过散列表和双向链表的组合使用, 实现一个高效的, 支持 LRU 缓存淘汰算法的缓存系统原型.

Reids 有序集合( Sorted Set)

在有序集合中, 每个成员对象有两个重要的属性, key(键值) he score(分值). 我们不仅会通过 score 来查找数据, 还会通过 key 来查找数据.

比如说 qq 获赞排行榜这个功能: 我们可以通过 userId 查找点赞信息, 也可以通过点赞次数的区间来查找 userId 或者姓名等信息. 这里包含 userId, 姓名和积分的用户信息, 这就是成员对象, userId 就是 key, 积分就是 score.

综上, 我们细化下 Redis 的有序集合的操作, 那就是下面所示的样子:

添加一个成员对象
按照指定的键值来删除一个成员对象
按照指定键值查找一个成员对象
按照点赞次数的区间查找数据, 比如查找点赞次数在 [100, 300] 之间的成员对象
按照点赞次数从小到大排序成员对象

如果我们仅仅按照分值将成员对象组织成跳表的结构, 那么按照键值来删除, 查询成员对象就会很慢, 解决的方法与 LRU 缓存淘汰算法解决方法类似. 我们可以再按照键值构建一个散列表, 这样按照 key 来删除, 查找一个成员对象的时间复杂度就变成了 O(1). 同时, 借助跳表结构, 其他操作也很高效.

散列表这种数据结构虽然支持高效的插入, 删除, 查找操作, 但是散列表中的数据都是通过散列函数打乱后无规律存储的. 换言之, 他无法按照某种顺序快速地遍历数据. 如果希望按照顺序遍历散列表中的数据, 那我们需要将散列表中的数据拷贝到数组中, 然后排序, 在遍历.

因为散列表是动态的数据结构, 不停地有数据插入, 删除. 所以每当我们希望按照顺序遍历散列表中的数据的时候, 都需要先排序, 那效率会很低. 为了解决这个问题, 我们将散列表和链表结合在一起用.