1. 定义
LRU是Least Recentily Used的缩写，即最近最少使用。是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。
2. 算法描述
借用LeetCode第146题的描述，该题就是让实现一个LRUCache类。
实现LRUCache类:
- LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
- int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。
- void put(int key, int value)如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
要求在O(1)的时间复杂度内完成get和put操作。
示例:
LRUCache lRUCache = new LRUCache(2);
// 你可以把 lRUCache 理解成一个队列
// 假设左边是队头，右边是队尾
// 最近使用的排在队头，久未使用的排在队尾
// 圆括号表示键值对 (key, val)
lRUCache.put(1, 1);
//缓存是 {1=1}
lRUCache.put(2, 2);
//缓存是 {2=2, 1=1}
lRUCache.get(1)
// 返回 1
lRUCache.put(3, 3)
// 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2)
// 返回 -1 (未找到)
lRUCache.put(4, 4)
// 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);
// 返回 -1 (未找到)
lRUCache.get(3);
// 返回 3
lRUCache.get(4);
// 返回 4
3. 算法设计
分析上面的操作过程，要让 put 和 get 方法的时间复杂度为O(1)，我们可以总结出 lRUCache 这个数据结构必要的条件：
- lRUCache中的数据必须是有序的，最近使用的在队头，当队列满了之后，就删除队尾的元素。
- 在lRUCache中要根据指定key，得到对应的val。
- 每次调用lRUCache.get(key)方法时，要将查询到的元素，更新到队头。
首先要让元素有序，插入删除快的话，可以用链表，这里用双向链表，但是链表要查询某个值的话，就必须从头遍历，所以采用哈希链表的数据结构。
4. 代码实现
先总结下要实现哪些功能:
- 实现一个双向链表DoubleLinkedList,包括head、tail节点，长度size，addFirst(在链表头部添加节点)、remove(删除指定节点)、removeLast(删除链表中最后一个节点)以及size(返回链表长度方法)
- 实现链表中的节点Node,包括next、prev指针，一个构造方法
- 实现LRUCache类
Node类
package LeetCode.LRU;
public class Node {
//节点的next指针
public Node next;
//节点的prev指针
public Node prev;
public int key,value;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
DoubleLinkList类
package LeetCode.LRU;
/**
* 双向链表
*/
public class DoubleLinkList {
//头结点
private Node head;
//尾节点
private Node tail;
private int size;
public DoubleLinkList() {
head = new Node(0,0);
tail = new Node(0,0);
head.next = tail;
tail.prev = head;
this.size = 0;
}
//在链表头部添加节点
public void addFirst(Node node){
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
size++;
}
//删除链表中指定节点，该节点一定存在
public void remove(Node node){
node.prev.next = node.next;
node.next.prev = node.prev;
size--;
}
//删除链表中最后一个节点，并返回该节点，时间O(1)
public Node removeLast(){
if (head.next == tail){
return null;
}
Node last = tail.prev;
remove(last);
return last;
}
//返回链表长度
public int size(){
return size;
}
}
LRUCache类
package LeetCode.LRU;
import java.util.HashMap;
public class LRUCache {
private HashMap<Integer, Node> hashMap;
private DoubleLinkList cache;
private int cap;
public LRUCache(int capacity) {
hashMap = new HashMap<>();
cache = new DoubleLinkList();
this.cap = capacity;
}
//将某个 key 提升为最近使用的
private void makeRecently(int key){
Node node = hashMap.get(key);
//先删除该节点
cache.remove(node);
//将该节点添加到队头
cache.addFirst(node);
}
//添加最近使用的元素
private void addRecently(int key, int val){
Node newNode = new Node(key,val);
//在链表头部添加节点
cache.addFirst(newNode);
//在map里添加该节点
hashMap.put(key,newNode);
}
//删除某一个 key
private void deleteKey(int key){
Node node = hashMap.get(key);
cache.remove(node);
hashMap.remove(key);
}
//删除最久未使用的元素
private void removeLeastRecently(){
//链表的最后一个元素，就是最久未使用的
Node node = cache.removeLast();
hashMap.remove(node.key);
}
public int get(int key){
if (!hashMap.containsKey(key)){
return -1;
}
makeRecently(key);
return hashMap.get(key).value;
}
public void put(int key, int val){
//若key已存在
if (hashMap.containsKey(key)){
deleteKey(key);
addRecently(key, val);
return;
}
if (cap == cache.size()){
removeLeastRecently();
}
addRecently(key, val);
}
}
5. 测试类
package LeetCode.LRU;
public class TestLRU {
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(2);
lruCache.put(1,1);
lruCache.put(2,2);
lruCache.get(1);
lruCache.put(3,3);
lruCache.get(2);
lruCache.put(4,4);
lruCache.get(1);
lruCache.get(3);
lruCache.get(4);
}
}
6. LeetCode
写完这个就可以拿下LeetCode第146题。
