LRU—>面试算法中的明星

Dear 丶 2022-05-10 14:10 170阅读 0赞

博主在keep、度小满和头条的面试中都曾遇到过这位“算法届小明星”；身边有同学在百度的面试中也层遇到过。LRU名副其实的面试算法明星。

那么LRU究竟是个什么东西呢，听上去是那么的高大上。Least Recently Used就是LRU的真面目，翻译过来是：最近最少使用，什么意思呢，请看下面这个示例。

我们要在有限的内存中存放一些<K,V>键值对，这些键值对很多，所有的键值对所占内存大于物理可用内存，并且每个键值对被访问的情况也是不一样的。当内存用尽的时候，这时新来了一个键值对，这时我们要如何处理呢？从内存中删除“潜水”时间最长的那个键值对，这样就可以把新来的键值对存入内存了，这就是LRU算法，也是在Redis缓存丢弃策略的一种。上面说的“潜水”时间最长指的是：被人遗忘时间最长的那个键值对，遗忘指的是没有被人访问过。

总结之下，LRU就是当你内存中数据到达指定容量的时候，LRU选择将最长时间没有被使用过的那个键值对从内存中移除。

我们回顾一下要实现的功能，功能完成了，LRU也就实现了：

1.  我们需要存储<K,V>键值对
2.  可以指定可以存储多少个键值对
3.  当存储容量满了以后，移除最长时间没有被访问过的键值对

分析一下上面的需求

*  **存储键值对**：第一想法是使用HashMap存储，毕竟HashMap是为“存储键值对而生”。
 *  **指定容量**：这也容易，每次向map中put键值对后，就检查map的容量是否超出了指定的容量，如果超出了，从map中移除一个元素即可。
 *  移除谁？难点在这里，当map在put操作之后超出了指定容量，我们移除谁？怎么找出那个“潜水”时间最长的键值对呢？第一个想法是我们需要维护一个有序的链表，这个链表从前到后“潜水”时间越来越短。这样当map的容量满了以后我们只需要获取链表头部元素，然后从map中移除该键值对即可，这也说明了链表节点中需要包含对应键值对的key，否则找到链表头结点后如何移除呢？
 *  为什么使用链表？容量指定的情况下，为什么不使用数组呢？原因如下，“潜水”时间最长的键值对经常发送变化，也就是链表中元素顺序经常发生改变，另外一方面，链表的插入和操作删除效率要比数组高。
 *  如何维护链表节点的顺序？可以这样，当一个“潜水”的键值对被访问后，把该节点从链表中移除，然后把这个节点插入到链表末尾，这样就可以保证链表第一个元素永远是“潜水”时间最长的键值对；链表末尾的元素永远是最近被访问过的元素。这样当map超出指定容量之后只需要删除链表头的键值对即可。

public class LRUCache {
    //“潜水”链表节点，抽象
       static class Node{
           //键值对
           private int key;
           private int value;
    
           //维护“潜水”键值对，双向链表
           private Node pre;
           private Node next;
    
           //构造器
           Node(){}
    
           Node(int key,int value){
            this.key = key;
            this.value = value;
        }
    }
    
    //指定的容量
    private int cap;
    
    //保留“潜水”双向链表的头尾指针
    private Node head;
    private Node tail;
    
    //保存键值对的map
    private HashMap<Integer,Node> map;
    
    //构造器参数是：指定的容量
    public LRUCache(int capacity) {
        this.cap = capacity;
    
        //初始化头尾节点，这里的头结点是辅助节点
        //head节点不存储任何有效元素
        head = new Node();
        tail = head;
    
        //构造器初试容量这样设置可以保证map
        //不会发生扩容，详见之前的HashMap
        //讲解文章
        map = new HashMap<>((int)(cap/0.75)+1);
    }
    
    //将指定节点从链表中删除
    private void removeNode(Node cur){
        if(cur==tail){
            tail = tail.pre;
    
            tail.next = null;
            cur.pre = null;
        }else{
            cur.pre.next = cur.next;
            cur.next.pre = cur.pre;
    
            cur.pre = null;
            cur.next = null;
        }
    }
    
    
    //将指定节点追加到链表末尾
    private void add(Node cur){
        tail.next = cur;
        cur.pre = tail;
    
        tail = cur;
    }
    
    //访问一个键值对
    public int get(int key) {
        Node cur = map.get(key);
        //不存在这个key
        if(cur==null){
            return -1;
        }else{//存在
         //含义是当前潜水节点已经被访问了
         //将这个节点添加到链表末尾
            removeNode(cur);
            add(cur);
    
            return cur.value;
        }
    }
    
    //存储一个键值对
    public void put(int key, int value) {
        Node cur =  map.get(key);
    
        if(cur==null){
            //put前不存在这个key
            cur = new Node(key,value);
    
           //将该键值对移动到链表末尾
            map.put(key,cur);
            add(cur);
    
            //超出了容量，移除链表头结点
            //后面那个元素(头结点是辅助节点)
           if(map.size()>cap && head!=tail){
               Node outDate  = head.next;
                removeNode(outDate);
    
                //不能忘记这里
                 map.remove(outDate.key);
            }
        }else{
    
           //put之前已经存在
           //将这个键值对移到链表末尾即可
            removeNode(cur);
            add(cur);
            //更新这个key的值
            cur.value = value;            
        }
    }
    
    }

对LRU算法还有疑问的同学请在评论中留言。希望大家更多的是理解，理解之后，LRU算法就不那么难了，学习在于理解。文章有不足支持欢迎大家评论留言~。

最后LinkedHashMap其实是可以直接支持LRU的，面试的时候可以提及这一点，但是面试官不会支持你使用LinkedHashMap实现LRU。之后讲解LinkedHashMap源码的时候会有详细说明，实质上LinkedHashMap底层实现也是类似原理，使用LinkedHashMap实现LRU代码如下：

//继承一下LinkedHashMap这个类，
    
    //使用LinkedHashMap实现LRU算法
    
    public class LRULinkedHashMap<K,V>  extends LinkedHashMap<K,V>{
          //定义缓存的容量
          private int capacity;
    
          //带参数的构造器   
          LRULinkedHashMap (int capacity){
              //调用LinkedHashMap的构造器
              super(capacity,0.75f,true);
    
              //传入指定的缓存最大容量
              this.capacity=capacity;
          }
    
    //返回true就会移除“潜水”时间最长
    //的键值对
          @Override
      public boolean removeEldestEntry(Map.Entry<K, V> eldest){
    
            //参数eldest就是“潜水”时间最长的键值对，可以获得对应的key,value
              return size()>capacity;
          }  
    
      }

--------------------

扫描下方二维码，**及时**获取更多**互联网求职面经**、**java**、**python**、**爬虫**、**大数据**等技术，和**海量资料分享**：  
公众号**`菜鸟名企梦`**后台发送“**csdn**”即可免费领取【csdn】和【百度文库】下载服务；  
公众号**`菜鸟名企梦`**后台发送“**资料**”:即可领取**5T精品学习资料**、**java面试考点**和**java面经总结**，以及**几十个java、大数据项目**，**资料很全，你想找的几乎都有**

![扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）][1240]

扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）

[1240]: /images/20220505/46a52f2cbae34b2b990ea3347e9d8994.png