LRU算法原理与实践

简介

操作系统中进行内存管理中时采用一些页面置换算法，如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);
    }
}