- LRU：Least Recently Used 最近最少使用
- 题目要求：
设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。
它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
思路1：
- KV操作一般想到的就是Map。
- LRU应该有排序功能，最热数据放最左，冷数据经过更迭就会滞后，map满了每次剔除最后的数据即可。HashMap是无序的，需要加入顺序，第一个想到的肯定是LinkedHashMap。
- 因为LinkedHashMap.put顺序是结尾插入，删除也需要从头结点遍历，所以正好修改思路以头结点定为最冷数据、结尾定为最热数据。
- put：分三种情况
- map里存在key，但还需要修改为最热数据，所以需要先remove后put即可。
- map里不存在key，并且容量不满，直接put即可。
- map里不存在key，并且容量满，删除最冷数据，put即可。
- get：
- get就是不存在key就返回-1，存在就先remove后put变为最热数据即可。
- 调试后代码：
class LRUCache {
private Map<Integer, Integer> map;
private int capacity;
public LRUCache(int capacity) {
map = new LinkedHashMap<>(capacity);
this.capacity = capacity;
}
public int get(int key) {
if(!map.containsKey(key)) {
return -1;
}
int value = map.get(key);
map.remove(key);
map.put(key, value);
return value;
}
public void put(int key, int value) {
if(map.containsKey(key)){
map.remove(key);
}else if(map.size() == capacity){
Integer removeKey = map.entrySet().iterator().next().getKey();
map.remove(removeKey);
}
map.put(key, value);
}
}
执行用时: 36 ms
内存消耗: 46.6 MB
思路2（看官方答案后）：
- 官方说不能使用自带的LinkedHashMap，只能用基础数据结构。
- 思路相同，不过只能用HashMap和List实现了，效率没有优化，直接贴代码。
public class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {}
public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
}
private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
private int size;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
// 使用伪头部和伪尾部节点
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 如果 key 存在，先通过哈希表定位，再移到头部
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
// 如果 key 不存在，创建一个新的节点
DLinkedNode newNode = new DLinkedNode(key, value);
// 添加进哈希表
cache.put(key, newNode);
// 添加至双向链表的头部
addToHead(newNode);
++size;
if (size > capacity) {
// 如果超出容量，删除双向链表的尾部节点
DLinkedNode tail = removeTail();
// 删除哈希表中对应的项
cache.remove(tail.key);
--size;
}
}
else {
// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
node.value = value;
moveToHead(node);
}
}
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}
