LRU 缓存算法
一、题目描述
运用你所掌握的数据结构，设计和实现一个 LRU（最近最少使用）缓存机制。它应该支持以下操作：
- 获取数据 get(key)：如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
- 写入数据 put(key, value) ：如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶：
你是否可以在 O(1) 时间复杂度内完成这两种操作？
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4二、题解
LRU 是 Least Recently Used 的缩写，这种算法认为最近使用的数据是热门数据，下一次很大概率将会再次被使用。而最近很少被使用的数据，很大概率下一次不再用到。当缓存容量满的时候，优先淘汰最近很少使用的数据。
实现 LRU 缓存的常用方法是使用有界队列。实现 LRU 的关键是将所有最近使用的数据放在队列的开头。在每次插入之前，我们检查队列是否已满。如果队列已满，我们将删除其最后一个元素，并将新节点插入队列的开头。如果队列未满，我们只需将数据添加到队列的开头。
为了方便理解，我们借助前面的示例来演示一下上述的处理流程：
当我们想要删除节点或更新节点时，我们需要快速找到该节点在队列中的位置。因此，可以使用 HashMap 支持快速查找操作。在这种情况下，get 操作的时间复杂度为 O(1)。
由于我们还需要有效地删除队列中间的节点，因此需要一个双向链表。在两种情况下，我们需要删除队列中间的节点：
- 客户端指定需要删除一个节点。
- 节点已更新，需要将其删除并插入队列的开头。
通过使用双向链表，一旦我们通过 HashMap 定位了要删除的节点的位置，就可以在 O(1) 时间从队列中删除该节点。
当我们需要更新键的缓存时，我们首先使用 HashMap 定位相应的节点，更新值，然后从队列中删除该节点，并将该节点放置在 Doubly Linked List 的开头。
什么是缓存
这里说的缓存是一种广义的概念，在计算机存储层次结构中，低一层的存储器都可以看做是高一层的缓存。比如Cache是内存的缓存，内存是硬盘的缓存，硬盘是网络的缓存等等。
缓存可以有效地解决存储器性能与容量的这对矛盾，但绝非看上去那么简单。如果缓存算法设计不当，非但不能提高访问速度，反而会使系统变得更慢。
从本质上来说，缓存之所以有效是因为程序和数据的局部性（locality）。程序会按固定的顺序执行，数据会存放在连续的内存空间并反复读写。这些特点使得我们可以缓存那些经常用到的数据，从而提高读写速度。
缓存的大小是固定的，它应该只保存最常被访问的那些数据。然而未来不可预知，我们只能从过去的访问序列做预测，于是就有了各种各样的缓存替换策略。本文介绍一种简单的缓存策略，称为最近最少使用（LRU，Least Recently Used）算法。
LRU
LRU（Least Recently Used）是一种常见的页面置换算法，在计算中，所有的文件操作都要放在内存中进行，然而计算机内存大小是固定的，所以我们不可能把所有的文件都加载到内存，因此我们需要制定一种策略对加入到内存中的文件进项选择。
常见的页面置换算法有如下几种：
- LRU 最近最久未使用
- FIFO 先进先出置换算法 类似队列
- OPT 最佳置换算法 （理想中存在的）
- NRU Clock置换算法
- LFU 最少使用置换算法
- PBA 页面缓冲算法
LRU原理
一个简单的例子
LRU的设计原理就是，当数据在最近一段时间经常被访问，那么它在以后也会经常被访问。这就意味着，如果经常访问的数据，我们需要然其能够快速命中，而不常访问的数据，我们在容量超出限制内，要将其淘汰。
当我们的数据按照如下顺序进行访问时，LRU的工作原理如下：
每次访问的数据都会放在栈顶，当访问的数据不在内存中，且栈内数据存储满了，我们就要选择移除栈底的元素，因为在栈底部的数据访问的频率是比较低的。所以要将其淘汰。
题目描述
设计并实现最近最少使用（LRU）缓存的数据结构。它应该支持以下操作：get 和 put。
get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，
LRUCache cache = new LRUCache( 2 /* capacity (缓存容量) */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 去除 key 2
cache.get(2); // 返回 -1 (未找到key 2)
cache.get(3); // 返回 3
cache.put(4, 4); // 去除 key 1
cache.get(1); // 返回 -1 (未找到 key 1)
cache.get(3); // 返回 3
cache.get(4); // 返回 4单链表来解决
当我们进行 put 操作的时候，会出现以下几种情况：
1、如果要 put(key,value) 已经存在于链表之中了（根据key来判断），那么我们需要把链表中旧的数据删除，然后把新的数据插入到链表的头部。、
2、如果要 put(key,value) 的数据没有存在于链表之后，我们我们需要判断下缓存区是否已满，如果满的话，则把链表尾部的节点删除，之后把新的数据插入到链表头部。如果没有满的话，直接把数据插入链表头部即可。
对于 get 操作，则会出现以下情况
1、如果要 get(key) 的数据存在于链表中，则把 value 返回，并且把该节点删除，删除之后把它插入到链表的头部。
2、如果要 get(key) 的数据不存在于链表之后，则直接返回 -1 即可。
时间、空间复杂度分析
对于这种方法，put 和 get 都需要遍历链表查找数据是否存在，所以时间复杂度为 O(n)。空间复杂度为 O(1)。哈希表
我们可以用一个额外哈希表（例如HashMap）来存放 key-value，这样的话，我们的 get 操作就可以在 O(1) 的时间内寻找到目标节点，并且把 value 返回了。
然而，大家想一下，用了哈希表之后，get 操作真的能够在 O(1) 时间内完成吗？
用了哈希表之后，虽然我们能够在 O(1) 时间内找到目标元素，可是，我们还需要删除该元素，并且把该元素插入到链表头部啊，删除一个元素，我们是需要定位到这个元素的前驱的，然而定位到这个元素的前驱，是需要 O(n) 时间复杂度的。
最后的结果是，用了哈希表时候，最坏时间复杂度还是 O(1)，而空间复杂度也变为了 O(n)。
http://www.manongjc.com/article/37262.html 泛型
https://blog.csdn.net/weixin_46625895/article/details/105387746 非泛型
package com.logi.algorithm;
public class LRUWithSinglyLinkedList {
LRUNode head;
int capacity;
int size;
public LRUWithSinglyLinkedList(int capacity) {
this.capacity = capacity;
this.size = 0;
this.head = new LRUNode();
}
public static void main(String[] args) {
LRUWithSinglyLinkedList lru = new LRUWithSinglyLinkedList(2);
lru.put(1, 1);
System.out.println(lru + ", after put(1,1)");
lru.put(2, 2);
System.out.println(lru + ", after put(2,2)");
lru.get(1);
System.out.println(lru + ", after get(1)");
lru.put(3, 3);
System.out.println(lru + ", after put(3,3)");
lru.get(2);
System.out.println(lru + ", after get(2)");
lru.put(4, 4);
System.out.println(lru + ", after put(4,4)");
lru.get(1);
System.out.println(lru + ", after get(1)");
lru.get(3);
System.out.println(lru + ", after get(3)");
lru.get(4);
System.out.println(lru + ", after get(4)");
}
@Override
public String toString() {
LRUNode current = this.head.next;
StringBuilder list = new StringBuilder();
while (current != null) {
list.append(current.value);
if (current.next != null) {
list.append("->");
}
current = current.next;
}
return list.toString();
}
/**
* 根据 key 查找 value，如果已存在将其移至表头并返回，否则返回 -1
*
* @param key
* @return
*/
public int get(int key) {
LRUNode prev = this.getPrev(key);
if (prev != null) {
LRUNode current = prev.next;
this.delete(prev);
this.insert(current);
return current.value;
} else {
return -1;
}
}
/**
* 加载页面，如果缓存已满，删掉表尾
*
* @param key
* @param value
*/
public void put(int key, int value) {
LRUNode current = new LRUNode(key, value);
LRUNode prev = this.getPrev(key);
if (prev == null) {
if (this.size == this.capacity) {
this.delete(this.getTailPrev());
}
this.insert(current);
}
}
/**
* 获取 tail 前驱
*
* @return
*/
public LRUNode getTailPrev() {
LRUNode current = this.head;
if (current.next == null) {
return null;
}
while (current.next.next != null) {
current = current.next;
}
return current;
}
/**
* 根据 key 获得前驱
*
* @param key
* @return
*/
public LRUNode getPrev(int key) {
LRUNode prev = this.head;
while (prev != null) {
if (prev.next != null && prev.next.key == key) {
break;
}
prev = prev.next;
}
return prev;
}
/**
* 根据前驱删除
*
* @param prev
*/
public void delete(LRUNode prev) {
prev.next = prev.next.next;
this.size--;
}
/**
* 插入到表头
*
* @param current
*/
public void insert(LRUNode current) {
current.next = this.head.next;
this.head.next = current;
this.size++;
}
}
class LRUNode {
LRUNode next;
int key;
int value;
public LRUNode() {
this.key = this.value = 0;
this.next = null;
}
public LRUNode(int key, int value) {
this.key = key;
this.value = value;
this.next = null;
}
}双向链表+哈希表
这可以通过HashMap+双向链表实现。HashMap保证通过key访问数据的时间为O(1)，双向链表则按照访问时间的顺序依次穿过每个数据。之所以选择双向链表而不是单链表，是为了可以从中间任意结点修改链表结构，而不必从头结点开始遍历。
代码实现
大致思路:
1 构建双向链表节点ListNode，应包含key,value,prev,next这几个基本属性
2 对于Cache对象来说，我们需要规定缓存的容量，所以在初始化时，设置容量大小，然后实例化双向链表的head,tail，并让head.next->tail tail.prev->head，这样我们的双向链表构建完成
3 对于get操作,我们首先查阅hashmap，如果存在的话，直接将Node从当前位置移除，然后插入到链表的首部，在链表中实现删除直接让node的前驱节点指向后继节点，很方便.如果不存在，那么直接返回Null
4 对于put操作，比较麻烦。
采用这两种数据结构的组合，我们的 get 操作就可以在 O(1) 时间复杂度内完成了。由于 put 操作我们要删除的节点一般是尾部节点，所以我们可以用一个变量 tai 时刻记录尾部节点的位置，这样的话，我们的 put 操作也可以在 O(1) 时间内完成了。
双链表 + 哈希表，采用这两种数据结构的组合，我们的 get 操作就可以在 O(1) 时间复杂度内完成了。由于 put 操作我们要删除的节点一般是尾部节点，所以我们可以用一个变量 tai 时刻记录尾部节点的位置，这样的话，我们的 put 操作也可以在 O(1) 时间内完成了。
//定义链表节点
class Node{
int key;
int value;
Node pre;
Node next;
public Node(int key,int value){
this.key = key;
this.value = value;
}
}
public class LRUCache{
Map<Integer,Node> cacheMap = new HashMap<>();
//定义哈希表
Node head = null;
//定义头节点
Node tail = null;
//定义尾节点
int nodeLength =0;
//容量
//put操作
public int get(int key){
if(cacheMap.containsKey(key)){
//如果存在的话
Node node =cacheMap.get(key);
removeNode(node);
//进行移除
setHead(node);
//把节点放到首部
return node.value;
//返回节点
}
return -1;
//不存在返回-1；
}
//移除链表中的节点
public void removeNode(Node node){
if(node.pre != null){
//如果前节点不为空
node.pre.next = node.next;
}else{
//前节点为空
head = node.next;
}
if(node.next != null){
//后节点不为空
node.next.pre = node.pre;
}else{
后节点为空
tail = node.pre;
}
}
//把节点放到链表的头部
public void setHead(Node node){
node.next = head;
node.pre = null;
if(head != null){
//如果头结点不为空
head.pre = node;
}else{
head = node;
//头结点为空
}
if(tail == null){
//如果尾部节点为空
tail = head;
}
}
//put操作
public void put(int key,int value){
if(cacheMap.containsKey(key)){
//如果包含key的话
Node oldNode = cacheMap.get(key);
//取出旧的值
oldNode.value = value;
//替换旧的值
remove(oldNode);
//移除链表中的旧的值
setHead(oldNode);
//把旧的值放到首部
}else{
//不包含的情况
Node newNode = new Node(key,value);
//考虑容量是否足够
if(cacheMap.size() >= nodeLength){
//容量不够的话
cacheMap.remove(tail.key);
//哈希表去掉尾部值
remove(tail);
//删除链表尾部
setHead(newNode);
//把新的链表放到头部位置
}else{
setHead(newNode);
容量够的话
}
cacheMap.put(key,newNode);
//放入到hashmap中
}
}
}
import java.util.HashMap;
import java.util.Map;
/**
* @Auther: liuhaidong
* Data: 2020/3/24 0024、22:41
* Description:
* @version: 1.0
*/
class Node {
int key;
int value;
Node pre;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public class LRUCache {
public static void main(String[] args) {
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println("cache.get(1): " + cache.get(1));
cache.put(3, 3);
System.out.println("cache.get(2): " + cache.get(2));
System.out.println("cache.get(3): " + cache.get(3));
}
int capacity;
Map<Integer, Node> map = new HashMap<>();
Node head = null;
Node tail = null;
public LRUCache(int capacity) {
this.capacity = capacity;
}
/**
* 根据指定key查找其对应的值
*
* @param key
* @return
*/
public int get(int key) {
if (map.containsKey(key)) {
Node node = map.get(key);
remove(node);
setHead(node);
return node.value;
}
return -1;
}
/**
* 移除指定n节点
*
* @param n
*/
public void remove(Node n) {
if (n.pre != null) { // 非头节点
n.pre.next = n.next;
} else { // 头节点
head = n.next;
}
if (n.next != null) { // 非尾节点
n.next.pre = n.pre;
} else { // 尾节点
tail = n.pre;
}
}
/**
* 设置双向链表的头节点
*
* @param n
*/
public void setHead(Node n) {
n.next = head;
n.pre = null;
if (head != null)
head.pre = n;
head = n;
if (tail == null)
tail = head;
}
/**
* 把指定key和value添加到缓存中
*
* @param key
* @param value
*/
public void put(int key, int value) {
// key对应的节点已存在，先更新节点值，然后将其删除并插入到链表头
if (map.containsKey(key)) {
Node old = map.get(key);
old.value = value;
remove(old);
setHead(old);
} else {
// 基于key和value创建新的节点
Node created = new Node(key, value);
// 若链表已满，则先移除链表尾元素，然后再把新元素添加到链表头
if (map.size() >= capacity) {
map.remove(tail.key);
remove(tail);
setHead(created);
} else {
setHead(created);
}
map.put(key, created);
}
}
}
https://cloud.tencent.com/developer/article/1583695
其它代码
值得一提的是，Java API中其实已经有数据类型提供了我们需要的功能，就是LinkedHashMap这个类。该类内部也是采用HashMap+双向链表实现的。使用这个类实现LRU就简练多了。
/**
*
* 一个更简单实用的LRUCache方案，使用LinkedHashMap即可实现。
* LinkedHashMap提供了按照访问顺序排序的方案，内部也是使用HashMap+双向链表。
* 只需要重写removeEldestEntry方法，当该方法返回true时，LinkedHashMap会删除最旧的结点。
*
* @author wjg
*
*/
public class LRUCacheSimple {
/**
* @param args
*/
public static void main(String[] args) {
LRUCacheSimple cache = new LRUCacheSimple(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1));
cache.put(3, 3);
System.out.println(cache.get(2));
cache.put(4, 4);
System.out.println(cache.get(1));
System.out.println(cache.get(3));
System.out.println(cache.get(4));
}
private LinkedHashMap<Integer, Integer> map;
private final int capacity;
public LRUCacheSimple(int capacity) {
this.capacity = capacity;
map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true){
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > capacity;
}
};
}
public int get(int key) {
return map.getOrDefault(key, -1);
}
public void put(int key, int value) {
map.put(key, value);
}
}只需要覆写LinkedHashMap的removeEldestEntry方法，在缓存已满的情况下返回true，内部就会自动删除最老的元素。
京公网安备 11010502036488号