保定网站设计制作需要多少钱_公司企业网站维护_软件开发公司推荐_汕头网站建设技术外包

时间:2025/7/13 3:50:55来源：https://blog.csdn.net/NiNg_1_234/article/details/142455134 浏览次数:0次

Java实现LRU（最近最少使用）算法

一、引言

LRU（Least Recently Used）算法，即最近最少使用算法，是一种常见的缓存淘汰策略。它基于局部性原理，即最近被访问的数据在未来一段时间内被访问的概率更高，而长时间未被访问的数据在未来一段时间内被访问的概率较低。在Java中实现LRU算法，可以有效地管理缓存数据，提高系统性能。

二、实现方式

在Java中实现LRU算法主要有两种方式：使用LinkedHashMap和自定义双向链表结合HashMap。

1、使用`LinkedHashMap`

Java的LinkedHashMap类提供了一个按访问顺序排序的功能，可以用来实现LRU缓存。通过设置accessOrder为true，LinkedHashMap会将最近访问的元素移动到链表的末尾，而最老的元素（链表的头部）则是最少被访问的元素。

1.1、步骤

创建一个LinkedHashMap实例，并设置一个初始容量和加载因子。
通过put和get方法操作缓存，LinkedHashMap会自动维护元素的访问顺序。
重写removeEldestEntry方法，当缓存容量超出限制时，自动移除最老的元素。

2、自定义双向链表结合`HashMap`

这种方式需要自己实现一个双向链表来维护缓存数据的顺序，同时使用HashMap来存储键和对应节点的引用，以实现快速查找。

2.1、步骤

定义一个双向链表节点类，包含键、值、前驱和后继指针。
创建一个缓存类，内部包含一个HashMap和一个双向链表。
在get和put方法中，根据访问情况更新节点在链表中的位置。
当缓存容量超出限制时，移除链表尾部的节点，即最老的元素。

三、代码实现

1、使用`LinkedHashMap`

/*** @author ning0* @date 2024/9/23 12:03* @description Main**/
import java.util.LinkedHashMap;
import java.util.Map;public class LRUCache<K, V> extends LinkedHashMap<K, V> {private final int capacity;public LRUCache(int capacity) {super(capacity, 0.75f, true);this.capacity = capacity;}@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > capacity;}public static void main(String[] args) {LRUCache<Integer, String> cache = new LRUCache<>(3);cache.put(1, "one");cache.put(2, "two");cache.put(3, "three");cache.get(2); // 访问2，将其移到链表尾部cache.put(4, "four"); // 容量超出，移除最老的元素1System.out.println(cache.keySet()); // 输出：[3, 2, 4]}
}

2、自定义双向链表结合`HashMap`


/*** @author ning0* @date 2024/9/23 12:03* @description Main**/import java.util.HashMap;
import java.util.Map;class LRUCache<K, V> {private final int capacity;private final Map<K, Node<K, V>> map;private final Node<K, V> head, tail;public LRUCache(int capacity) {this.capacity = capacity;map = new HashMap<>();head = new Node<>(null, null);tail = new Node<>(null, null);head.next = tail;tail.prev = head;}public V get(K key) {Node<K, V> node = map.get(key);if (node == null) return null;moveToHead(node);return node.value;}public void put(K key, V value) {Node<K, V> node = map.get(key);if (node == null) {node = new Node<>(key, value);map.put(key, node);addNode(node);if (map.size() > capacity) {map.remove(tail.prev.key);removeNode(tail.prev);}} else {node.value = value;moveToHead(node);}}private void addNode(Node<K, V> node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}private void removeNode(Node<K, V> node) {node.prev.next = node.next;node.next.prev = node.prev;}private void moveToHead(Node<K, V> node) {removeNode(node);addNode(node);}class Node<K, V> {K key;V value;Node<K, V> prev;Node<K, V> next;Node(K key, V value) {this.key = key;this.value = value;}}@Overridepublic String toString() {StringBuilder sb = new StringBuilder("[");Node<K, V> curr = head.next;while (curr != tail) {sb.append(curr.key).append(", ");curr = curr.next;}return sb.delete(sb.length() - 2, sb.length()).append("]").toString();}public static void main(String[] args) {LRUCache<Integer, String> cache = new LRUCache<>(3);cache.put(1, "one");cache.put(2, "two");cache.put(3, "three");cache.get(2); // 访问2，将其移到链表头部cache.put(4, "four"); // 容量超出，移除最老的元素1System.out.println(cache); // 输出：[4, 2, 3]}
}