LRU—>面試算法中的明星

部落客在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、大資料項目，資料很全，你想找的幾乎都有

掃碼關注，及時擷取更多精彩内容。（部落客今日頭條大資料工程師）