在数据结构中，散列表和链表经常会组合在一块使用，如果你对java很熟悉，你会发现LinkedHashMap这样一个常用的容器，也把散列表和链表组合起来使用。那散列表和链表是如何组合使用的，他们组合在一起能碰撞出什么火花，请跟随我的脚步，一起一探究竟。
我们先思考这么一个问题，如何使用链表来实现LRU缓存呢？如果对LRU不熟，可以看这篇文章。
我们可以维护一个有序的单链表，越靠近链表尾部的结点是越早访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历。遍历的结果有两种情况。
如果此数据之前就已经被缓存在链表中，我们遍历得到这个数据对应的结点，然后将其从这个位置移动到链表的头部。
如果此数据不在链表中，又会分为两种情况。如果此时缓存链表没有满，我们直接将该结点插入链表头部。如果此时缓存链表已经满了，我们从链表尾部删除一个结点，然后将新的数据结点插入到链表头部。
这样我们就用链表实现了一个LRU缓存，我们接下来分析一下缓存访问的时间复杂度。因为不管缓存有没有满，我们都需要遍历一遍链表，所以基于链表实现的LRU缓存，缓存访问的时间复杂度是O(n)。
那有没有什么方法可以减低时间复杂度呢？我们先来分析一下缓存的常用操作。对于一个缓存来说，主要涉及以下三种操作：
往缓存添加一个元素。
从缓存中删除一个元素。
在缓存中查找一个元素。
这三个操作都会涉及到查找的操作，如果单纯的使用链表，时间复杂度只能是O(n)。大家都知道散列表的查找操作是O(1)，那我们能不能把散列表和链表结合起来使用，将缓存的这三个常用操作的时间复杂度减低到O(1)呢？答案是肯定的，我们来看一下他们是如何组合在一起的。
如图所示，我们使用双向链表来存储数据，链表中的每个结点除了数据（data）、前驱指针（pre）、后继指针（next）之外，还新增了一个特殊的字段 hnext。这个hnext有什么作用呢？因为我们的散列表是通过链表法解决散列冲突的，所以每个结点会在两条链中。一个链是刚刚我们提到的双向链表，另一个链是散列表中的拉链。前驱和后继指针是为了将结点串在双向链表中，hnext 指针是为了将结点串在散列表的拉链中。
了解了这个散列表和双向链表的组合存储结构之后，我们再来看，前面讲到的缓存的三个操作，是如何做到时间复杂度是 O(1) 的？
首先，我们来看如何查找一个数据。我们前面讲过，散列表中查找数据的时间复杂度接近 O(1)，所以通过散列表，我们可以很快地在缓存中找到一个数据。当找到数据之后，我们还需要将它移动到双向链表的尾部。
其次，我们来看如何删除一个数据。我们需要找到数据所在的结点，然后将结点删除。借助散列表，我们可以在 O(1) 时间复杂度里找到要删除的结点。因为我们的链表是双向链表，双向链表可以通过前驱指针 O(1) 时间复杂度获取前驱结点，所以在双向链表中，删除结点只需要 O(1) 的时间复杂度。
最后，我们来看如何添加一个数据。添加数据到缓存稍微有点麻烦，我们需要先看这个数据是否已经在缓存中。如果已经在其中，需要将其移动到双向链表的头部；如果不在其中，还要看缓存有没有满。如果满了，则将双向链表尾部的结点删除，然后再将数据放到链表的头部；如果没有满，就直接将数据放到链表的头部。这整个过程涉及的查找操作都可以通过散列表来完成。
其他的操作，比如删除头结点、链表尾部插入数据等，都可以在 O(1) 的时间复杂度内完成。所以，这三个操作的时间复杂度都是 O(1)。至此，我们就通过散列表和双向链表的组合使用，实现了一个高效的、支持 LRU 缓存淘汰算法的缓存系统原型。
所以，可以通过散列表和链表结合的方式，实现一个时间复杂度为O(1)的LRU缓存。
更多硬核知识，请关注公众号”"。