【原创图解 算法leetcode 146】实现一个LRU缓存淘汰策略策略的数据结构

1 概念

LRU是Least Recently Used的缩写，即最近最少使用，是一种常见的缓存淘汰算法。
其核心思想为：当内存达到上限时，淘汰最久未被访问的缓存。

2 LeetCode

LeetCode: 146. LRU缓存

3 实现

通过上面LRU的淘汰策略可知，需要记录每个缓存key的访问时间顺序，并且在达到缓存上限时，淘汰最久没有被访问的那个key。
由于是淘汰最久未被使用的key，可以并不需要记录每个key的访问时间戳这样细的粒度，只需要根据对key的访问时间进行排序来得到最久未被访问的key。这个有序的数据结构可以采用双向队列来实现，其核心思想为：

1. 使用map来存储缓存的key, value，并且将key存入一个双端队列中。
2. 当put缓存时，先判断key是否在缓存中，若是将key移动到队列的末尾（代表最近被访问），否则直接将key添加到队列末尾。然后判断缓存是否超过容量限制，若是则将队列头的key移除并从map中移除缓存。
3. 当get缓存时，将key移动到队列头部（代表最近被访问）。

即通过双端队列来维护对缓存key的访问顺序，当存入和读取缓存key时，都将其移动到最后的位置，当缓存超过容量限制的时候，就从头的位置开始删除缓存。如下图所示

2.1 使用LinkedList + HashMap实现

class LRUCache<K, V> {private final int capacity;private final Map<K, V> cache;private final LinkedList<K> list;public LRUCache(int capacity) {this.capacity = capacity;this.cache = new HashMap<>(capacity);this.list = new LinkedList<>();}public synchronized V get(K key) {if (!cache.containsKey(key)) {return null;}// 访问这个key直接放到最后，代表最近访问list.remove(key);list.addLast(key);// 然后返回这个key的valuereturn cache.get(key);}public synchronized void put(K key, V value) {if (cache.containsKey(key)) {list.remove(key);}// 然后放入缓存并放到最新的一个位置cache.put(key, value);list.addLast(key);// 如果cache满了，就把最久未访问的key删掉while (cache.size() > capacity) {K remove = list.removeFirst();cache.remove(remove);}}
}

2.2 使用LinkedHashMap实现

class LRUCache2<K, V> extends LinkedHashMap<K, V> {private final int capacity;public LRUCache2(int capacity) {// 初始化容量，开启访问排序super(capacity, 0.75F, true);this.capacity = capacity;}@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {// 超过容量，删除最久未使用的元素return size() > capacity;}
}

源码见：GitHub欢迎star