散列表 三

一、为什么散列表和链表经常放在一起使用?

1.散列表的优点:支持高效的数据插入、删除和查找操作

2.散列表的缺点:不支持快速顺序遍历散列表中的数据

3.如何按照顺序快速遍历散列表的数据?只能将数据转移到数组，然后排序，最后再遍历数据。

4.我们知道散列表是动态的数据结构，需要频繁的插入和删除数据，那么每次顺序遍历之前都需要先排序，这势必会造成效率非常低下。

5.如何解决上面的问题呢?就是将散列表和链表(或跳表)结合起来使用。

二、散列表和链表如何组合起来使用?

LRU缓存淘汰算法

借助散列表，我们可以把LRU缓存淘汰算法的时间复杂度降低为O(1)。

首先，我们来回顾一下当时我们是如何通过链表实现LRU缓存淘汰算法的。

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

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

实际上，我总结一下，一个缓存(cache)系统主要包含下面这几个操作:

1.往缓存中添加一个数据;

2.从缓存中删除一个数据;

3.在缓存中查找一个数据。

这三个操作都要涉及“查找”操作，如果单纯地采用链表的话，时间复杂度只能是O(n)。如果我们将散列表和链表两种数据结构组合使用，可以将这三个操作的时间 复杂度都降低到O(1)。

具体的结构就是下面这个样子:

image.png

我们使用双向链表存储数据，链表中的每个结点处理存储数据(data)、前驱指针(prev)、后继指针(next)之外，还新增了一个特殊的字段hnext。这个hnext有 什么作用呢?

因为我们的散列表是通过链表法解决散列冲突的，所以每个结点会在两条链中。一个链是刚刚我们提到的双向链表，另一个链是散列表中的拉链。前驱和后继指针是为了将结点串在双向链表中，hnext指针是为了将结点串在散列表的拉链中。 了解了这个散列表和双向链表的组合存储结构之后，我们再来看，前面讲到的缓存的三个操作，是如何做到时间复杂度是O(1)的?

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

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

最后，我们来看如何添加一个数据。添加数据到缓存稍微有点麻烦，我们需要先看这个数据是否已经在缓存中。如果已经在其中，需要将其移动到双向链表的尾

部;如果不在其中，还要看缓存有没有满。如果满了，则将双向链表头部的结点删除，然后再将数据放到链表的尾部;如果没有满，就直接将数据放到链表的尾

部。

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

结论：

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

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

作者：尼桑麻

链接：https://www.jianshu.com/p/27637cb2fd9e

来源：简书

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。