一次倒在LRU上的经历

转x33g5p2x  于2021-12-07 转载在 其他  
字(5.9k)|赞(0)|评价(0)|浏览(282)

前言

大家好，我是bigsai，好久不见，甚是想念！

最近有个小伙伴跟我诉苦，说他没面到LRU，他说他很久前知道有被问过LRU的但是心想自己应该不会遇到，所以暂时就没准备。

奈何不巧，这还就真的考到了！他此刻的心情，可以用一张图来证明：

他说他最终踉踉跄跄的写了一个效率不是很高的LRU，面试官看着不是很满意要求写一个O(1)复杂度的LRU……后来果真GG了，后来发现这是力扣146的一道原题。

防止日后再碰到这个坑，今天和大家一起把这个坑踩了，这道题我自身刚开始也是用较为普通的方法，但是好的方法虽然不是很难但是想了真的很久才想到，虽然花了太多时间不太值，总算是自己想出来了，将这个过程给大家分享一下(只从算法的角度，不从操作系统的角度)。

理解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。

这里的流程可以给大家举个例子，例如

  1. 容量大小为2：
  2. [ "put",  "put", "get", "put","get", "put","get","get","get"]
  3. [ [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操作：

如果来put操作：

用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)的操作究竟怎么优化，这里面我把这个版本代码放出来，大家可以参考一下(如果面试问到实在不会可以这么写)

  1. class LRUCache {
  3.     Map<Integer,Integer>map=new HashMap<>();
  4.     List<Integer>list=new ArrayList<>();
  5.     int maxSize;
  6.     public  LRUCache(int capacity) {
  7.         maxSize=capacity;
  8.     }
  10.     public int get(int key) {
  11.         if(!map.containsKey(key))//不存在返回-1
  12.             return -1;
  13.         int val=map.get(key);
  14.         put(key,val);//要更新位置 变成最新 很重要！
  15.         return val;
  16.     }
  18.     public void put(int key, int value) {
  19.         //如果key存在，直接更新即可
  20.         if (map.containsKey(key)) {
  21.             list.remove((Integer) key);
  22.             list.add(key);
  23.         } else {//如果不存在 要插入到最后，但是如果容量满了需要删除第一个(最久)
  24.             if (!map.containsKey(key)) {
  25.                 if (list.size() == maxSize) {
  26.                     map.remove(list.get(0));
  27.                     list.remove(0);
  28.                 }
  29.                 list.add(key);
  30.             }
  31.         }
  32.         map.put(key, value);
  33.     }
  34. }

哈希+双链表

上面我们已经知道用哈希能够直接查到有木有这个元素，但是苦于删除！用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、尾指针删除等等特殊情况即可。

具体实现的代码为：

  1. class LRUCache {
  2.     class Node {
  3.         int key;
  4.         int value;
  5.         Node pre;
  6.         Node next;
  8.         public Node() {
  9.         }
  11.         public Node( int key,int value) {
  12.             this.key = key;
  13.             this.value=value;
  14.         }
  15.     }
  16.     class DoubleList{
  17.         private Node head;// 头节点
  18.         private Node tail;// 尾节点
  19.         private int length;
  20.         public DoubleList() {
  21.             head = new Node(-1,-1);
  22.             tail = head;
  23.             length = 0;
  24.         }
  25.         void add(Node teamNode)// 默认尾节点插入
  26.         {
  27.             tail.next = teamNode;
  28.             teamNode.pre=tail;
  29.             tail = teamNode;
  30.             length++;
  31.         }
  32.         void deleteFirst(){
  33.             if(head.next==null)
  34.                 return;
  35.             if(head.next==tail)//如果删除的那个刚好是tail  注意啦 tail指针前面移动
  36.                 tail=head;
  37.             head.next=head.next.next;
  39.             if(head.next!=null)
  40.                 head.next.pre=head;
  41.             length--;
  42.         }
  43.         void deleteNode(Node team){
  45.             team.pre.next=team.next;
  46.             if(team.next!=null)
  47.                 team.next.pre=team.pre;
  48.             if(team==tail)
  49.                 tail=tail.pre;
  50.            team.pre=null;
  51.            team.next=null;
  52.             length--;
  53.         }
  54.         public String toString() {
  55.             Node team = head.next;
  56.             String vaString = "len:"+length+" ";
  57.             while (team != null) {
  58.                 vaString +="key:"+team.key+" val:"+ team.value + " ";
  59.                 team = team.next;
  60.             }
  61.             return vaString;
  62.         }
  63.     }
  64.     Map<Integer,Node> map=new HashMap<>();
  65.     DoubleList doubleList;//存储顺序
  66.     int maxSize;
  67.     LinkedList<Integer>list2=new LinkedList<>();
  69.     public   LRUCache(int capacity) {
  70.         doubleList=new DoubleList();
  71.         maxSize=capacity;
  72.     }
  73.     public  void print(){
  74.         System.out.print("maplen:"+map.keySet().size()+" ");
  75.         for(Integer in:map.keySet()){
  76.             System.out.print("key:"+in+" val:"+map.get(in).value+" ");
  77.         }
  78.         System.out.print("              ");
  79.         System.out.println("listLen:"+doubleList.length+" "+doubleList.toString()+" maxSize:"+maxSize);
  80.     }
  82.     public int get(int key) {
  83.         int val;
  84.         if(!map.containsKey(key))
  85.             return  -1;
  86.         val=map.get(key).value;
  87.         Node team=map.get(key);
  88.         doubleList.deleteNode(team);
  89.         doubleList.add(team);
  90.         return  val;
  91.     }
  93.     public void put(int key, int value) {
  94.         if(map.containsKey(key)){// 已经有这个key 不考虑长短直接删除然后更新
  95.            Node deleteNode=map.get(key);
  96.             doubleList.deleteNode(deleteNode);
  97.         }
  98.         else if(doubleList.length==maxSize){//不包含并且长度小于
  99.             Node first=doubleList.head.next;
  100.             map.remove(first.key);
  101.             doubleList.deleteFirst();
  102.         }
  103.        Node node=new Node(key,value);
  104.         doubleList.add(node);
  105.         map.put(key,node);
  107.     }
  108. }

就这样，一个get和put都是O(1)复杂度的LRU写出来啦！

尾声

后来看了题解，才发现，Java中的LinkedHashMap也差不多是这种数据结构！几行解决，但是一般面试官可能不会认同，还是会希望大家能够手写一个双链表的。

  1. class LRUCache extends LinkedHashMap<Integer, Integer>{
  2.     private int capacity;
  4.     public LRUCache(int capacity) {
  5.         super(capacity, 0.75F, true);
  6.         this.capacity = capacity;
  7.     }
  9.     public int get(int key) {
  10.         return super.getOrDefault(key, -1);
  11.     }
  13.     public void put(int key, int value) {
  14.         super.put(key, value);
  15.     }
  17.     @Override
  18.     protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
  19.         return size() > capacity; 
  20.     }
  21. }//这个来源官方题解 给大家分享一下

哈希+双链表虽然在未看题解的情况想出来，但是真的花了挺久才想到这个点，以前见得确实比较少，高效手写LRU到今天算是真真正正的完全掌握啦！

不过除了LRU,其他的页面置换算法无论笔试还是面试也是非常高频啊，大家有空自己梳理一下哦。

除了算法水平真的很强的，不然大部分人其实不可能当场想到一些比较巧妙的方法，所以面对笔试最好的诀窍还是多刷力扣。

**所以，有兴趣的可以加我拉你进力扣打卡群，一起坚持刷题。
**

欢迎加我[bigsai66]加入力扣打卡群

推荐阅读：

有这几个编程利器网站，再也不愁学习

动态规划，它来了

备战蓝桥杯  这样准没错！

欢迎关注 **「bigsai」，**获取个人原创数据结构算法学习pdf

原创不易，大赛ge求个三连！

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/qq_40693171/article/details/121759664

内容来源于网络，如有侵权，请联系作者删除！

Javaredis数据结构算法链表

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com