3种堆内缓存算法 _算法

要说计算机系统里，什么技术把 tradeoff 体现的淋漓尽致，那肯定是缓存无疑。为了协调高速部件和低速部件的速度差异，加入一个中间缓存层，是解决这种冲突最有效的方案。
其中，JVM堆内缓存是缓存体系中重要的一环，最常用的有 FIFO / LRU / LFU 三种算法。

FIFO 是简单的队列，先进先出。
LRU 是最近最少使用，优先移除最久未使用的数据。是时间维度。
LFU 是最近最不常用，优先移除访问次数最少的数据。是统计维度。

由于过期也是缓存的一个重要特点。所有在设计这三种缓存算法时，需要额外的存储空间去存储这个过期时间。
以下将讨论这三种缓存算法的操作和设计要点，但暂未考虑高并发环境。
FIFO先进先出，如果缓存容量满，则优先移出最早加入缓存的数据；其内部可以使用队列实现。

文章插图

操作

Object get(key)：获取保存的数据，如果数据不存在或者已经过期，则返回null 。
void put(key,value,expireTime)：加入缓存。无论此key是否已存在，均作为新key处理（移除旧key）；如果空间不足，则移除已过期的key，如果没有，则移除最早加入缓存的key 。过期时间未指定，则表示永不自动过期。
注意，我们允许key是有过期时间的，这一点与普通的FIFO有所区别，所以在设计此题时需要注意。（也是面试考察点，偏设计而非算法）

普通的FIFO或许大家都能很简单的写出，增加了过期时间的考虑之后，在设计时需要多考虑。如下示例，为暂未考虑并发环境的FIFO设计。
设计思路1）用普通的hashMap保存缓存数据。
2）需要额外的map用来保存key的过期特性，例子中使用了TreeMap，将“剩余存活时间”作为key，利用TreeMap的排序特性。

public class FIFOCache {//按照访问时间排序,保存所有key-valueprivate final Map<String,Value> CACHE = new LinkedHashMap<>();//过期数据，只保存有过期时间的key//暂不考虑并发，我们认为同一个时间内没有重复的key，如果改造的话，可以将value换成setprivate final TreeMap<Long, String> EXPIRED = new TreeMap<>();private final int capacity;public FIFOCache(int capacity) {this.capacity = capacity;}public Object get(String key) {//Value value = https://www.isolves.com/it/cxkf/sf/2020-05-12/CACHE.get(key);if (value == null) {return null;}//如果不包含过期时间long expired = value.expired;long now = System.nanoTime();//已过期if (expired > 0 && expired <= now) {CACHE.remove(key);EXPIRED.remove(expired);return null;}return value.value;}public void put(String key,Object value) {put(key,value,-1);}public void put(String key,Object value,int seconds) {//如果容量不足，移除过期数据if (capacity < CACHE.size()) {long now = System.nanoTime();//有过期的,全部移除Iterator iterator = EXPIRED.keySet().iterator();while (iterator.hasNext()) {long _key = iterator.next();//如果已过期，或者容量仍然溢出，则删除if (_key > now) {break;}//一次移除所有过期keyString _value = EXPIRED.get(_key);CACHE.remove(_value);iterator.remove();}}//如果仍然容量不足，则移除最早访问的数据if (capacity < CACHE.size()) {Iterator iterator = CACHE.keySet().iterator();while (iterator.hasNext() && capacity < CACHE.size()) {String _key = iterator.next();Value _value = CACHE.get(_key);long expired = _value.expired;if (expired > 0) {EXPIRED.remove(expired);}iterator.remove();}}//如果此key已存在,移除旧数据Value current = CACHE.remove(key);if (current != null && current.expired > 0) {EXPIRED.remove(current.expired);}//如果指定了过期时间if(seconds > 0) {long expireTime = expiredTime(seconds);EXPIRED.put(expireTime,key);CACHE.put(key,new Value(expireTime,value));} else {CACHE.put(key,new Value(-1,value));}}private long expiredTime(int expired) {return System.nanoTime() + TimeUnit.SECONDS.toNanos(expired);}public void remove(String key) {Value value = CACHE.remove(key);if(value == null) {return;}long expired = value.expired;if (expired > 0) {EXPIRED.remove(expired);}}class Value {long expired; //过期时间,纳秒Object value;Value(long expired,Object value) {this.expired = expired;this.value = value;}}}

LRUleast recently used，最近最少使用，是目前最常用的缓存算法和设计方案之一，其移除策略为“当缓存（页）满时，优先移除最近最久未使用的数据”，优点是易于设计和使用，适用场景广泛。算法可以参考leetcode 146 （LRU Cache）。
操作