1. 什么是LRU
LRU（Least Recently Used），即最近最少使用策略，是一种常用的页面置换算法。
比如当缓存数据在内存越来越多，以至于无法存放即将到来的新缓存数据时，就必须扔掉最不常用的缓存数据。
最新被访问的数据【get、put操作】的‘优先级’是最高的，当缓存达到一定容量时，之前最早被访问的数据将会被清除。
Redis 就使用了LRU作为缓存淘汰策略。
2、设计一个简单的LRUCache【leetcode146】
LRUCache支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
要求get、put操作时间复杂度为O(1).
3、思路
LRU可以用哈希链表实现，即哈希表+双向链表，链表中的node存储了同时存储了缓存的【key和value】，哈希表中存储key和node，这样get操作时能通过key查找到node的地址获取value值，同时get、put操作时间复杂度为O(1)。
在双向链表中，把最新操作【get、put操作】过的node移动到队尾。那么越靠近对尾的元素就是最新被操作的元素。
当缓存达到一定的容量时候，要删除队头的元素。
image.png
4、实现
哈希表+双向链表
/**
* 设计双向链表的Node结构
* key:表示缓存的key，存在Node是为了在后边删除缓存的操作中，删除map和双向链表中的记录
* val:表示缓存的值
*/
class Node {
int key;
int val;
Node pre;
Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
class DoubleList {
Node head;
Node tail;
public DoubleList() {
}
/**
* 因为新加入的节点是最新被访问的，所以将新加入的节点放入对尾
* @param node
*/
public void addToTail(Node node) {
if (node == null) {
return;
}
if (this.head == null) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
node.pre = this.tail;
this.tail = node;
}
}
/**
* 将某个节点放到对尾
* @param node
*/
public void moveNodeToTail(Node node) {
if (node == null || node == this.tail) {
return;
}
if (node == this.head) {
this.head = this.head.next;
this.head.pre = null;
} else {
node.pre.next = node.next;
node.next.pre = node.pre;
}
this.tail.next = node;
node.pre = this.tail;
node.next = null;
// 更新tail不要忘了
this.tail = node;
}
/**
* 删除对头，也就是删除最没有被访问的元素
* @return
*/
public Node removeHead() {
if (this.head == null) {
return null;
}
Node res = this.head;
// 如果只有一个节点
if (this.head == this.tail) {
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
this.head.pre = null;
}
return res;
}
}
/**
* LRU缓存结构
*/
class LRUCache {
Map<Integer, Node> map = new HashMap<>();
DoubleList doubleList = new DoubleList();
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
}
/**
* 获取指定key 的 value值，同时需要更新被访问的元素的优先级，将其放到对尾
* @param key
* @return
*/
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
Node res = map.get(key);
doubleList.moveNodeToTail(res);
return res.val;
}
/**
* 插入一对新的缓存，如果队列已满，需要先删除队头
* @param key
* @param value
*/
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.val = value;
map.put(key, node);
doubleList.moveNodeToTail(node);
} else {
Node node = new Node(key, value);
while (map.size() >= this.capacity) {
Node removedNode = doubleList.removeHead();
// 这时候就用到了node中的key
map.remove(removedNode.key);
}
map.put(key, node);
doubleList.addToTail(node);
}
}
}
@Test
public void testFun() {
LRUCache lruCache = new LRUCache(1);
lruCache.put(2, 1);
System.out.println(lruCache.get(2));
lruCache.put(3, 2);
System.out.println(lruCache.get(2));
System.out.println(lruCache.get(3));
}
