数据结构和算法之——散列表下
散列表和链表经常组合起来使用，但它们是如何组合起来使用的，为什么它们会经常一块使用呢？
1. LRU 缓存淘汰算法？
基于链表实现 LRU 缓存淘汰算法的原理是这样的：我们维护一个有序单链表，越靠近链表头部的结点是越早访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
- 如果此数据之前已经被缓存在链表中了，我们将其从原来的位置删除，然后再插入到链表的尾部。
如果此数据没有缓存在链表中，又可以分为两种情况：
- 如果缓存未满，直接将此结点插入到链表的尾部
- 如果缓存已满，则将链表尾结点删除，然后再将新的数据结点插入到链表的尾部
因为不管缓存是否已满，我们都需要遍历一遍链表，因此，基于链表实现的缓存访问的时间复杂度为 $O(n)$。
一个缓存（cache）系统主要包含下面这几个操作：
- 往缓存中添加一个数据
- 从缓存中删除一个数据
- 在缓存中查找一个数据
如果我们将散列表和链表两种数据结构结合起来使用，可以将这几个操作的时间复杂度都降低到 $O(1)$。
具体的结构就是下面这个样子：
使用双向链表来存储数据，链表中的每个结点包括数据（data）、前驱指针（prev）、后继指针（next）还有一个特殊的 hnext 指针。
因为我们使用链表法来解决散列冲突，所以每个结点都会在两条链中存在。一个链是上面的双向链表，另一个链则是散列表中散列值相同的元素组成的拉链。前驱和后继指针是为了将结点串在双向链表中，hnext 指针是为了将结点串在散列表的拉链中。
查找数据的时候，我们通过散列表可以在时间复杂度接近于 $O(1)$ 内找到一个数据，然后，我们再将其移动到双向链表的尾部。
删除数据的时候，我们在时间复杂度接近于 $O(1)$ 内找到要删除的结点，然后由于是双向链表，我们可以直接得到前驱指针，删除结点也只需要 $O(1)$ 的时间复杂度。
添加数据的时候，类似于单链表的情况，我们也可以在 $O(1)$ 时间复杂度内完成。
而其他操作，比如删除头结点、尾部插入数据等，都可以在 $O(1)$ 时间复杂度内完成。因此，我们就通过散列表和双向链表的组合使用，实现了一个高效的、支持 LRU 缓存淘太算法的缓存系统原型。
2. Redis 有序集合？
在 跳表 中，我们实现了一个简单的有序集合。但实际上，在有序集合中，每个成员对象有两个重要的属性，key （键值）和 score （分值）。我们不仅会通过 score 来查找数据，还会通过 key 来查找数据。
因此 Redis 有序集合的操作主要有以下几种：
- 添加一个成员对象
- 按照键值来删除一个成员对象
- 按照键值来查找一个成员对象
- 按照分值区间查找数据
- 按照分值从小到大排序成员变量
如果我们仅仅按照分值将成员对象组织成跳表的结构，那按照键值来删除、查找成员对象就会很慢，解决方法与 LRU 缓存淘太算法的解决方法类似。我们可以再按照键值构建一个散列表，这样按照键值来删除、查找成员对象的时间复杂度就变成了 $O(1)$。
3. Java LinkedHashMap？
HashMap<Integer, Integer> m = new LinkedHashMap<>();
m.put(3, 11);
m.put(1, 12);
m.put(5, 23);
m.put(2, 22);
for (Map.Entry e : m.entrySet()) {
System.out.println(e.getKey());
}这段代码的输出是 3, 1, 5, 2，你有没有觉得奇怪？散列表中的数据是经过散列函数打乱之后无规律存储的，这里是如何按照数据的插入顺序来遍历输出的呢？
其实，LinkedHashMap 也是通过散列表和链表结合在一起实现的。实际上，它不仅支持按照插入顺序遍历数据，还支持按照访问顺序来遍历数据。
// 10 是初始大小，0.75 是装载因子，true 是表示按照访问时间排序
HashMap<Integer, Integer> m = new LinkedHashMap<>(10, 0.75f, true);
m.put(3, 11);
m.put(1, 12);
m.put(5, 23);
m.put(2, 22);
m.put(3, 26);
m.get(5);
for (Map.Entry e : m.entrySet()) {
System.out.println(e.getKey());
}这段代码的输出是 1, 2, 3, 5，我们来具体看一下。
每次调用 put() 函数，都会将数据添加到链表的尾部，前四个操作后，链表中的数据是下面这样：
在第八行，当我们再次将键值为 3 的数据放入到 LinkedHashMap 中去的时候，就会先查找这个键值是否已经存在。然后，将已经存在的 (3, 11) 删除，并将新的 (3, 26) 放到链表尾部。
在第九行，当我们访问键值为 5 的数据的时候，我们将被访问的数据移动到链表尾部。
可以看到，按照访问时间排序的 LinkedHashMap 本身就是一个支持 LRU 缓存淘汰策略的缓存系统。 LinkedHashMap 中的 Linked 实际上指的是双向链表。
4. 小结？
散列表这种结构虽然支持非常高效的数据插入、删除、查找操作，但是散列表中的数据都是通过散列函数打乱之后无规率存储的。也就是说，它无法支持按照某种顺序快速地遍历数据。
如果希望按照顺序遍历散列表中的数据，那我们需要将散列表中的数据拷贝到数组中，然后排序遍历。
但是，散列表是动态数据结构，需要不停地插入、删除数据，若每次遍历数据都需要先排序，那效率势必很低。
为了解决这个问题，我们就将散列表和链表（或者跳表）结合在一起使用。
获取更多精彩，请关注「seniusen」! 