一次倒在 LRU 上的經(jīng)歷
本文轉(zhuǎn)載自微信公眾號(hào)「bigsai」，作者大賽 。轉(zhuǎn)載本文請(qǐng)聯(lián)系bigsai公眾號(hào)。
前言
大家好，我是bigsai，好久不見，甚是想念!
最近有個(gè)小伙伴跟我訴苦，說他沒面到LRU，他說他很久前知道有被問過LRU的但是心想自己應(yīng)該不會(huì)遇到，所以暫時(shí)就沒準(zhǔn)備。
奈何不巧，這還就真的考到了!他此刻的心情，可以用一張圖來證明：
他說他最終踉踉蹌蹌的寫了一個(gè)效率不是很高的LRU，面試官看著不是很滿意要求寫一個(gè)O(1)復(fù)雜度的LRU……后來果真GG了，后來發(fā)現(xiàn)這是力扣146的一道原題。
防止日后再碰到這個(gè)坑，今天和大家一起把這個(gè)坑踩了，這道題我自身剛開始也是用較為普通的方法，但是好的方法雖然不是很難但是想了真的很久才想到，雖然花了太多時(shí)間不太值，總算是自己想出來了，將這個(gè)過程給大家分享一下(只從算法的角度，不從操作系統(tǒng)的角度)。
理解LRU
設(shè)計(jì)一個(gè)LRU，你得知道什么是LRU吧?
LRU，英文全稱為L(zhǎng)east Recently Used，翻譯過來就是最近最久未使用算法，是一種常用的頁面置換算法。
說起頁面置換算法，這就是跟OS關(guān)系比較大的了，我們都知道內(nèi)存的速度比較快，但是內(nèi)存的容量是非常有限的，不可能給所有頁面裝到內(nèi)存中，所以就需要一個(gè)策略將常用的頁面預(yù)放到內(nèi)存中。
但是吧，誰也不知道進(jìn)程下次會(huì)訪問哪個(gè)內(nèi)存，并不能很有效的知道(我們?cè)诋?dāng)前并沒有預(yù)測(cè)未來的功能)，所以有些頁面置換算法只是理想化但是沒法真實(shí)實(shí)現(xiàn)的(沒錯(cuò)就是最佳置換算法(Optimal)),然后常見必回的算法就是FIFO(先進(jìn)先出)和LRU(最近最久未使用)。
LRU理解不難，就是維護(hù)一個(gè)有固定大小的容器，核心就是get()和put()兩個(gè)操作。
我們先看一下LRU會(huì)有的兩個(gè)操作：
初始化：LRUCache(int capacity) ，以正整數(shù)作為容量 capacity 初始化 LRU 緩存。
查詢：get(int key),從自己的設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)中查找是否有當(dāng)前key對(duì)應(yīng)的value，如果有那么返回對(duì)應(yīng)值并且要將key更新記錄為最近使用，如果沒有返回-1。
插入/更新：put(int key,int value)，可能是插入一個(gè)key-value，也可能是更新一個(gè)key-value，如果容器中已經(jīng)存才這個(gè)key-value那么只需要更新對(duì)應(yīng)value值，并且標(biāo)記成最新。如果容器不存在這個(gè)值，那么要考慮容器是否滿了，如果滿了要先刪除最久未使用的那對(duì)key-value。
這里的流程可以給大家舉個(gè)例子，例如
容量大小為2：
- 容量大小為2：
- [ "put", "put", "get", "put","get", "put","get","get","get"]
- [ [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
這個(gè)過程如下：
大家容易忽略的細(xì)節(jié)有：
- put()存在更新的操作,例如put(3,3),put(3,4)會(huì)更新key為3的操作。
- get()可能查詢不到，但是查詢到也會(huì)更新最久未使用的順序。
- 如果容器未使用滿，那么put可能更新可能插入，但是不會(huì)刪除;如果容器滿了并且put插入，就要考慮刪除最久未使用的key-value了。
對(duì)于上面的這么一個(gè)規(guī)則，我們?cè)撊绾翁幚砟?
如果單單用一個(gè)List類似的列表，可以順序存儲(chǔ)鍵值對(duì)，在List前面的(0下標(biāo)為前)我們認(rèn)為它是比較久的，在List后我們認(rèn)為它是比較新的。我們考慮下各種操作可能會(huì)這樣設(shè)計(jì)：
如果來get操作：
遍歷List一個(gè)個(gè)比對(duì)，查看是否有該key的鍵值對(duì)，如果有直接返回對(duì)應(yīng)key的value，如果沒有那么返回-1.
如果來put操作：
遍歷List，如果有該key的鍵值對(duì)，那么果斷刪除這個(gè)key-value，最后在末尾統(tǒng)一插入該鍵值對(duì)。
如果沒有對(duì)應(yīng)的key并且List容器已經(jīng)到達(dá)最滿了，那么果斷刪除第一個(gè)位置的key-value。
用List可能需要兩個(gè)(一個(gè)存key一個(gè)存value)，或者一個(gè)存Node節(jié)點(diǎn)(key，value為屬性)的List，考慮下這個(gè)時(shí)間復(fù)雜度：
put操作：O(n)，get操作：O(n) 兩個(gè)操作都需要枚舉列表線性復(fù)雜度，效率屬實(shí)有點(diǎn)拉胯，肯定不行，這樣的代碼我就不寫了。
哈希初優(yōu)化
從上面的分析來看，我們已經(jīng)可以很自信的將LRU寫出來了，不過現(xiàn)在要考慮的是一個(gè)優(yōu)化的事情。
如果說我們將程序中引入哈希表，那么肯定會(huì)有一些優(yōu)化的。用哈希表存儲(chǔ)key-value，查詢是否存在的操作都能優(yōu)化為O(1),但是刪除或者插入或者更新位置的復(fù)雜度可能還是O(n),我們一起分析一下：
最久未使用一定是一個(gè)有序的序列來儲(chǔ)存，要么是順序表(數(shù)組)要么是鏈表，如果是數(shù)組實(shí)現(xiàn)的ArrayList存儲(chǔ)最久未使用這個(gè)序列。
如果是ArrayList進(jìn)行刪除最久未使用(第一個(gè))key-value，新的key被命中變成最新被使用(先刪除然后插入末尾)操作都是O(n)。
同理如果是LinkedList的一些操作大部分也是O(n)的，像刪除第一個(gè)元素這個(gè)是因?yàn)閿?shù)據(jù)結(jié)構(gòu)原因O(1)。
你發(fā)現(xiàn)自己的優(yōu)化空間其實(shí)非常非常小，但是確實(shí)還是有進(jìn)步的，只是被卡住不知道雙O(1)的操作究竟怎么優(yōu)化，這里面我把這個(gè)版本代碼放出來，大家可以參考一下(如果面試問到實(shí)在不會(huì)可以這么寫)
- 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 {//如果不存在 要插入到最后，但是如果容量滿了需要?jiǎng)h除第一個(gè)(最久)
- 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)知道用哈希能夠直接查到有木有這個(gè)元素，但是苦于刪除!用List都很費(fèi)力。
更詳細(xì)的說，是苦于List的刪除操作，Map的刪除插入還是很高效的。
在上面這種情況，我們希望的就是能夠快速刪除List中任意一個(gè)元素，并且效率很高，如果借助哈希只能最多定位到，但是無法刪除啊!該怎么辦呢?
哈希+雙鏈表啊!
我們將key-val的數(shù)據(jù)存到一個(gè)Node類中，然后每個(gè)Node知道左右節(jié)點(diǎn)，在插入鏈表的時(shí)候直接存入Map中，這樣Map在查詢的時(shí)候可以直接返回該節(jié)點(diǎn)，雙鏈表知道左右節(jié)點(diǎn)可以直接將該節(jié)點(diǎn)在雙鏈表中刪除。
當(dāng)然，為了效率，這里實(shí)現(xiàn)的雙鏈表帶頭結(jié)點(diǎn)(頭指針指向一個(gè)空節(jié)點(diǎn)防止刪除等異常情況)和尾指針。
對(duì)于這個(gè)情況，你需要能夠手寫鏈表和雙鏈表啦，雙鏈表的增刪改查已經(jīng)寫過清清楚楚，小伙伴們不要擔(dān)心，這里我已經(jīng)整理好啦：
單鏈表：https://mp.weixin.qq.com/s/Cq98GmXt61-2wFj4WWezSg
雙鏈表：https://mp.weixin.qq.com/s/h6s7lXt5G3JdkBZTi01G3A
也就是你可以通過HashMap直接得到在雙鏈表中對(duì)應(yīng)的Node，然后根據(jù)前后節(jié)點(diǎn)關(guān)系刪除，期間要考慮的一些null、尾指針刪除等等特殊情況即可。
具體實(shí)現(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é)點(diǎn)
- private Node tail;// 尾節(jié)點(diǎn)
- private int length;
- public DoubleList() {
- head = new Node(-1,-1);
- tail = head;
- length = 0;
- }
- void add(Node teamNode)// 默認(rèn)尾節(jié)點(diǎn)插入
- {
- tail.next = teamNode;
- teamNode.pre=tail;
- tail = teamNode;
- length++;
- }
- void deleteFirst(){
- if(head.next==null)
- return;
- if(head.next==tail)//如果刪除的那個(gè)剛好是tail 注意啦 tail指針前面移動(dòng)
- 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;//存儲(chǔ)順序
- 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)有這個(gè)key 不考慮長(zhǎng)短直接刪除然后更新
- Node deleteNode=map.get(key);
- doubleList.deleteNode(deleteNode);
- }
- else if(doubleList.length==maxSize){//不包含并且長(zhǎng)度小于
- Node first=doubleList.head.next;
- map.remove(first.key);
- doubleList.deleteFirst();
- }
- Node node=new Node(key,value);
- doubleList.add(node);
- map.put(key,node);
- }
- }
就這樣，一個(gè)get和put都是O(1)復(fù)雜度的LRU寫出來啦!
尾聲
后來看了題解，才發(fā)現(xiàn)，Java中的LinkedHashMap也差不多是這種數(shù)據(jù)結(jié)構(gòu)!幾行解決，但是一般面試官可能不會(huì)認(rèn)同，還是會(huì)希望大家能夠手寫一個(gè)雙鏈表的。
- 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;
- }
- }//這個(gè)來源官方題解 給大家分享一下
}//這個(gè)來源官方題解 給大家分享一下
哈希+雙鏈表雖然在未看題解的情況想出來，但是真的花了挺久才想到這個(gè)點(diǎn)，以前見得確實(shí)比較少，高效手寫LRU到今天算是真真正正的完全掌握啦!
不過除了LRU,其他的頁面置換算法無論筆試還是面試也是非常高頻啊，大家有空自己梳理一下哦。
除了算法水平真的很強(qiáng)的，不然大部分人其實(shí)不可能當(dāng)場(chǎng)想到一些比較巧妙的方法，所以面對(duì)筆試最好的訣竅還是多刷力扣。
