3种堆内缓存算法( 二 ) _算法

这里的设计关键是过期时间特性，这与常规的LRU有所不同。

设计思路

LRU的基础算法，需要了解；每次put、get时需要更新key对应的访问时间，我们需要一个数据结构能够保存key最近的访问时间且能够排序。
既然包含过期时间特性，那么带有过期时间的key需要额外的数据结构保存。
暂时不考虑并发操作；尽量兼顾空间复杂度和时间复杂度。
此题仍然偏向于设计题，而非纯粹的算法题。

此题代码与FIFO基本相同，唯一不同点为get()方法，对于LRU而言，get方法需要重设访问时间（即调整所在cache中顺序）

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;}//相对于FIFO，增加顺序重置CACHE.remove(key);CACHE.put(key,value);return value.value;}

LFU最近最不常用，当缓存容量满时，移除访问次数最少的元素，如果访问次数相同的元素有多个，则移除最久访问的那个。设计要求参见leetcode 460（ LFU Cache）

public class LFUCache {//主要容器，用于保存k-vprivate Map<String, Object> keyToValue = https://www.isolves.com/it/cxkf/sf/2020-05-12/new HashMap<>();//记录每个k被访问的次数private Map keyToCount = new HashMap<>();//访问相同次数的key列表，按照访问次数排序，value为相同访问次数到key列表 。private TreeMap> countToLRUKeys = new TreeMap<>();private int capacity;public LFUCache(int capacity) {this.capacity = capacity;//初始化，默认访问1次，主要是解决下文}public Object get(String key) {if (!keyToValue.containsKey(key)) {return null;}touch(key);return keyToValue.get(key);}/*** 如果一个key被访问，应该将其访问次数调整 。* @param key*/private void touch(String key) {int count = keyToCount.get(key);keyToCount.put(key, count + 1);//访问次数增加//从原有访问次数统计列表中移除countToLRUKeys.get(count).remove(key);//如果符合最少调用次数到key统计列表为空，则移除此调用次数到统计if (countToLRUKeys.get(count).size() == 0) {countToLRUKeys.remove(count);}//然后将此key的统计信息加入到管理列表中LinkedHashSet countKeys = countToLRUKeys.get(count + 1);if (countKeys == null) {countKeys = new LinkedHashSet<>();countToLRUKeys.put(count + 1,countKeys);}countKeys.add(key);}public void put(String key, Object value) {if (capacity <= 0) {return;}if (keyToValue.containsKey(key)) {keyToValue.put(key, value);touch(key);return;}//容量超额之后，移除访问次数最少的元素if (keyToValue.size() >= capacity) {Map.Entry> entry = countToLRUKeys.firstEntry();Iterator it = entry.getValue().iterator();String evictKey = it.next();it.remove();if (!it.hasNext()) {countToLRUKeys.remove(entry.getKey());}keyToCount.remove(evictKey);keyToValue.remove(evictKey);}keyToValue.put(key, value);keyToCount.put(key, 1);LinkedHashSet keys = countToLRUKeys.get(1);if (keys == null) {keys = new LinkedHashSet<>();countToLRUKeys.put(1,keys);}keys.add(key);}}

End本文力求比较三个基本的缓存算法，以便对缓存建设之路有一个比较笼统的感觉。
更加易用的cache，可以参考guava的实现。谨希望这三个代码模版，能够对你有所帮助。

【3种堆内缓存算法】