LRU（Least Recently Used）算法是一种常用的页面置换算法，它的基本思想是如果一个数据在最近一段时间没有被访问到，那么将来访问的可能性也很小。LRU算法的实现方式有很多，其中最常用的是基于双向链表的LRU算法，它的原理是把最近访问的数据结点放到链表的头部，当链表满了之后，再有新的数据访问时，就把链表最后的结点删除，把新的数据结点放到链表的头部。
LRU（Least Recently Used）算法是一种常用的页面置换算法，它的基本思想是如果一个数据在最近一段时间没有被访问到，那么将来访问的可能性也很小。
LRU算法的实现方式有很多，其中最常用的是基于双向链表的LRU算法，它的原理是把最近访问的数据结点放到链表的头部，当链表满了之后，再有新的数据访问时，就把链表最后的结点删除，把新的数据结点放到链表的头部。
以下是一个基于双向链表的LRU算法的Java实现：
public cl LRUCache {
private int capacity; // 容量
private Map
private Node head; // 头结点
private Node tail; // 尾结点
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>();
this.head = new Node(-1, -1);
this.tail = new Node(-1, -1);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (map.containsKey(key)) {
Node node = map.get(key);
int value = node.value;
removeNode(node);
addNode(node);
return value;
}
return -1;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.value = value;
removeNode(node);
addNode(node);
} else {
Node node = new Node(key, value);
if (map.size() == capacity) {
map.remove(tail.prev.key);
removeNode(tail.prev);
}
addNode(node);
map.put(key, node);
}
}
// 将结点添加到头结点之后
private void addNode(Node node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
// 将结点从双向链表中删除
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 双向链表的结点
cl Node {
int key;
int value;
Node prev;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
}
本站系公益性非盈利分享网址，本文来自用户投稿，不代表边看边学立场，如若转载，请注明出处
评论列表（21条）