前言
LRU（Least Recently Used，最近最少使用），是一种缓存数据淘汰策略。由于缓存有容量上限，当缓存写满后，有新的数据要放入缓存，则需要按照一定的策略淘汰掉缓存中原有的数据，这个策略就叫做缓存淘汰策略。常见的缓存淘汰策略有：FIFO（First Input First Output）、LRU、LFU（Least Frequently Used）等。
LRU的思想认为，最近被访问过的数据，在将来被访问的几率最大。
LRU算法设计
LRU缓存要求
- 以正整数作为容量 capacity 初始化 LRU 缓存。
- 查找操作：如果关键字 key 存在于缓存中，则返回关键字的值，否则返回null 。
- 插入操作：如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
- 插入操作和查找操作的平均时间复杂度为O(1)。
LRU算法设计
- 由于LRU缓存有容量限制，在put操作的时候需要先查看缓存是否已满，因此在初始化缓存时需要指定capacity和size分别记录缓存的容量和已经存放元素个数。
- 为了保证查找操作的平均时间复杂度为O(1)，可以使用HashMap来存放。
- 如果仅使用HashMap，淘汰元素时，就没法保证O(1)的时间复杂度。
LRU算法实现——Java语言
主要成员变量和方法
- 首先定义一个Cache接口，在该接口中定义主要的方法。
csharp
体验AI代码助手
代码解读
复制代码
package com.shg.algorithm.lru;
/**
* @author: shg
* @create: 2022-05-09 5:53 下午
*/
public interface Cache<K, V> {
/**
* 获取缓存中的数据
*
* @param key
* @return
*/
V get(K key);
/**
* 向缓存中添加数据
*
* @param key
* @param value
*/
void put(K key, V value);
/**
* 返回缓存中存放元素个数
*
* @return
*/
int size();
/**
* 缓存是否为空
*
* @return
*/
boolean isEmpty();
/**
* 清空缓存
*/
void clear();
}
- 定义一个基于LRU算法的Cache接口的实现类LRUCache，在该类中实现具体方法，以及主要的成员变量。
- 由于LRUCache需要维护一个双端队列，因此定义一个Entry封装放入缓存中的数据，作为链表的节点
- 定义head和tail分别作为链表的头节点和尾节点，head是哑节点，不保存任何数据，其key和value始终为null
- 定义一个HashMap类型的cache，用于存放数据，其中key为数据的关键字，而value是链表的节点
- capacity和size分别表示缓存的容量和放入数据的数量
java
体验AI代码助手
代码解读
复制代码
package com.shg.algorithm.lru;
import java.util.HashMap;
/**
* @author: shg
* @create: 2022-05-09 5:57 下午
*/
public class LRUCache<K, V> implements Cache<K, V> {
/**
* 缓存容量
*/
private int capacity;
/**
* 缓存中已经存放元素数量
*/
private int size;
/**
* head，双向链表的头节点
* tail，双向链表的尾节点
*/
private Entry head, tail;
/**
* 用来存放关键字k和关键字所对应的节点entry
*/
private HashMap<K, Entry> cache;
/**
* 需要指定缓存容量的构造方法
* @param capacity
*/
public LRUCache(int capacity) {
this.capacity = capacity;
}
@Override
public V get(K key) {
return null;
}
@Override
public void put(K key, V value) {
}
@Override
public int size() {
return 0;
}
@Override
public boolean isEmpty() {
return false;
}
@Override
public void clear() {
}
/**
* 内部类，用于将放入缓存中的数据k、v封装城双向链表的节点
*
* @param <K>
* @param <V>
*/
class Entry<K, V> {
K key;
V value;
Entry<K, V> pre;
Entry<K, V> next;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
}
}
具体方法实现详解
- 构造方法
- 初始容量应为正整数，否则抛出非法的参数异常
- 本类中的哈希表采用懒初始化，因此在构造方法中并没有初始化哈希表
arduino
体验AI代码助手
代码解读
复制代码
/**
* 需要指定缓存容量的构造方法
* @param capacity
*/
public LRUCache(int capacity) {
if (capacity <= 0)
throw new IllegalArgumentException("capacity不能小于1，capacity：" + capacity);
this.capacity = capacity;
this.size = 0;
}
- get(K): V 操作
- 首先判断cache是否为null，如果cache为null，则缓存中没有数据，直接返回null
- 如果cache不为null，则根据key从cache中对应的entry
- 判断entry是否为null，如果为null，则关键字key对应的数据不存在，返回null
- 如果entry不为null，则判断该节点是否在队尾，如果不在队尾，则将该节点移到队尾
- 将entry节点的前驱节点的后继节点指向entry节点的后继节点
- 将entry节点的后继节点的前驱节点指向entry节点的前驱节点
- 将entry节点的前驱节点指向队尾
- 将队尾的后继节点执行entry
- 将entry节点的后继节点置空
- 将tail指向entry，完成将entry移到队尾操纵
- 最后返回数据
ini
体验AI代码助手
代码解读
复制代码
@Override
public V get(K key) {
// 如果cache为null，则缓存中没有数据，直接返回null
if (cache == null) return null;
// 否则，从cache中获取数据
Entry<K, V> entry = cache.get(key);
// 判断entry是否为空，如果为空，则关键字key对应的数据不存在，返回null
if (entry == null) return null;
// 否则判断该节点是否在队尾，如果不在队尾，则将该节点移到队尾
if (entry != tail) {
entry.pre.next = entry.next;
entry.next.pre = entry.pre;
entry.pre = tail;
tail.next = entry;
entry.next = null;
tail = entry;
}
// 返回entry中的value值
return entry.value;
}
- put(K, V): void
- 首先校验插入的数据是否为null，为null则直接抛出异常
- 判断cache是否初始化，如果没有初始化，则进行初始化
- 判断是否需要先进行淘汰：如果缓存已满且要插入的key不在缓存中，需要先进行淘汰
- 淘汰数据：
- 将队首元素移出队列：队首元素是head.next，而不是head，head是不保存数据的哑节点
- 从cache中删除数据
- 移出队首元素后，队列已存入的元素数量要减1
- 插入数据：这里还要考虑到数据是否已经存在于缓存中
- 如果不存在需要先根据key和value封装entry插入到队列队尾，并加入到cache中
- 如果存在，则需要更新value，并将对应的entry移动到队尾
ini
体验AI代码助手
代码解读
复制代码
@Override
public void put(K key, V value) {
// 校验数据，如果为null则抛出异常
if (key == null || value == null)
throw new IllegalArgumentException("key-value不能为null");
// 判断cache是否初始化，如果没有初始化，则进行初始化
if (cache == null)
initialCache();
// 判断是否需要先进行淘汰：如果缓存已满且要插入的key不在缓存中，需要先进行淘汰
if (size == capacity && !cache.containsKey(key)) {
// 淘汰数据
// 1. 将队首元素移出队列：队首元素是head.next，而不是head，head是不保存数据的哑节点
// 2. 从cache中删除数据
head = head.next;
if (head != null) {
cache.remove(head.key);
head.key = null;
head.value = null;
head.pre = null;
}
// 移出队首元素后，队列已存入的元素数量要减1
size--;
}
// 插入数据：这里还要考虑到数据是否已经存在于缓存中
// 如果不存在需要先根据key和value封装entry插入到队列中，并加入到cache中
// 如果存在，则需要更新value，并将对应的entry移动到队尾
for (Entry<K, V> entry = cache.get(key);; ) {
if (entry == null) {
// 封装entry，并加入到cache中
entry = new Entry<>(key, value);
cache.put(key, entry);
} else {
if (entry.pre == null) { // 新创建的entry，直接加入到队尾
tail.next = entry;
entry.pre = tail;
// tail = entry; // 这一步由于不管是新加入entry还是更新entry都有，因此可以提取出来
size++;
} else { // 更新entry
entry.value = value;
if (entry != tail) { // 如果entry不在队尾，则移到队尾
entry.pre.next = entry.next;
entry.next.pre = entry.pre;
entry.pre = tail;
tail.next = entry;
entry.next = null;
// tail = entry; // 这一步由于不管是新加入entry还是更新entry都有，因此可以提取出来
}
}
tail = entry;
return;
}
}
}
/**
* 初始化cache、head、tail
*/
private void initialCache() {
// 初始化cache，直接指定cache大小，防止以后扩容影响性能
cache = new HashMap<>(capacity);
// 初始化队列，head作为哑节点，不保存数据
head = new Entry(null, null);
tail = head;
}
- clear(): void
ini
体验AI代码助手
代码解读
复制代码
@Override
public void clear() {
// 清空cache
cache.clear();
// 清空队列
head = null;
tail = null;
// 缓存中数据的数量置为0
size = 0;
}
- size(): int
arduino
体验AI代码助手
代码解读
复制代码
@Override
public int size() {
return size;
}
- isEmpty(): boolean
typescript
体验AI代码助手
代码解读
复制代码
@Override
public boolean isEmpty() {
return size == 0;
}
完整代码
ini
体验AI代码助手
代码解读
复制代码
package com.shg.algorithm.lru;
import java.util.HashMap;
/**
* @author: shg
* @create: 2022-05-09 5:57 下午
*/
public class LRUCache<K, V> implements Cache<K, V> {
/**
* 缓存容量
*/
private int capacity;
/**
* 缓存中已经存放元素数量
*/
private int size;
/**
* head，双向链表的头节点
* tail，双向链表的尾节点
*/
private Entry head, tail;
/**
* 用来存放关键字k和关键字所对应的节点entry
*/
private HashMap<K, Entry> cache;
/**
* 需要指定缓存容量的构造方法
*
* @param capacity
*/
public LRUCache(int capacity) {
if (capacity <= 0)
throw new IllegalArgumentException("capacity不能小于1，capacity：" + capacity);
this.capacity = capacity;
this.size = 0;
}
@Override
public V get(K key) {
// 如果cache为null，则缓存中没有数据，直接返回null
if (cache == null) return null;
// 否则，从cache中获取数据
Entry<K, V> entry = cache.get(key);
// 判断entry是否为空，如果为空，则关键字key对应的数据不存在，返回null
if (entry == null) return null;
// 否则判断该节点是否在队尾，如果不在队尾，则将该节点移到队尾
if (entry != tail) {
entry.pre.next = entry.next;
entry.next.pre = entry.pre;
entry.pre = tail;
tail.next = entry;
entry.next = null;
tail = entry;
}
// 返回entry中的value值
return entry.value;
}
@Override
public void put(K key, V value) {
// 校验数据，如果为null则抛出异常
if (key == null || value == null)
throw new IllegalArgumentException("key-value不能为null");
// 判断cache是否初始化，如果没有初始化，则进行初始化
if (cache == null)
initialCache();
// 判断是否需要先进行淘汰：如果缓存已满且要插入的key不在缓存中，需要先进行淘汰
if (size == capacity && !cache.containsKey(key)) {
// 淘汰数据
// 1. 将队首元素移出队列：队首元素是head.next，而不是head，head是不保存数据的哑节点
// 2. 从cache中删除数据
head = head.next;
if (head != null) {
cache.remove(head.key);
head.key = null;
head.value = null;
head.pre = null;
}
// 移出队首元素后，队列已存入的元素数量要减1
size--;
}
// 插入数据：这里还要考虑到数据是否已经存在于缓存中
// 如果不存在需要先根据key和value封装entry插入到队列中，并加入到cache中
// 如果存在，则需要更新value，并将对应的entry移动到队尾
for (Entry<K, V> entry = cache.get(key);; ) {
if (entry == null) {
// 封装entry，并加入到cache中
entry = new Entry<>(key, value);
cache.put(key, entry);
} else {
if (entry.pre == null) { // 新创建的entry，直接加入到队尾
tail.next = entry;
entry.pre = tail;
// tail = entry; // 这一步由于不管是新加入entry还是更新entry都有，因此可以提取出来
size++;
} else { // 更新entry
entry.value = value;
if (entry != tail) { // 如果entry不在队尾，则移到队尾
entry.pre.next = entry.next;
entry.next.pre = entry.pre;
entry.pre = tail;
tail.next = entry;
entry.next = null;
// tail = entry; // 这一步由于不管是新加入entry还是更新entry都有，因此可以提取出来
}
}
tail = entry;
return;
}
}
}
/**
* 初始化cache、head、tail
*/
private void initialCache() {
// 初始化cache，直接指定cache大小，防止以后扩容影响性能
cache = new HashMap<>(capacity);
// 初始化队列，head作为哑节点，不保存数据
head = new Entry(null, null);
tail = head;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void clear() {
// 清空cache
cache.clear();
// 清空队列
head = null;
tail = null;
// 缓存中数据的数量置为0
size = 0;
}
/**
* 内部类，用于将放入缓存中的数据k、v封装城双向链表的节点
*
* @param <K>
* @param <V>
*/
class Entry<K, V> {
K key;
V value;
Entry<K, V> pre;
Entry<K, V> next;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
}
}
小结
主要特点
- 并没有使用JDK内置的双端队列，而是通过内部类Entry来维护一个双端队列
- 内部维护了一个不保存任何数据的哑节点即head，这便于插入和移出节点操作
转载来源：https://juejin.cn/post/7095728841582198815
