2023-05-28 22:04:11
浏览数 (1)
- 什么是LRU算法
- Least Recently Used 淘汰算法以时间作为参考，淘汰最长时间未被使用的数据
- 如果数据最近被访问过，那么将来被访问的几率也更高；会淘汰最长时间没有被使用的元素（都没人要你了，不淘汰你淘汰谁）
- 基本原理是：在缓存满时，将最近最久未使用的数据淘汰出缓存，以便给新的数据留出空间。
- 实现方式可以用：数组、链表等方式
- 新插入的数据放在头部，最近访问过的也移到头部，空间满时将尾部元素删除
在这里插入图片描述代码语言：java
复制public class LRUCache<K,V> {
//定义存储key的顺序表
private LinkedList<K> cacheKey;
//定规存储数据的map 存储key，value
private HashMap<K,V> cacheValues;
//定义缓存的容量
private int capacity;
//构造方法初始化缓存
public LRUCache(int capacity) {
this.cacheKey = new LinkedList<>();
this.capacity = capacity;
this.cacheValues = new HashMap<>();
}
//向缓存中put元素
public void put(K key, V value) {
//先添加元素，无论有没有这个key，直接进行put
cacheValues.put(key, value);
cacheKey.add(0, key);
//判断长度是否超出最大容量，超出进行淘汰
if (cacheKey.size() > capacity) {
//如果容量已满，则删除最后一个key
K lastKey = cacheKey.get(cacheKey.size() - 1);
cacheKey.remove(lastKey);
cacheValues.remove(lastKey);
}
}
//获取指定key的元素的value，并且将这个key放置在队头的位置
public V get(K key) {
V data = null;
if (cacheKey.contains(key)) {
data = cacheValues.get(key);
cacheKey.remove(key);
cacheKey.add(0,key);
}
return data;
}
//
public void showList(){
System.out.println(cacheKey.toString());
}
public static void main(String[] args) {
LRUCache<String,String> cache = new LRUCache<>(5);
cache.put("A", "任务A");
cache.put("B", "任务B");
cache.put("C", "任务C");
cache.put("D", "任务D");
cache.put("E", "任务E");
cache.showList();
System.out.println("G=" cache.get("G"));
System.out.println("C=" cache.get("C"));
cache.showList();
cache.put("F", "任务F");
cache.showList();
}
}
在这里插入图片描述
