前言
源码：weloe/Java-Distributed-Cache (github.com
Java-Distributed-Cache/src/test/java/com/weloe/cache/outstrategy at master · weloe/Java-Distributed-Cache (github.com
什么是缓存？将之前请求的数据暂存，遇到同样的请求/状况直接返回，这就是缓存。
那么缓存怎么存？简单的缓存为键值对，可以用Map存储。这就完了吗？如果我们一直往Map中存储数据，占用的内存会越来越大，这时候怎么办？
要使用缓存，就必然会面临到缓存使用空间达到上限的问题，这个时候就需要从已有的缓存数据中淘汰一部分去维持缓存的可用性。
LRU
https://leetcode.cn/problems/lru-cache/
原理：为最近被访问的数据进行缓存，淘汰不常被访问的数据。
举一个我们最常见的例子，手机可用把软件放到后台运行，比如我们先后打开了日历，设置，闹钟。后台的顺序是 日历->设置->闹钟，如果这台手机只能打开三个应用，再打开 应用商城，后台的顺序会变成 应用商城->日历->设置。
缓存一般以key,value形式存储，因此选择map存储，而存储顺序的数据结构由于要不断改动节点顺序，选择双向链表
public class LRUCache<K, V> implements CacheStrategy<K, V> {
private Map<K, V> map;
private int capacity;
private Deque<K> queue;
private Callback callback;
public LRUCache(int capacity {
this.capacity = capacity;
this.map = new HashMap(;
this.queue = new LinkedList(;
}
}
put(key,value
如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity，则应该 逐出 最久未使用的关键字。
public void put(int key, int value {
if (map.containsKey(key {
queue.remove(key;
}
queue.addFirst(key;
map.put(key, value;
// 缓存达到上限
if (queue.size( > capacity {
// 移除
K last = queue.removeLast(;
V removeValue = map.remove(last;
// 回调
if (callback != null {
callback.callback(last, removeValue;
}
}
return value;
}
get(key
如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
public V get(K key {
// 如果已经缓存过该数据
if (map.containsKey(key {
queue.remove(key;
queue.addFirst(key;
return map.get(key;
}
return null;
}
弊端，容易出现缓存污染问题
(k2,v2,(k4,v4,(k1,v1,(k3,v3
LRU-K
LRU-K算法有两个队列，一个是缓存队列，一个是数据访问历史队列。当访问一个数据时，首先先在访问历史队列中累加访问次数，当历史访问记录超过K次后，才将数据缓存至缓存队列，从而避免缓存队列被污染。同时访问历史队列中的数据可以按照LRU的规则进行淘汰。具体如下：
public class LRUKCache<K, V> extends LRUCache<K, V> {
// 进入缓存队列的评判标准
private int putStandard;
// 访问数据历史记录
private LRUCache<Object, Integer> historyList;
public LRUKCache(int cacheSize, int historyCapacity, int putStandard {
super(cacheSize;
this.putStandard = putStandard;
this.historyList = new LRUCache(historyCapacity;
}
@Override
public V get(K key {
// 记录数据访问次数
Integer historyCount = historyList.get(key;
historyCount = historyCount == null ? 0 : historyCount;
historyList.put(key, ++historyCount;
return super.get(key;
}
@Override
public V put(K key, V value {
if (value == null {
return null;
}
// 如果已经在缓存里则直接返回
if (super.get(key != null {
return super.put(key, value;
}
// 如果数据历史访问次数达到上限，则加入缓存
Integer historyCount = historyList.get(key;
historyCount = (historyCount == null ? 0 : historyCount;
if (removeCache(historyCount {
// 移除历史访问记录，加入缓存
historyList.remove(key;
return super.put(key, value;
}
return value;
}
private boolean removeCache(Integer historyCount {
return historyCount >= putStandard;
}
public void setPutStandard(int putStandard {
this.putStandard = putStandard;
}
@Override
public void setCallback(Callback<K, V> callback {
super.setCallback(callback;
}
public void setHistoryListCallback(Callback<K, V> callback {
historyList.setCallback((Callback<Object, Integer> callback;
}
}
LRU-K能降低缓存污染发生的概率，但是需要额外记录对象访问次数，内存消耗较大。
测试
class LRUCacheTest {
@Test
void lru({
CacheStrategy<Integer, Integer> lruCache = new LRUCache<>(5;
lruCache.setCallback((integer, integer2 -> System.out.println("淘汰"+integer+"="+integer2;
lruCache.put(1,1;
lruCache.put(2,2;
lruCache.put(3,3;
lruCache.put(4,4;
lruCache.put(5,5;
lruCache.put(6,6;
List list = lruCache.list(;
System.out.println(list;
}
}
淘汰1=1
[2=2, 3=3, 4=4, 5=5, 6=6]
class LRUKCacheTest {
@Test
void lrukCacheTest( {
LRUKCache<Integer, Integer> lrukCache = new LRUKCache<>(2,3,1;
lrukCache.setHistoryListCallback((integer, integer2 -> System.out.println("记录队列淘汰"+integer+"="+integer2;
lrukCache.setCallback((integer, integer2 -> System.out.println("缓存淘汰"+integer+"="+integer2;
lrukCache.get(1;
lrukCache.get(1;
lrukCache.get(1;
lrukCache.get(2;
lrukCache.get(2;
lrukCache.get(2;
lrukCache.get(3;
lrukCache.get(3;
lrukCache.get(3;
lrukCache.get(4;
lrukCache.get(4;
lrukCache.get(4;
lrukCache.put(1,2;
lrukCache.put(2,2;
lrukCache.put(3,2;
lrukCache.put(4,2;
List list = lrukCache.list(;
System.out.println(list;
}
}
记录队列淘汰1=3
缓存淘汰2=2
[3=2, 4=2]