# LRU 缓存
146.LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现
LRUCache类：
LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。函数
get和put必须以O(1)的平均时间复杂度运行。
一开始想到是使用双向链表，但是双向链表的查询是 O (n) 的，O (1) 的查询自然就是哈希表了
PUT操作 ：
添加元素时判断 key 是否存在（HashMap 查找）
存在
- 重新赋值
- 将节点从原有位置抽离
- 节点放到链表头部
不存在
判断容量已经满了 ？（用
count变量记录 cache 中元素数量）没满：新建一个节点
newNode插入链表头部满了：
- 将尾部节点删除
- 新建节点
newNode插入头部
HashMap 存放 < key,
newNode>
GET操作 ：
- 从 HashMap 取节点
- 为
null返回 - 1 - 不为
null- 将节点从原有位置抽离
- 节点放到链表头部
- 为
AC 之后考虑并发问题，LRU 本身就是操作系统的内存淘汰机制，需要考虑并发问题：如果 get 的同时
在多线程的情况下， get() 移动节点操作和 put() 整个方法加锁来保证节点的顺序正常。
import java.util.HashMap; | |
class LRUCache { | |
/** | |
* 容量 | |
*/ | |
private final int capacity; | |
/** | |
* 元素个数 | |
*/ | |
private int count; | |
/** | |
* head.next 指向的是最近最多使用的节点 | |
*/ | |
private final Node head; | |
/** | |
* tail.prev 指向的是最近最少使用的节点 | |
*/ | |
private final Node tail; | |
private final HashMap<Integer, Node> hash; | |
static class Node { | |
Node next, prev; | |
int key, val; | |
public Node() { | |
} | |
public Node(int key, int val, Node prev, Node next) { | |
this.next = next; | |
this.prev = prev; | |
this.key = key; | |
this.val = val; | |
} | |
public Node(int key, int val) { | |
this.key = key; | |
this.val = val; | |
} | |
} | |
public LRUCache(int capacity) { | |
this.capacity = capacity; | |
this.hash = new HashMap<>(); | |
head = new Node(); | |
tail = new Node(); | |
count = 0; | |
head.next = tail; | |
tail.prev = head; | |
} | |
public int get(int key) { | |
// 查找节点 | |
Node cur = hash.get(key); | |
if (cur != null) { | |
synchronized (this) { | |
unLinkedNode(cur); | |
moveToHead(cur); | |
} | |
return cur.val; | |
} | |
return -1; | |
} | |
public synchronized void put(int key, int value) { | |
Node tmp; | |
// 判断是否有此节点，有就放到头部，没有就新建放到头部 | |
if ((tmp = hash.get(key)) != null) { | |
tmp.val = value; | |
unLinkedNode(tmp); | |
} else { | |
count++; | |
if (capacity < count) { | |
hash.remove(tail.prev.key); | |
removeTail(); | |
} | |
tmp = new Node(key, value); | |
hash.put(key, tmp); | |
} | |
moveToHead(tmp); | |
} | |
/** | |
* 将节点放到链表头部 | |
*/ | |
private void moveToHead(Node cur) { | |
head.next.prev = cur; | |
cur.next = head.next; | |
head.next = cur; | |
cur.prev = head; | |
} | |
/** | |
* 将节点从原有链表拿出来 | |
*/ | |
private void unLinkedNode(Node cur) { | |
cur.prev.next = cur.next; | |
cur.next.prev = cur.prev; | |
} | |
/** | |
* 淘汰最近最少使用的节点（尾节点） | |
*/ | |
private void removeTail() { | |
unLinkedNode(tail.prev); | |
// 元素个数减少 | |
count--; | |
} | |
} | |
/** | |
* Your LRUCache object will be instantiated and called as such: | |
* LRUCache obj = new LRUCache(capacity); | |
* int param_1 = obj.get(key); | |
* obj.put(key,value); | |
*/ |
# 引申
LRU 全程 Least Recently Used，即最近最少使用的页面置换算法，是服务虚拟页式存储管理服务的，实现思想是读取的数据会更新到 LRU 列表最前端， 当容量满的时候会淘汰尾部数据，来达到一个最近最少使用的数据淘汰功能。
根据局部性原理（包括空间局部性和时间局部性，一条指令执行后在将来的一段时间内可能会再次执行（热点代码），一个数据被访问后可能会再次访问，或者这个数据相邻的数据很大概率会再次访问到）。
CSAPP 关于局部性的论述：
- 在一个具有良好时间局部性的程序中，被引用过的内存位置很可能在不远的将来再被多次引用。
- 在一个具有良好空间局部性的程序中，一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。
个人思考：局部性原理是无处不在的，LRU 就是基于局部性原理的一个体现。
