[[438898]]

本文轉(zhuǎn)載自微信公眾號「bigsai」，作者大賽  。轉(zhuǎn)載本文請聯(lián)系bigsai公眾號。

前言

大家好，我是bigsai，好久不見，甚是想念!

最近有個小伙伴跟我訴苦，說他沒面到LRU，他說他很久前知道有被問過LRU的但是心想自己應(yīng)該不會遇到，所以暫時就沒準(zhǔn)備。

奈何不巧，這還就真的考到了!他此刻的心情，可以用一張圖來證明：

[[438899]]

他說他最終踉踉蹌蹌的寫了一個效率不是很高的LRU，面試官看著不是很滿意要求寫一個O(1)復(fù)雜度的LRU……后來果真GG了，后來發(fā)現(xiàn)這是力扣146的一道原題。

防止日后再碰到這個坑，今天和大家一起把這個坑踩了，這道題我自身剛開始也是用較為普通的方法，但是好的方法雖然不是很難但是想了真的很久才想到，雖然花了太多時間不太值，總算是自己想出來了，將這個過程給大家分享一下(只從算法的角度，不從操作系統(tǒng)的角度)。

理解LRU

設(shè)計一個LRU，你得知道什么是LRU吧?

LRU，英文全稱為Least Recently Used，翻譯過來就是最近最久未使用算法，是一種常用的頁面置換算法。

說起頁面置換算法，這就是跟OS關(guān)系比較大的了，我們都知道內(nèi)存的速度比較快，但是內(nèi)存的容量是非常有限的，不可能給所有頁面裝到內(nèi)存中，所以就需要一個策略將常用的頁面預(yù)放到內(nèi)存中。

但是吧，誰也不知道進程下次會訪問哪個內(nèi)存，并不能很有效的知道(我們在當(dāng)前并沒有預(yù)測未來的功能)，所以有些頁面置換算法只是理想化但是沒法真實實現(xiàn)的(沒錯就是最佳置換算法(Optimal)),然后常見必回的算法就是FIFO(先進先出)和LRU(最近最久未使用)。

LRU理解不難，就是維護一個有固定大小的容器，核心就是get()和put()兩個操作。

我們先看一下LRU會有的兩個操作：

初始化：LRUCache(int capacity) ，以正整數(shù)作為容量 capacity 初始化 LRU 緩存。

查詢：get(int key),從自己的設(shè)計的數(shù)據(jù)結(jié)構(gòu)中查找是否有當(dāng)前key對應(yīng)的value，如果有那么返回對應(yīng)值并且要將key更新記錄為最近使用，如果沒有返回-1。

插入/更新：put(int key,int value)，可能是插入一個key-value，也可能是更新一個key-value，如果容器中已經(jīng)存才這個key-value那么只需要更新對應(yīng)value值，并且標(biāo)記成最新。如果容器不存在這個值，那么要考慮容器是否滿了，如果滿了要先刪除最久未使用的那對key-value。

這里的流程可以給大家舉個例子，例如

容量大小為2：

容量大小為2： 
[ "put",  "put", "get", "put","get", "put","get","get","get"] 
[ [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1],  [3], [4]] 

這個過程如下：

大家容易忽略的細(xì)節(jié)有：

• put()存在更新的操作,例如put(3,3),put(3,4)會更新key為3的操作。
• get()可能查詢不到，但是查詢到也會更新最久未使用的順序。
• 如果容器未使用滿，那么put可能更新可能插入，但是不會刪除;如果容器滿了并且put插入，就要考慮刪除最久未使用的key-value了。

對于上面的這么一個規(guī)則，我們該如何處理呢?

如果單單用一個List類似的列表，可以順序存儲鍵值對，在List前面的(0下標(biāo)為前)我們認(rèn)為它是比較久的，在List后我們認(rèn)為它是比較新的。我們考慮下各種操作可能會這樣設(shè)計：

如果來get操作：

遍歷List一個個比對，查看是否有該key的鍵值對，如果有直接返回對應(yīng)key的value，如果沒有那么返回-1.

如果來put操作：

遍歷List，如果有該key的鍵值對，那么果斷刪除這個key-value，最后在末尾統(tǒng)一插入該鍵值對。

如果沒有對應(yīng)的key并且List容器已經(jīng)到達(dá)最滿了，那么果斷刪除第一個位置的key-value。

用List可能需要兩個(一個存key一個存value)，或者一個存Node節(jié)點(key，value為屬性)的List，考慮下這個時間復(fù)雜度：

put操作：O(n)，get操作：O(n) 兩個操作都需要枚舉列表線性復(fù)雜度，效率屬實有點拉胯，肯定不行，這樣的代碼我就不寫了。

哈希初優(yōu)化

從上面的分析來看，我們已經(jīng)可以很自信的將LRU寫出來了，不過現(xiàn)在要考慮的是一個優(yōu)化的事情。

如果說我們將程序中引入哈希表，那么肯定會有一些優(yōu)化的。用哈希表存儲key-value，查詢是否存在的操作都能優(yōu)化為O(1),但是刪除或者插入或者更新位置的復(fù)雜度可能還是O(n),我們一起分析一下：

最久未使用一定是一個有序的序列來儲存，要么是順序表(數(shù)組)要么是鏈表，如果是數(shù)組實現(xiàn)的ArrayList存儲最久未使用這個序列。

如果是ArrayList進行刪除最久未使用(第一個)key-value，新的key被命中變成最新被使用(先刪除然后插入末尾)操作都是O(n)。

同理如果是LinkedList的一些操作大部分也是O(n)的，像刪除第一個元素這個是因為數(shù)據(jù)結(jié)構(gòu)原因O(1)。

你發(fā)現(xiàn)自己的優(yōu)化空間其實非常非常小，但是確實還是有進步的，只是被卡住不知道雙O(1)的操作究竟怎么優(yōu)化，這里面我把這個版本代碼放出來，大家可以參考一下(如果面試問到實在不會可以這么寫)

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); 
    } 
} 

哈希+雙鏈表

上面我們已經(jīng)知道用哈希能夠直接查到有木有這個元素，但是苦于刪除!用List都很費力。

更詳細(xì)的說，是苦于List的刪除操作，Map的刪除插入還是很高效的。

在上面這種情況，我們希望的就是能夠快速刪除List中任意一個元素，并且效率很高，如果借助哈希只能最多定位到，但是無法刪除啊!該怎么辦呢?

哈希+雙鏈表啊!

我們將key-val的數(shù)據(jù)存到一個Node類中，然后每個Node知道左右節(jié)點，在插入鏈表的時候直接存入Map中，這樣Map在查詢的時候可以直接返回該節(jié)點，雙鏈表知道左右節(jié)點可以直接將該節(jié)點在雙鏈表中刪除。

當(dāng)然，為了效率，這里實現(xiàn)的雙鏈表帶頭結(jié)點(頭指針指向一個空節(jié)點防止刪除等異常情況)和尾指針。

對于這個情況，你需要能夠手寫鏈表和雙鏈表啦，雙鏈表的增刪改查已經(jīng)寫過清清楚楚，小伙伴們不要擔(dān)心，這里我已經(jīng)整理好啦：

單鏈表：https://mp.weixin.qq.com/s/Cq98GmXt61-2wFj4WWezSg

雙鏈表：https://mp.weixin.qq.com/s/h6s7lXt5G3JdkBZTi01G3A

也就是你可以通過HashMap直接得到在雙鏈表中對應(yīng)的Node，然后根據(jù)前后節(jié)點關(guān)系刪除，期間要考慮的一些null、尾指針刪除等等特殊情況即可。

具體實現(xiàn)的代碼為：

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;// 頭節(jié)點 
        private Node tail;// 尾節(jié)點 
        private int length; 
        public DoubleList() { 
            head = new Node(-1,-1); 
            tail = head; 
            length = 0; 
        } 
        void add(Node teamNode)// 默認(rèn)尾節(jié)點插入 
        { 
            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)){// 已經(jīng)有這個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)復(fù)雜度的LRU寫出來啦!

尾聲

后來看了題解，才發(fā)現(xiàn)，Java中的LinkedHashMap也差不多是這種數(shù)據(jù)結(jié)構(gòu)!幾行解決，但是一般面試官可能不會認(rèn)同，還是會希望大家能夠手寫一個雙鏈表的。

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,其他的頁面置換算法無論筆試還是面試也是非常高頻啊，大家有空自己梳理一下哦。

除了算法水平真的很強的，不然大部分人其實不可能當(dāng)場想到一些比較巧妙的方法，所以面對筆試最好的訣竅還是多刷力扣。