第二十节-散列表（下）

为什么散列表和链表经常会一起使用？

因为散列表有 O(1) 的时间查找、删除数据的特性，但是元素是无序的。而链表中的数据可以是有序的，可以顺着指针按顺序遍历所有节点，但是在链表中查找数据的时间是 O(n)。

很明显，通过时间换空间，我们同时对一组数据建立链表和散列表两种数据结构，并且组合在一起，就可以构造出一种兼具两者优点的数据结构——快速的插入、查找、删除和按顺序遍历功能。

这个组合的数据结构示意图如下：

同样的道理，如果我们组合的散列表 + 跳表，我们就可以在上面的基础上额外获得在 O(logn) 的时间内定位元素区间的数据的功能。

课后思考

1. 今天讲的几个散列表和链表组合使用的例子里，我们用的都是双向链表，如果把双向链表改成单链表，还能否正常工作？为什么呢？

• 对于 LRU 缓存淘汰算法，可以改装成单链表

在这个算法里，我们使用链表主要是为了维护有序性（按照元素访问的顺序排列），并不需要逆序输出序列，此时对链表的要求只是删除一个节点，然后把这个节点插入到链表的尾端。我们可以通过特殊的技巧，把下一个节点的数据移到这个节点，然后下个节点来达到类似删除本节点的效果。这个删除时间同样是 O(1)，除了删除的节点是尾节点，就需要 O(n) 的时间找到它的上一个节点。

• 对于需要逆序输出一个区间的数据的情况，最好使用双链表

2. 假设猎聘网有 10 万名猎头，每个猎头都可以通过做任务（比如发布职位）来积累积分，然后通过积分来下载简历。假设你是猎聘网的一名工程师，如何在内存中存储这 10 万个猎头 ID 和积分信息，让它能够支持这样几个操作：

• 根据猎头的 ID 快速查找、删除、更新这个猎头的积分信息；
• 查找积分在某个区间的猎头 ID 列表；
• 查找按照积分从小到大排名在第 x 位到第 y 位之间的猎头 ID 列表。

对于这个问题，我们可以维护一个散列表 + 跳表的结构。

散列表的 key 存放猎头的 ID，跳表的索引存放猎头的积分，每次猎头的积分发生变化，就从跳表中删除这个节点，再在合适的位置重新插入这个节点，达到维持底层链表有序性的效果。

这样实现起来，按照 ID 查找、删除猎头的积分信息的效率是 O(1)，更新积分的效率是 O(logn)，查找积分区间的猎头的时间是 O(logn)。但是最后一个操作暂时还不知道怎么实现。