Java 中的 LRU 缓存实现

LRU 缓存（Least Recently Used Cache）的缩写是最近最少使用缓存。这意味着 LRU 缓存是指最近最少使用的那个缓存，其缓存大小或容量是固定的，允许用户使用 get() 和 put() 方法。当缓存满时，通过 put() 操作，它会移除最近最少使用的缓存。

在本 Java 部分，我们将简要介绍 LRU 缓存，其在 Java 中的实现，以及可以实现 LRU 缓存的几种方法。

什么是 LRU 缓存

大家可能都知道，缓存是计算机内存的一部分，用于临时存储频繁使用的数据。但是缓存内存的大小是固定的，因此需要一种管理机制来移除不需要的数据并存储新数据。这时 LRU 就派上用场了。因此，LRU 是一种缓存替换算法，用于通过移除最近最少使用的数据来为新数据腾出内存空间。

在 Java 中实现 LRU 缓存

要在 Java 中实现 LRU 缓存，我们可以通过以下两种数据结构来实现 LRU 缓存：

队列： 使用双向链表，可以实现一个队列，队列的最大大小将等于缓存大小（总帧数）。很容易发现最近最少使用的页面位于队头附近，而最近最少使用的页面位于双向链表的队尾附近。

哈希： 这里的键代表页码的哈希值，值代表相应队列节点的地址。

理解 LRU

每当用户引用一个页面时，可能会有两种情况。一种是页面已在内存中，如果是，则只需将链表节点分离并将其移到队列的前面。另一种是页面不在内存中（不存在），则将其移入内存。为此，用户在队列前面插入一个新节点，然后更新哈希表中相应节点的地址。如果用户确定队列已满（所有帧都已满），只需从队尾移除一个节点，然后在队列前面添加新节点。

LRU 示例

给定如下引用字符串：

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

因此，使用 LRU 页替换算法，可以找到页面数为 3 时的缺页次数。

在下面的图表中，您可以看到我们如何执行 LRU 算法来查找缺页次数。

通过队列实现 LRU 缓存

要通过队列实现 LRU 缓存，我们需要使用双向链表。尽管代码足够长，但这是 LRU 缓存的基本实现版本。

以下是代码：

代码解释

• 在上面的代码中，我们导入了内置的 Deque 包和所有其他集合类，并创建了一个实现了 main() 方法的 lru 类。
• 实现了一个 Cache 类，其中声明了两个变量（key 和 value），key 用于访问实际数据，value 用于缓存访问数据。
• 接下来，通过创建 Cache 类的构造函数，我们设置了两个变量的值。
• 进入 lru 类，我们声明了一个充当缓存以存储数据的队列和一个用于存储数据项键值对的 Map。变量 CACHE_CAPACITY 的值设置为 4。
• 接下来，实现了一个 getElementFromCache(int key) 方法，如果 key 已存在，则从缓存中获取数据。在其中，如果项存在于缓存中，则将其移除并添加到缓存的前面。如果不存在，则返回没有这样的元素。
• 现在，使用 map，我们检查元素是否已存在于缓存中，为此，实现了另一个方法 putELementCache(nt key, String value)。在其中，如果元素已存在于缓存中，则将其移除。否则，如果缓存已满，则从队列末尾移除一个元素。之后，只需在队列中添加已存在的元素或具有给定键和值的元素。
• 在 main() 方法中，我们调用了我们在 main() 方法中创建的方法。

因此，执行上述代码后，我们得到了下面显示的输出：

使用 LinkedHashMap 实现 LRU 缓存

LinkedHashMap 类似于 HashMap，但在 LinkedHashMap 中，有一个功能允许用户维护插入到 LinkedHashMap 中的元素的顺序。因此，LinkedHashMap 的此功能使 LRU 缓存实现变得简单而简短。如果使用 HashMap 实现，我们会得到不同的元素序列，因此我们可能需要编写更多代码来排列这些元素，但使用 LinkedHashMap，我们无需增加更多代码行。

以下是让您使用 LinkedHashMap 实现 LRU 缓存的代码：

代码解释

• 在上面的代码中，我们创建了一个 lru 类并使用 LinkedHashSet 实现程序。
• 我们声明了一个缓存和一个容量变量，并通过构造函数设置了它们的值。
• 接下来，我们创建了一个布尔返回值函数 get()，如果 key 不存在于缓存中，则返回 false。否则，它会先移除 key，然后将其移到前面。然后添加它，最后返回布尔 true。
• 之后，我们创建了一个 get_Value 函数，如果 get(key)==false，则调用 put(key)。
• 然后我们创建了一个 display() 函数来按相反的顺序显示缓存的元素。
• 最后，执行 main() 方法。

当我们执行上述代码时，我们得到了下面显示的输出：

从输出中可以清楚地看出，与上面一个相比，我们用更少的代码行获得了正确的结果。

因此，这样我们就可以在 Java 中实现 LRU 缓存并对其进行表示。