找到了吗？ 有两种数据结构。 散列表和链表经常被一起使用。

在

LRU缓存淘汰算法

链表的部分中，我们提到了使用哈希表可以将LRU缓存丢弃算法的时间复杂度降低到o(1)。 那么，让我们来看看怎么能做到这一点。

首先，让我们回顾一下LRU缓存处置算法是如何在链表中实现的。

需要根据访问时间维持按从大到小顺序排列的链表结构。 如果由于缓存大小有限，缓存空间不足，需要丢弃数据，请直接删除链表开头的节点。

缓存某个数据时，首先在链表中查找该数据。 如果找不到，直接将数据放在链表的末尾。 找到后，移动到链表的末尾。 由于查找数据需要遍历链表，因此单纯通过链表实现的LRU缓存丢弃算法时间复杂且为o(n )。

总结起来，缓存系统主要包括以下操作：

向缓存中添加数据从缓存中删除数据； 搜索缓存中的数据。 这三个操作都与“查找”操作有关，如果简单地采用链表，时间的复杂性只有o(n )。 结合哈希表和链表两种数据结构，可以将这三种操作的时间复杂度降低到o(1)。 具体结构如下。

使用双向链表存储数据。 链表中的每个节点除了存储数据(data )、前向指针(prev )和后向指针(next )之外，还添加了特殊的字段hnext。 这个hnext有什么作用？

因为我们的哈希表通过链表法解决哈希冲突，所以每个节点都在两条链上。 一条链是我刚才提到的双向链表，另一条链是散列表的拉链。 前驱和后续的指针是为了将节点连接到双向链表上，hnext指针是为了将节点连接到哈希表的拉链上。

在了解了这个哈希表和双向链表的组合存储结构之后，我们来看看前面提到的缓存的三个操作是如何使时间复杂度达到o(1)的。

首先，让我们来看看如何找到数据。 如上所述，在散列表中查找数据的时间复杂度接近o(1)，因此使用散列表可以很快找到缓存中的数据。 找到数据后，必须移动到双向链表的末尾。

接下来，让我们来看看如何删除数据。 必须找到具有数据的节点，然后删除该节点。 通过哈希表，可以在o(1)时间的复杂性中查找要删除的节点。 因为我们的链表是双向链表，双向链表可以通过前驱指针o(1)的时间复杂度获取前驱节点，所以在双向链表中删除节点只需要o )1)的时间复杂度。

最后，让我们来看看如何添加数据。 向缓存中添加数据有点麻烦。 首先，需要确认这个数据是否已经在缓存中。 如果已经在其中，则需要移动到双向链表的末尾； 如果不在其中，也要检查缓存是否已满。 满后，删除双向链表开头的节点，然后将数据放在链表末尾。 如果未满，则将数据直接放在链表的末尾。

可以使用散列表执行涉及整个过程的搜索操作。 其他操作，例如删除头节点、在链表末尾插入数据等，可以在o(1)的时间复杂度内进行。 因此，这三种操作的时间复杂度都是o(1)。 到目前为止，通过结合使用哈希表和双向链表，实现了高效、支持LRU缓存丢弃算法的缓存系统原型。

Redis有序集合

实际上，在规则集合中，每个成员对象都有两个重要的属性：密钥(键值)和得分)。 我们不仅在score上搜索数据，也在key上搜索数据。

例如，用户积分排名具有根据用户ID搜索积分信息，或者在积分区间搜索用户ID和名称信息的功能。 这里包含ID、名称、点的用户信息为成员对象，用户ID为key，点为score。

因此，如果细化Redis有序集合的操作，则如下所示。

添加成员对象； 根据键值删除成员对象； 根据键值搜索成员对象； 按分数区间搜索数据，例如搜索点位于[ 100，356 ]之间的成员对象。 按得分从小到大的顺序对成员变量进行排序； 如果只根据分数将成员对象组织到跳转表的结构中，则根据键值删除和查询成员对象会比较慢。 解决方法类似于LRU缓存处置算法的解决方法。 通过基于键值创建哈希表，基于key删除和搜索成员对象的时间复杂度变为o(1)。 另外，通过跳转表结构，其他操作也非常高效。

事实上，Redis规则集合的操作还有另一个类别。 也就是说，它会根据要在其中搜索成员对象的排名(Rank )或排名部分来搜索成员对象。 该功能仅靠刚才所述的组合结构是无法有效实现的。

Java链接的散列图

我之前说过将两个散列表和链表组合在一起的例子，我们再来看看Java的一个叫做LinkedHashMap的容器。

如果熟悉Java的话，几乎每天都使用这个容器。 如前所述，HashMap的基础是通过一种叫做散列表的数据结构实现的。 另一方面，在LinkedHashMap之前，比HashMap多了一个“Linked”。 这里的“Linked”是指LinkedHashMap是用链表方法解决散列冲突的散列表吗？

实际上，LinkedHashMap并没有这么简单，其中的“Linked”也并不仅仅代表它是通过链表法解决散列冲突的。关于这一点，在我是初学者的时候，也误解了很久。

我们先来看一段代码。你觉得这段代码会以什么样的顺序打印3，1，5，2这几个key呢？原因又是什么呢？

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()函数，往LinkedHashMap中添加数据的时候，都会将数据添加到链表的尾部，所以，在前四个操作完成之后，链表中的数据是下面这样：

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

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

所以，最后打印出来的数据是1，2，3，5。从上面的分析，你有没有发现，按照访问时间排序的LinkedHashMap本身就是一个支持LRU缓存淘汰策略的缓存系统？实际上，它们两个的实现原理也是一模一样的。我也就不再啰嗦了。

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

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

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

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