Least Recently Used(LRU) 是缓存淘汰一种常用的策略,内存满了则优先删除最久没被使用的数据。
LRU 算法的需求
- 接收一个参数
capacity
作为缓存的最大容量 - 实现一个函数
put()
添加数据到缓存 - 实现一个函数
get()
查询缓存中的数据 - 以上函数应该在 \(O(1)\) 的时间内完成
满足以上需求的数据结构 —— 哈希表 + 双向链表,通过哈希表快速定位到链表中的节点,然后完成添加、删除等操作。文章来源:https://www.toymoban.com/news/detail-505252.html
LRU 算法的实现
节点定义
public class Node {
public int key;
public String data;
public Node next;
public Node prev;
public Node(int key, String data) {
this.key = key;
this.value = value;
this.next = null;
this.prev = null;
}
}
双向链表
public class MyLinkedList {
private Node head; // 头节点
private Node tail; // 尾节点
private int size;
public MyLinkedList() {
this.head = new Node(-1, "head");
this.tail = new Node(-1, "tail");
head.next = tail;
tail.prev = head;
this.size = 0;
}
// 添加新的数据到缓存
public void addLast(Node node) {
node.prev = tail.prev;
node.next = tail;
tail.prev.next = node;
tail.prev = node;
this.size += 1;
}
// 删除缓存中的某项数据
public void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
this.size -= 1;
}
// 缓存空间已满,删除最早未被使用的数据
public Node removeFirst() {
if (head.next == tail) {
return null;
}
Node first = head.next;
remove(first);
return first;
}
public int size() {
return this.size;
}
}
LRU Cache
目前使用的双向链表支持从尾部插入,即尾部为最新的数据,头部则是最久未被使用的数据。文章来源地址https://www.toymoban.com/news/detail-505252.html
public class LRUCache {
private Map<Integer, Node> map;
private MyLinkedList cache;
private int capacity;
public LRUCache(int capacity) {
this.map = new HashMap<>();
this.cache = new MyLinkedList();
this.capacity = capacity;
}
public String get(int key) {
if (!map.containsKey(key)) {
return null;
}
makeRecently(key);
return map.get(key).data;
}
/**
* 1. 判断 key 是否已存在于缓存,若已存在则更新对应的data,并设置为最新使用即添加到队尾
* 2. 判断缓存空间是否已满,若已满则删除最久未使用的数据
*/
public void put(int key, String data) {
if (map.containsKey(key)) {
deleteKey(key);
addRecently(key, data);
return;
}
// 缓存空间已满
if (this.capacity == cache.size()) {
removeLeastRecently();
}
addRecently(key, data);
}
private void addRecently(int key, String data) {
Node node = new Node(key, data);
cache.addLast(node);
map.put(key, node);
}
private void makeRecently(int key) {
Node node = map.get(key);
cache.remove(node);
cache.addLast(node);
}
private void deleteKey(int key) {
Node node = map.get(key);
cache.remove(node);
map.remove(key);
}
/**
* 删除最久未被使用的数据
*/
private void removeLeastRecently() {
Node node = cache.removeFirst();
map.remove(node.key);
}
}
到了这里,关于LRU 缓存淘汰算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!