在前面的学习中，我们发现散列表经常会和链表放在一起使用，这是为什么呢？

        这节课我们就结合几个例子来看看为什么~       

    1LRU缓存淘汰算法

        LRU，顾名思义，Least Rencently Used，最近最少使用。

        借助散列表，我们可以把LRU缓存淘汰算法的时间复杂度降低为O(1)，现在我们来看看它是怎么做到的~

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

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

        当要缓存某个数据的时候，先在链表中查找这个数据。如果没有找到，则直接将数据放到链表尾部；如果找到了，就把它移动到链表尾部。

        因为查找数据需要遍历链表，所以单纯用链表实现的LRU缓存淘汰算法的时间复杂度很高，是O(n)。

        一个缓存（cache）系统主要包含下面这几种操作：

        往缓存中添加一个数据；

        从缓存中删除一个数据；

        从缓存中查找一个数据。

        这三个操作都要涉及“查找”操作。如果我们将散列表和链表两种数据结构组合使用，就可以将这三个操作的时间复杂度都降低到O(1)，具体的结构如下图所示：

        由上图我们可以看到，链表中的每个结点除了存储数据（data）、前驱指针（prev）、后继指针（next）外，还新增了一个特殊的字段hnext。

        因为散列表是通过链表法解决散列冲突的，所以每个结点会在两条链中。一个链是双向链表，另一个链是散列表中的拉链。前驱和后继指针是为了将结点串在双向链表中，hnext指针是为了将结点存在散列表的拉链中。

        OK，散列表和双向链表的组合结构就是这样的，我们再来看它是如何做到时间复杂度是O(1)的。

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

        其次，删除数据。我们通过O(1)的时间复杂度找到要删除的结点，因为链表是双向的，所以可以通过前驱指针获取前驱节点并删除，这个操作的时间复杂度是O(1)。因此，双向链表中删除结点只需要O(1)的时间复杂度。

        最后，添加数据。首先需要查看这个数据是否已经存在在缓存中，若存在，则将该结点移动到链表尾部；若不存在，则看缓存有没有满，若没有满，则插在链表尾部，若满了，则将头结点删除并将新结点插入尾部。而查找、删除、插入的操作，都可以在O(1)时间复杂度内完成。所以添加数据的时间复杂度是O(1)。

        至此，我们就通过散列表和双向链表的组合使用，实现了一个高效的、支持LRU缓存淘汰算法的缓存系统原型。

    2Redis有序集合

        在跳表那一节我们对有序其实作了一些简化，实际上，有序集合中的每个成员对象有两个重要属性，key（键值）和score（分值）。我们不仅会通过score来查找数据，还会通过key来查找数据。

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

    3Java LinkedHashMap

        Java LinkedHashMap是Java中的一种容器，HashMap底层是通过散列表这种数据结构实现的，而LinkedHashMap比HashMap多了一个“Linked”。

        其实，“Linked”也并不仅仅代表它是通过链表解决散列冲突的。

        我们先来看一段代码：

        这段代码的打印顺序会是什么样的呢？

        答案是：3，1，5，2

        但是会有一点比较奇怪的是，散列表中的数据是经过散列函数打乱之后无规律存储的，这里是如何实现按照数据的插入顺序来遍历打印的呢？

        其实，LinkedHashMap也是通过散列表和链表组合在一起实现的，实际上，它不仅支持按照插入顺序遍历数据，还支持按照访问顺序来遍历数据，可以看一下下面这段代码：

        它的打印结果是1，2，3，5。

        因为，每次调用put()函数，往LinkedHashMap中添加数据的时候，都会将数据添加到链表的尾部，所以，在前四个操作完成之后，链表中的数据是下面这样：

        第8行代码中，再次将键值为3的数据放入到LinkedHashMap的时候，会先查找这个键值是否已经有了，然后，再将（3,11）删除，并将新的（3,26）放到链表的尾部。所以，这个时候链表中的数据就是下面这样：

        当第9行代码访问到key为5的数据的时候，我们将被访问到的数据移动到链表的尾部。所以，第9行代码之后，链表中数据的顺序又变成了这样：

        因此，最后打印出来的顺序是1，2，3，5。

        其实呀，访问按照时间排序的LinkedHashMap本身就是一个支持LRU缓存淘汰策略的缓存系统，实际上它们的实现原理也是一模一样滴。

        总结一下，LinkedHashMap是通过双向链表和散列表这两种数据结构组合实现的，其中的“Linked”实际上是指的双向链表，并非指用链表法解决散列冲突。

    4散列表&双向链表|内容小结

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

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