前言
大家好，我是bigsai，好久不见，甚是惦记！
最近有个小伙伴跟我诉苦，说他没面到LRU，他说他很久前晓得有被问过LRU的然而心想本人应该不会遇到，所以临时就没筹备。
奈何不巧，这还就真的考到了！他此刻的情绪，能够用一张图来证实：
他说他最终踉踉跄跄的写了一个效率不是很高的LRU，面试官看着不是很称心……起初果然GG了。
避免日后再碰到这个坑，明天和大家一起把这个坑踩了，这道题我本身刚开始也是用较为一般的办法，然而好的办法尽管不是很难然而想了真的很久才想到，尽管花了太多工夫不太值，总算是本人想进去了，将这个过程给大家分享一下(只从算法的角度，不从操作系统的角度)。
了解LRU
设计一个LRU，你得晓得什么是LRU吧？
LRU，英文全称为Least Recently Used，翻译过去就是最近最久未应用算法，是一种罕用的页面置换算法。
说起页面置换算法，这就是跟OS关系比拟大的了，咱们都晓得内存的速度比拟快，然而内存的容量是十分无限的，不可能给所有页面装到内存中，所以就须要一个策略将罕用的页面预放到内存中。
然而吧，谁也不晓得过程下次会拜访哪个内存，并不能很无效的晓得(咱们在以后并没有预测将来的性能)，所以有些页面置换算法只是理想化然而没法实在实现的(没错就是最佳置换算法(Optimal)),而后常见必回的算法就是FIFO(先进先出)和LRU(最近最久未应用)。
LRU了解不难，就是保护一个有固定大小的容器，外围就是get()和put()两个操作。
咱们先看一下LRU会有的两个操作：
初始化：LRUCache(int capacity) ，以正整数作为容量 capacity 初始化 LRU 缓存。
查问：get(int key),从本人的设计的数据结构中查找是否有以后key对应的value，如果有那么返回对应值并且要将key更新记录为最近应用，如果没有返回-1。
插入/更新：put(int key,int value)，可能是插入一个key-value，也可能是更新一个key-value，如果容器中曾经存才这个key-value那么只须要更新对应value值，并且标记成最新。如果容器不存在这个值，那么要思考容器是否满了，如果满了要先删除最久未应用的那对key-value。
这里的流程能够给大家举个例子，例如
容量大小为2：[ "put", "put", "get", "put","get", "put","get","get","get"][ [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]这个过程如下：
大家容易疏忽的细节有：
- put()存在更新的操作,例如put(3,3),put(3,4)会更新key为3的操作。
- get()可能查问不到，然而查问到也会更新最久未应用的程序。
- 如果容器未应用满，那么put可能更新可能插入，然而不会删除；如果容器满了并且put插入，就要思考删除最久未应用的key-value了。
对于下面的这么一个规定，咱们该如何解决呢？
如果单单用一个List相似的列表，能够顺序存储键值对，在List后面的(0下标为前)咱们认为它是比拟久的，在List后咱们认为它是比拟新的。咱们思考下各种操作可能会这样设计：
如果来get操作：
遍历List一个个比对，查看是否有该key的键值对，如果有间接返回对应key的value，如果没有那么返回-1.
如果来put操作：
遍历List，如果有该key的键值对，那么果决删除这个key-value，最初在开端对立插入该键值对。
如果没有对应的key并且List容器曾经达到最满了，那么果决删除第一个地位的key-value。
用List可能须要两个(一个存key一个存value)，或者一个存Node节点(key，value为属性)的List，思考下这个工夫复杂度：
put操作：O(n)，get操作：O(n) 两个操作都须要枚举列表线性复杂度，效率属实有点拉胯，必定不行，这样的代码我就不写了。
哈希初优化
从下面的剖析来看，咱们曾经能够很自信的将LRU写进去了，不过当初要思考的是一个优化的事件。
如果说咱们将程序中引入哈希表，那么必定会有一些优化的。用哈希表存储key-value，查问是否存在的操作都能优化为O(1),然而删除或者插入或者更新地位的复杂度可能还是O(n),咱们一起剖析一下：
最久未应用肯定是一个有序的序列来贮存，要么是程序表(数组)要么是链表，如果是数组实现的ArrayList存储最久未应用这个序列。
如果是ArrayList进行删除最久未应用(第一个)key-value，新的key被命中变成最新被应用(先删除而后插入开端)操作都是O(n)。
同理如果是LinkedList的一些操作大部分也是O(n)的，像删除第一个元素这个是因为数据结构起因O(1)。
你发现自己的优化空间其实十分十分小，然而的确还是有提高的，只是被卡住不晓得双O(1)的操作到底怎么优化，这外面我把这个版本代码放进去，大家能够参考一下(如果面试问到切实不会能够这么写)
class LRUCache { Map<Integer,Integer>map=new HashMap<>(); List<Integer>list=new ArrayList<>(); int maxSize; public LRUCache(int capacity) { maxSize=capacity; } public int get(int key) { if(!map.containsKey(key))//不存在返回-1 return -1; int val=map.get(key); put(key,val);//要更新地位 变成最新 很重要！ return val; } public void put(int key, int value) { //如果key存在，间接更新即可 if (map.containsKey(key)) { list.remove((Integer) key); list.add(key); } else {//如果不存在 要插入到最初，然而如果容量满了须要删除第一个(最久) if (!map.containsKey(key)) { if (list.size() == maxSize) { map.remove(list.get(0)); list.remove(0); } list.add(key); } } map.put(key, value); }}哈希+双链表
下面咱们曾经晓得用哈希可能间接查到有木有这个元素，然而苦于删除！用List都很费劲。
更具体的说，是苦于List的删除操作，Map的删除插入还是很高效的。
在下面这种状况，咱们心愿的就是可能疾速删除List中任意一个元素，并且效率很高，如果借助哈希只能最多定位到，然而无奈删除啊！该怎么办呢？
哈希+双链表啊！
咱们将key-val的数据存到一个Node类中，而后每个Node晓得左右节点，在插入链表的时候间接存入Map中，这样Map在查问的时候能够间接返回该节点，双链表晓得左右节点能够间接将该节点在双链表中删除。
当然，为了效率，这里实现的双链表带头结点(头指针指向一个空节点避免删除等异常情况)和尾指针。
对于这个状况，你须要可能手写链表和双链表啦，双链表的增删改查曾经写过清清楚楚，小伙伴们不要放心，这里我曾经整顿好啦：
单链表：https://mp.weixin.qq.com/s/Cq98GmXt61-2wFj4WWezSg
双链表：https://mp.weixin.qq.com/s/h6s7lXt5G3JdkBZTi01G3A
也就是你能够通过HashMap间接失去在双链表中对应的Node，而后依据前后节点关系删除，期间要思考的一些null、尾指针删除等等非凡状况即可。
具体实现的代码为：
class LRUCache { class Node { int key; int value; Node pre; Node next; public Node() { } public Node( int key,int value) { this.key = key; this.value=value; } } class DoubleList{ private Node head;// 头节点 private Node tail;// 尾节点 private int length; public DoubleList() { head = new Node(-1,-1); tail = head; length = 0; } void add(Node teamNode)// 默认尾节点插入 { tail.next = teamNode; teamNode.pre=tail; tail = teamNode; length++; } void deleteFirst(){ if(head.next==null) return; if(head.next==tail)//如果删除的那个刚好是tail 留神啦 tail指针后面挪动 tail=head; head.next=head.next.next; if(head.next!=null) head.next.pre=head; length--; } void deleteNode(Node team){ team.pre.next=team.next; if(team.next!=null) team.next.pre=team.pre; if(team==tail) tail=tail.pre; team.pre=null; team.next=null; length--; } public String toString() { Node team = head.next; String vaString = "len:"+length+" "; while (team != null) { vaString +="key:"+team.key+" val:"+ team.value + " "; team = team.next; } return vaString; } } Map<Integer,Node> map=new HashMap<>(); DoubleList doubleList;//存储程序 int maxSize; LinkedList<Integer>list2=new LinkedList<>(); public LRUCache(int capacity) { doubleList=new DoubleList(); maxSize=capacity; } public void print(){ System.out.print("maplen:"+map.keySet().size()+" "); for(Integer in:map.keySet()){ System.out.print("key:"+in+" val:"+map.get(in).value+" "); } System.out.print(" "); System.out.println("listLen:"+doubleList.length+" "+doubleList.toString()+" maxSize:"+maxSize); } public int get(int key) { int val; if(!map.containsKey(key)) return -1; val=map.get(key).value; Node team=map.get(key); doubleList.deleteNode(team); doubleList.add(team); return val; } public void put(int key, int value) { if(map.containsKey(key)){// 曾经有这个key 不思考长短间接删除而后更新 Node deleteNode=map.get(key); doubleList.deleteNode(deleteNode); } else if(doubleList.length==maxSize){//不蕴含并且长度小于 Node first=doubleList.head.next; map.remove(first.key); doubleList.deleteFirst(); } Node node=new Node(key,value); doubleList.add(node); map.put(key,node); }}就这样，一个get和put都是O(1)复杂度的LRU写进去啦！
序幕
起初看了题解，才发现，Java中的LinkedHashMap也差不多是这种数据结构！几行解决，然而个别面试官可能不会认同，还是会心愿大家可能手写一个双链表的。
class LRUCache extends LinkedHashMap<Integer, Integer>{ private int capacity; public LRUCache(int capacity) { super(capacity, 0.75F, true); this.capacity = capacity; } public int get(int key) { return super.getOrDefault(key, -1); } public void put(int key, int value) { super.put(key, value); } @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { return size() > capacity; }}哈希+双链表尽管在未看题解的状况想进去，然而真的花了挺久才想到这个点，以前见得的确比拟少，高效手写LRU到明天算是真真正正的齐全把握啦！
不过除了LRU,其余的页面置换算法无论口试还是面试也是十分高频啊，大家有空本人梳理一下哦。
首发公众号：bigsai 转载请搁置作者和原文(本文)链接 ,定期分享，欢送一起打卡力扣、学习交换！