LRU最近最少使用算法
一、LRU算法
1.简介
LRU（Least Recently Used，最近最少使用）算法是一种常用的缓存淘汰策略，当缓存达到其容量上限时，它会移除那些最久没有被访问的数据项。这种策略基于这样一个假设：如果一个数据项在近期没有被访问过，那么在未来一段时间内也不太可能被访问。
2.LRU算法的核心思想
LRU算法的核心在于追踪每个数据项的访问历史，并优先保留最近被访问过的数据项。具体来说，每当有新的数据需要存储而缓存已满时，LRU算法会选择移除那个最长时间未被访问的数据项。
二、算法题目
1.LeetCode题目
146. LRU 缓存
2.实现
class LRUCache extends LinkedHashMap<Integer, Integer> {private int capacity;public LRUCache(int capacity) {super(capacity, 0.75F, true);this.capacity = capacity;}public int get(int key) {return getOrDefault(key, -1);}public void put(int key, int value) {super.put(key, value);}@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {return size() > capacity;}}/*** 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);*/
三、项目中实现
- 定义Cache接口
package com.zzc.design.cache;import java.util.concurrent.Callable;public interface Cache<K, V> {/*** 添加值到缓存中，如果key已经存在，值将会被覆盖* @param key* @param val*/void put(K key, V val);/*** 根据key从缓存中获取value* @param key* @return*/V get(K key);/*** “加载-通过”模式（load-through pattern）* 从缓存中获取值，如果该值不存在，则通过给定的函数处理并将其结果更新到缓存中。* @param key* @param call* @return* @throws Exception*/V get(K key, Callable<? extends V> call) throws Exception;/*** 通过key移除缓存* @param key* @return*/V remove(K key);/*** 清除整个缓存*/void clear();/*** 缓存数量大小* @return*/int getCapacity();}- 实现具体存储key-value数据的接口
package com.zzc.design.cache;import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.Callable;public class SimpleCache<K, V> implements Cache<K, V> {private final Map<K, V> cache;public SimpleCache(int size) {cache = new HashMap<>(size);}@Overridepublic void put(K key, V val) {cache.put(key, val);}@Overridepublic V get(K key) {return cache.get(key);}@Overridepublic V get(K key, Callable<? extends V> call) throws Exception {if (cache.containsKey(key)) {return cache.get(key);} else {V v2 = call.call();cache.put(key, v2);return v2;}}@Overridepublic V remove(K key) {return cache.remove(key);}@Overridepublic void clear() {cache.clear();}@Overridepublic int getCapacity() {return cache.size();}}- 拓展LRU缓存类型
package com.zzc.design.cache.lru;import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.Callable;public class LruCache<K, V> implements Cache<K, V> {/*** 存储键值对数据*/private final Cache<K, V> delegate;/*** 跟踪键的访问顺序，从而实现 LRU 策略*/private Map<K, V> visits;/*** 记录最近要被移除的最老键*/private K eldestKey;public LruCache(Cache<K, V> delegate, int capacity) {this.delegate = delegate;setCapacity(capacity);}public void setCapacity(final int capacity) {visits = new LinkedHashMap<K, V>(capacity, .75F, true) {@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {boolean tooBig = size() > capacity;if (tooBig) {eldestKey = eldest.getKey();}return tooBig;}};}@Overridepublic void put(K key, V val) {delegate.put(key, val);cycleKeyList(key);}@Overridepublic V get(K key) {visits.get(key);return delegate.get(key);}@Overridepublic V get(K key, Callable<? extends V> call) throws Exception {return delegate.get(key, call);}@Overridepublic V remove(K key) {return delegate.remove(key);}@Overridepublic void clear() {delegate.clear();visits.clear();}@Overridepublic int getCapacity() {return delegate.getCapacity();}private void cycleKeyList(K key) {visits.put(key, null);if (eldestKey != null) {delegate.remove(eldestKey);eldestKey = null;}}
}- Demo示例
package com.zzc.design.cache.lru;import com.zzc.design.cache.Cache;
import com.zzc.design.cache.SimpleCache;public class Demo {private static final int initCapacity = 1;private static final int maxCapacity = 3;public static void main(String[] args) {Cache<String, String> cache = new LruCache<>(new SimpleCache<>(initCapacity), maxCapacity);cache.put("key1", "value1");cache.put("key2", "value2");cache.put("key3", "value3");System.out.println(cache.get("key1"));//访问key1System.out.println(cache.get("key2"));//访问key2System.out.println(cache.get("key3"));//访问key3System.out.println(cache.get("key1"));//访问key1System.out.println(cache.get("key2"));//访问key2cache.put("key4", "value4");//新增key4System.out.println(cache.get("key3"));//key3的访问次数最少，在添加key4的时候被删除掉了}}
/** 结果:* value1* value2* value3* value1* value2* null*/
