在Java中实现LRU Cache
，LRU（Least Recently Used，最近最少使用）是一种缓存淘汰算法，它根据数据的访问顺序来决定是否淘汰某个缓存项。以下是实现LRU Cache的步骤：
- 创建一个双向链表来维护缓存项的顺序，每个节点包含key和value两个属性。
- 创建一个HashMap来存储key和对应的节点对象，以实现快速查找。
- 设定缓存的容量大小，如果插入新的缓存项时超过容量大小，则需要删除最久未使用的缓存项。
- 在获取缓存项时，如果该项存在于缓存中，则将其移到链表的头部，表示最近使用过。
- 在插入新的缓存项时，如果该项已存在于缓存中，则更新其值，并将其移到链表头部。如果不存在于缓存中，则创建新的节点，并将其插入链表头部，同时将其添加到HashMap中。
- 在删除缓存项时，如果该项存在于缓存中，则将其从链表和HashMap中删除。
下面是一个示例代码实现：
import java.util.HashMap;
class LRUCache {
private int capacity;
private Node head;
private Node tail;
private HashMap<Integer, Node> map;
class Node {
int key;
int value;
Node prev;
Node next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (map.containsKey(key)) {
Node node = map.get(key);
remove(node);
addToHead(node);
return node.value;
}
return -1;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.value = value;
remove(node);
addToHead(node);
} else {
if (map.size() >= capacity) {
map.remove(tail.prev.key);
remove(tail.prev);
}
Node node = new Node(key, value);
map.put(key, node);
addToHead(node);
}
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addToHead(Node node) {
node.next = head.next;
node.next.prev = node;
node.prev = head;
head.next = node;
}
}上述代码使用双向链表和HashMap实现了LRU Cache。双向链表用于维护缓存项的顺序，HashMap用于实现快速查找。LRUCache类的构造函数初始化了缓存的容量、双向链表的头部和尾部节点，以及HashMap。get()方法根据缓存项的键获取对应的节点，并将该节点移到链表的头部，表示最近使用过。put()方法插入新的缓存项时，如果容量已满，则删除链表尾部的节点和对应的HashMap中的键值对，然后将新的节点插入链表头部，并加入HashMap中。如果缓存项已存在，则更新其值并将其移到链表头部。
这是一个简单的LRU Cache实现示例，适用于小规模的缓存场景。在实际应用中，还需要根据具体需求对LRU Cache进行性能优化和线程安全处理。
关于腾讯云相关产品和产品介绍链接地址，可以参考腾讯云官方文档：https://cloud.tencent.com/document/product/583
相关·内容
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM活动推荐
腾讯云开发者
