简介
操作系统中进行内存管理中时采用一些页面置换算法，如LRU、LFU和FIFO等。其中LRU应用较为广泛。LRU的全称是Least Recently Used，即最近最少使用算法。
大家都知道在缓存的大小是有限的，那么我们应该基于什么策略进行缓存数据呢？LRU提供的思路是将最近没有使用的数据从缓存中移除，这样的思路在实际的环境中比较符合常识。
原理
LRU算法的原理比较简单，数据存储的数据结构为链表。当访问数据时，如缓存中有数据，则将该数据移动至链表的顶端；没有该数据则在顶端加入该数据，并移除链表中的低端的数据。
LRU涉及一个概念叫做缺页中断，缺页中断的次数即一次访问过程时没有没有在缓存中找到数据。
假如页面大小为3，序列为4、3、2、3、5，下面的缺页次数为4次
| 4 | 3 | 2 | 3 | 5 |
|---|---|---|---|---|
| 4 | 3 | 2 | 3 | 5 |
| null | 4 | 3 | 2 | 3 |
| null | null | 4 | 4 | 2 |
| 缺页 | 缺页 | 缺页 | 不缺 | 缺页 |
代码实现
LRU算法原理较为简单，但是实现较为复杂，尤其是处理页面替换时，在Java中的LinkedHashMap的访问有序性恰好满足LRU的需求。下面通过LeetCode第146题描述下算法的实现过程
样例：
实现如下操作，且时间复杂度为O(1)
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
代码实现
public class LRUCache {
private LinkedHashMap<Integer, Integer> map;
private final int CAPACITY;
public LRUCache(int capacity) {
CAPACITY = capacity;
map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true){
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > CAPACITY;
}
};
}
public int get(int key) {
return map.getOrDefault(key, -1);
}
public void put(int key, int value) {
map.put(key, value);
}
}
