概念
LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。
什么是Cache？狭义的Cache指的是位于CPU和主存间的快速RAM， 通常它不像系统主存那样使用DRAM技术，而使用昂贵但较快速的SRAM技术。 广义上的Cache指的是位于速度相差较大的两种硬件之间， 用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache， 内存与硬盘之间也有Cache，乃至在硬盘与网络之间也有某种意义上的Cache── 称为Internet临时文件夹或网络内容缓存等。
Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时， 就需要挑选并舍弃原有
的部分内容，从而腾出空间来放新内容。
LRU Cache 的替换原则就是将最近最少使用的内容替换掉。
其实，LRU译成最久未使用会更形象， 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。
LRUCache 的运行机制
LRUCache 使用的是 哈希表加双向链表的 数据结构进行实现的，由于使用哈希表，那么查找的时间复杂度为O(1)，使用双向链表，那么在插入和删除结点的时间复杂度页为 O(1)，总体来看，LRUCache 的查找、插入以及删除的时间复杂度均为O(1)，效率十分的高
数据的插入是以尾插的形式进行的，如果空间不够的话，就会删除最前面的数据，然后再执行插入操作。
如果更新或者访问数据的话，就会将数据放到最后面。
因此，LRUCahche 会将经常访问的数据放在后面，将不经常访问的数据放在前面，如果插入的时候，发现空间不够，就会删除前面的数据也就是不经常访问的数据。
LinkedHashMap
在Java 中，类似LRUCahe的数据结构是 LinkedHashMap.
构造方法：
参数说明：
1.initialCapacity 初始容量大小，使用无参构造方法时，此值默认是16
2.loadFactor 加载因子，使用无参构造方法时，此值默认是 0.75f
3.accessOrder
false：基于插入顺序
true：基于访问顺序
解释一下 accessOrder，accessOrder 表示你有没有需求——把经常访问到的数据放到后面，把不经常访问到的数据放到前面，如果你有这个需求可以设置为 true (也就是基于访问顺序进行对数据的管理)，如果你没有这个需求，只是单纯的插入数据，那么可以指定为 false
大家页看到了还有其他一些构造方法，这些构造方法不需要指定 accessOrder，那么Java 会默认你是 基于访问顺序，也就是 accessOrder = true 来进行管理数据，毕竟 LinkedHashMap 是 LRUCache 数据结构。
演示：
asscessOrder 等于 false， 基于插入顺序管理数据。
public static void main(String[] args) {LinkedHashMap<Integer,Character> map = new LinkedHashMap<>(5,0.7f,false);map.put(3,'c');map.put(2,'d');map.put(5,'s');map.get(2);System.out.println(map);map.get(3);System.out.println(map);}
accessOrder 等于 true ，基于访问顺序 管理数据：
public static void main(String[] args) {LinkedHashMap<Integer,Character> map = new LinkedHashMap<>(5,0.7f,true);map.put(3,'c');map.put(2,'d');map.put(5,'s');System.out.println(map);map.get(2);System.out.println(map);map.get(3);System.out.println(map);}
模拟实现
结构定义
我们需要哈希表和双向链表两种数据结构，这里我们直接使用哈希表 HashMap，就不模拟哈希表的实现了。哈希表我们存放 key 和 Node 这两个数值，这样我们就可以通过 key 获取到 key 所在的结点了。
双向链表需要结点，我们来定义结点：
static class Node {int key;int val;Node prev;Node next;public Node(int key, int val) {this.key = key;this.val = val;}public Node() {}}
我们使用双向链表进行插入和删除的时候，可以提前定义好两个空结点，方便我们插入和删除操作，所以上面的结点里面还定义了空的构造方法。
除此之外，我们还需要两个成员变量，一个用来记录当前使用了多少的空间，另一个则是用来记录容量的大小。
HashMap<Integer,Node> map;int useSized; //使用空间int capacity; //容量//两个辅助结点，便于插入和删除操作Node head;Node tail;
最后我们来搭建LRUCache 的两个构造方法：
//提供构造方法public LRUCache() {capacity = 3;map = new HashMap<>();head = new Node();tail = new Node();head.next = tail;tail.prev = head;}public LRUCache(int capacity) {this.capacity = capacity;map = new HashMap<>();head = new Node();tail = new Node();head.next = tail;tail.prev = head;}
查找
使用哈希表的 get 方法，就可以找到对应的结点。
//查找public Node get(int key) {return map.get(key);}
删除
删除某个数值，我们先通过哈希表得到结点，然后对链表和哈希表同时进行删除操作。
public boolean remove(int key) {Node node = get(key);if(node == null) {return false;}removeNode(node);return true;}private void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;map.remove(node.key);}
插入
插入首先我们要找到是否已经存在 key 这个数值
如果存在，我们则需要更新数据，然后将结点插入到后面。
如果不存在，我们就需要查看当前的useSized 是不是已经达到最大容量了，如果达到最大容量，我们需要先删除前面的一个有效结点，再去插入新结点；如果没有达到最大容量，我们直接插入结点即可，同时 useSized + 1。
//插入public void put(int key, int val) {Node node = get(key);Node newNode = new Node(key,val);if(node == null) {//如果不存在这个结点，需要插入到尾巴if(useSized == capacity) {//需要进行删除removeFrontNode();//插入insertToTail(newNode);} else {//插入insertToTail(newNode);useSized++;}} else {//如果存在这个结点，需要进行更新操作，并且最后要将结点插入到尾巴removeNode(node);insertToTail(newNode);}}
这时候剩下的就是链表的基本操作了：
private void insertToTail(Node node) {Node prev = tail.prev;tail.prev = node;node.next = tail;node.prev = prev;prev.next = node;map.put(node.key,node);}private void removeFrontNode() {Node del = head.next;head.next = del.next;del.next.prev = head;map.remove(del.key);}
最终代码
import java.util.HashMap;public class LRUCache {HashMap<Integer,Node> map;int useSized; //使用空间int capacity; //容量//两个辅助结点，便于插入和删除操作Node head;Node tail;static class Node {int key;int val;Node prev;Node next;public Node(int key, int val) {this.key = key;this.val = val;}public Node() {}}//提供构造方法public LRUCache() {capacity = 3;map = new HashMap<>();head = new Node();tail = new Node();head.next = tail;tail.prev = head;}public LRUCache(int capacity) {this.capacity = capacity;map = new HashMap<>();head = new Node();tail = new Node();head.next = tail;tail.prev = head;}//插入public void put(int key, int val) {Node node = get(key);Node newNode = new Node(key,val);if(node == null) {//如果不存在这个结点，需要插入到尾巴if(useSized == capacity) {//需要进行删除removeFrontNode();//插入insertToTail(newNode);} else {//插入insertToTail(newNode);useSized++;}} else {//如果存在这个结点，需要进行更新操作，并且最后要将结点插入到尾巴removeNode(node);insertToTail(newNode);}}public boolean remove(int key) {Node node = get(key);if(node == null) {return false;}removeNode(node);return true;}private void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;map.remove(node.key);}private void insertToTail(Node node) {Node prev = tail.prev;tail.prev = node;node.next = tail;node.prev = prev;prev.next = node;map.put(node.key,node);}private void removeFrontNode() {Node del = head.next;head.next = del.next;del.next.prev = head;map.remove(del.key);}//查找public Node get(int key) {return map.get(key);}
}
