LRU算法
LRU是一种页面置换算法，least recently used（最近最少使用）算法，意思是在发生缺页现象时，需要置换页面的时候，将最近最少使用的页面删除，添加需要的页面进来
LRU举例
下面我们来看看具体的LRU算法是如何工作的，我们假设内存页面有2块，每次访问内存时总会一次性读取一页的数据进来，当页面数量不够时，发生LRU置换：
有以下页面走向：1 2 3 2 4
每次请求页面的时候，都去寻找最近最不常使用的页面丢弃，将新页面加载进来
LRU题目
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：
- LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 - void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
思路分析
想要实现get和put的操作，想要用Key拿到Value嘛，很容易想到用HashMap来实现，这样子好像get的O（1）操作就完成了，返回一个value，其实不然，因为拿到值之后还需要调整顺序，以便后续让不经常使用的页面删除出去，于是想到用双向链表来存储节点，插入和删除节点都非常简单，但是如何定位这个节点的位置呢？比如我想删除key为2的节点，如果我要在链表中从头遍历一次，那么定位的时间复杂度就是O（n），能实现O（1）的复杂度就是HashMap，于是想到用HashMap来存储Key对应的节点，让key对应一个节点，节点中存储value，找到节点，对节点的前后进行调整，最后让节点挂到尾部表示最近挂载上去的，让删除节点从链表头开始。
get和put，分析如下几种情况：
- 通过key get到了节点
- 通过key 没get到节点
- put插入的时候已有
- 更新key对应的node中的value值，调整节点到链表尾部
- put插入的时候没有
代码实现
import java.util.HashMap;
public class LRUCache {
class Node {
int key;
int val;
Node next;
Node pre;
public Node(int key, int val, Node next, Node pre) {
this.key = key;
this.val = val;
this.next = next;
this.pre = pre;
}
}
HashMap<Integer, Node> nodeMap;
Node head;
Node tail;
int capacity;
int size;
LRUCache(int capacity) {
nodeMap = new HashMap<>();
head = tail = null;
this.size = 0;
this.capacity = capacity;
}
int get(int key) {
if (nodeMap.get(key) == null) {
return -1;
} else {
Node node = nodeMap.get(key);
if (node != tail) {
moveToTail(node);
}
return node.val;
}
}
private void moveToTail(Node node) {
if(node != head){
node.pre.next = node.next;
}else{
head = head.next;
}
node.next.pre = node.pre;
node.next = null;
node.pre = tail;
tail.next = node;
tail = node;
}
void put(int key, int value) {
if (nodeMap.get(key) != null) {
Node node = nodeMap.get(key);
node.val = value;
if (node != tail) {
moveToTail(node);
}
}else {
if (size < capacity) {
if (size == 0) {
Node node = new Node(key, value, null, null);
head = tail = node;
nodeMap.put(key, node);
} else {
Node node = new Node(key, value, null, tail);
addToTail(node);
}
size++;
} else {
Node node = new Node(key, value, null, tail);
addToTail(node);
removeHead();
}
}
}
private void removeHead() {
nodeMap.remove(head.key);
head = head.next;
head.pre = null;
}
private void addToTail(Node node) {
node.next = null;
tail.next = node;
tail = node;
nodeMap.put(node.key, node);
}
}
|