一、什么是LRU算法

LRU，Least Recently Used算法，即一种缓存淘汰策略。

计算机的缓存容量有限，若缓存满了则需要删除一些内容，给新的缓存腾出空间，但问题是要删除哪些内容呢？当然是把用的少的缓存删掉，把最有用的数据继续保留以便于继续使用。那么如何判定哪些数据是有用的呢？

缓存淘汰的策略有很多，而LRU则是一种较为简单常用的算法，LRU判定最近使用过的数据为有用的，很久都没用过的数据是无用的，在内存满了就优先删除很久未使用，也就是无用的数据。

常见的场景如手机的后台运行缓存，我们依次打开了[设置] [网易云音乐] [优酷视频] [bilibili]，假设手机只允许同时打开个应用程序，那么在我们打开bilibili的那一刻，就会将最久未使用的 [设置] 关闭，腾出空间给 [bilibili]

 

二、LRU的算法描述

①接收一个capacity的参数作为缓存的最大容量

②实现put(key,value)方法存入键值对

③实现get(key)方法获取key对应的value，若不存在返回-1

//缓存容量为2
LRUCache cache = new LRUCache(2);
//可以把cache理解为一个队列
//最近使用过的在队列头，久未使用的在队列尾cache.put(1,1);//cache = [(1,1)]cache.put(2,2);//cache = [(2,2),(1,1)]cache.get(1);//此时访问了key为1的entry 因此将其移动到队列头 cache = [(1,1),(2,2)]cache.put(3,3);//此时容量已满，需要删除久未使用的数据，也就是队列尾 然后插入新的数据 cache = [(3,3),(1,1)]cache.get(2);//return -1cache.put(1,4);//key=1已经存在，只需要覆盖value即可 且此时需要将更新的entry提前到队列头 cache = [(1,4),(3,3)]

 

三、LRU算法设计

要让LRUCache的put和get方法时间复杂度为O(1)，那么要求数据结构的查询时间为O(1)，插入时间为O(1)，删除时间为O(1)，且有序。

为了区分最近使用和久未使用的数据，我们必须要求cache有序；能够在cache中判断key是否存在；cache容量满了需要删除最后一个entry；每次访问的entry都重新放在队列头部。

为此我们可以考虑到HashMap与LinkedList的结合——LinkedHashMap

LRU缓存算法的核心就是基于LinkedHashMap实现的，其核心就是通过HashMap赋予链表查询迅速的特性

（图片来源LeetCode）

 

四、代码实现

首先将双向链表实现

class DoubleLinkedList {class Entry{int key;int value;Entry prev;Entry next;Entry(int key, int value) {this.key = key;this.value = value;}}private Entry head;private Entry tail;private int size;public LRUCache() {//缓存初始化head = new Entry(0,0);tail = new Entry(0,0);head.next = tail;tail.prev = head;int size = 0;}//在链表首部添加entrypublic void addFirst(Entry entry) {entry.next = head.next;entry.prev = head;head.next.prev = entry;head.next = entry;size++;}//删除链表中的entrypublic void remove(Entry entry) {Entry prev = entry.prev;Entry next = entry.next;prev.next = next;next.prev = prev;size--;}//删除链表中最后一个节点并返回public Entry removeLast() {if (tail.prev == head) {return null;}Entry last = tail.prev;remove(last);return last;}public int size() {return size;}
}

然后结合HashMap即可：

public class LRUCache {private HashMap<Integer, DoubleLinkedList.Entry> map;private DoubleLinkedList cache;private int capacity;public LRUCache(int capacity) {this.capacity = capacity;map = new HashMap<>();cache = new DoubleLinkedList();}public int get(int key) {//若map中不存在cache映射的key return -1if (!map.containsKey(key)) {return -1;}int val = map.get(key).value;//将get过的entry提前,put方法直接采用了删除尾部，首部添加的策略。put(key,val);return val;}public void put(int key, int val) {DoubleLinkedList.Entry x = new DoubleLinkedList.Entry(key,val);if (map.containsKey(key)) {//可以理解为缓存队列尾部删除 首部添加cache.remove(map.get(key));cache.addFirst(x);//map中添加该entry的映射map.put(key,x);} else {//当缓存已满，不仅要删除最后一个Entry，还要把map中映射到该节点的key同时删除，而这个key只能通过Entry得到。if(capacity == cache.size()) {//删除链表最后一个数据DoubleLinkedList.Entry last = cache.removeLast();map.remove(last.key);}cache.addFirst(x);map.put(key,x);}}
}

以上就是LRU的简单实现，

原文参考LeetCode：https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/

放个源码：https://github.com/whl-1998/DataStructAndAlgorithm/tree/master/src/com/whl