前言

• 相信有的伙伴在面試的過程中，或多或少的會被問到redis的內存淘汰策略，可能大部分人都知道都有哪些對應的策略，畢竟對于八股文的套路大家肯定早已銘記于心。但是當面試官問你如何實現或者讓你去寫一個對應策略的算法時，可能就頓時一臉蒙蔽了：不對啊，套路不是這樣的啊！！如果單純的讓你直接寫對應的算法還好，要是再更深入一點讓你說一下你的思考過程或者說如果讓你來設計你會怎么去做，這個可能就上升到了一個架構的思維（如果你打算面試架構死，不妨提前鍛煉一下這樣的思維），對于平時沒有這方面準備的伙伴來講，那無疑就是當頭一棒：與自己心儀的offer就要失之交臂了。
• 這篇文章我將從如何設計LRU Cache算法，跟大家一起來看一下整體的設計過程，包括我們應該如何去思考，如何去解決，提前鍛煉一下自己初步的架構設計能力。當然在這里只是淺談一下我的思考過程，為大家拋磚引玉，歡迎在留言區分享你的想法。目前博主個人博客已經搭建發布，后期相關文章也會發布在上面，大家有興趣可以去上面學習，點擊即可前往文青樂園

LRU Cache基本概述

LRU 是什么

• 基本概述
  LRU（Least Recently Used） ，即最近最少使用，它是一種緩存逐出策略 cache eviction policies。LRU 算法是假設最近最少使用的那些信息，將來被使用的概率也不大，所以在容量有限的情況下，就可以把這些不常用的信息清理掉。
• 使用場景
  比如有熱點新聞時，所有人都在搜索這個信息，那剛被一個人搜過的信息接下來被其他人搜索的概率也大，之前的新聞被搜索的概率就會小，所以我們把很久沒有用過的信息清理掉，也就是把 Least Recently Used 的信息清理掉。

我們舉個例子，假設內存容量為 5，現在有 1-5 五個數，存儲順序如下：

數據從左到右邊其使用最新程度逐漸增加，比如1就是最早使用的數據，5就是最近使用的數據，我們現在想加入一個新的數6，可是容量已經滿了，所以需要清理其中的某一個，那按照什么規則清理呢？目前主要有如下緩存逐出策略：

• LFU (Least Frequently Used) ：這個是計算每個信息的訪問次數，清除掉訪問次數最少的那個；如果訪問次數一樣，就清除掉好久沒用過的那個。這個算法其實很高效，但是耗資源，所以一般不用。
• LRU (Least Recently Used) ：這是目前最常用了，把很長時間沒有用過的清除掉，那它的隱含假設就是，認為最近用到的信息以后用到的概率會更大。

那我們這個例子中就是把最老的 1 清理掉，變成：

如此不斷地進行迭代。

Cache 是什么

• 基本概述
  • 簡單理解就是：把一些可以重復使用的信息存起來，以便之后需要時可以快速拿到。至于它存在哪里就不一定了，最常見的是存在內存里，也就是 memory cache，但也可以不存在內存里。
• 使用場景
  • Spring 中有 @Cacheable 等支持 Cache 的一系列注解，使用它大大減少了 call 某服務器的次數，解決了一個性能上的問題。
  • 在進行數據庫查詢的時候，不想每次請求都去 call 數據庫，那我們就在內存里存一些常用的數據，來提高訪問性能。這種設計思想其實是遵循了著名的“二八定律”。在讀寫數據庫時，每次的 I/O 過程消耗很大，但其實 80% 的 request 都是在用那 20% 的數據，所以把這 20% 的數據放在內存里，就能夠極大的提高整體的效率。

總之，Cache 的目的是存一些可以復用的信息，方便將來的請求快速獲得。

那我們知道了 LRU，了解了 Cache，合起來就是 LRU Cache 了：當 Cache 儲存滿了的時候，使用 LRU 算法把老數據清理出去。接下來我們看看具體的實現思路。

LRU Cache設計思路詳解

其實很多伙伴都知道設計這個算法需要使用 HashMap + Doubly Linked List，或者說用 Java 中現成的 LinkedHashMap，但是，你有思考過下面的問題么？

• 為什么是使用上面的數據結構？
• 你是怎么想到用這兩個數據結構的？

如果真的問到這個，面試的時候不講清楚這個，不說清楚思考過程，代碼寫對了也沒用。其實這個和在工作中的設計思路類似，沒有人會告訴我們要用什么數據結構，一般的思路是：

先想有哪些操作

然后根據這些操作，再去看哪些數據結構合適

定義數據結構內容

接下來我們就從上面的思路出發進行設計。

分析 Operations

對于這個 LRU Cache 需要有哪些操作呢？我們來分析一下：

首先最基本的操作就是能夠從里面讀信息，不然之后快速獲取是咋來的；

還得能加入新的信息，新的信息進來就是 most recently used 了；

在加新信息之前，還得看看有沒有空位，如果沒有空間了，得先把老的清理掉，那就需要能夠找到那個老的數據并且刪除它；

如果加入的新信息是緩存里已經有的，那意思就是 key 已經有了，要更新 value，那就只需要調整一下這條信息的 priority，將它從上一次被使用升級為最新使用。

找尋數據結構

第一個操作很明顯，我們需要一個能夠快速查找的數據結構，非 HashMap 莫屬，還不了解 HashMap 原理和設計規則的大家可以去百度查查，這里不做贅述。可是發現后面的操作 HashMap 就不頂用了。這里我們先來數一遍基本的數據結構：Array, LinkedList, Stack, Queue, Tree, BST, Heap, HashMap。在做這種數據結構的題目時，就這樣把所有的數據結構列出來，一個個來分析，有時候不是因為這個數據結構不行，而是因為其他的數據結構更好。我們做出如下的分析：

• Array, Stack, Queue ：這三種本質上都是 Array 實現的（當然 Stack, Queue 也可以用 LinkedList 來實現。。），一會插入新的，一會刪除老的，一會調整下順序，array 不是不能做，時間復雜度 O(n) 啊，不可行；
• BST ：同理，時間復雜度是 O(logn)；
• Heap： 即便可以，也是 O(logn)；
• LinkedList：有點可以哦，按照從老到新的順序，排排站，刪除、插入、移動，都可以是 O(1) 。但是刪除時我還需要一個 previous pointer 才能刪掉，所以我需要一個 Doubly LinkedList。
  

最后我們數據結構選定為HashMap + Double LinkedList。

定義數據結構的內容

選好了數據結構之后，還需要定義清楚每個數據結構具體存儲的是是什么，HashMap + Doubly LinkedList兩個數據結構是如何聯系的，這才是核心問題。我們先想個場景，在搜索引擎里，你輸入問題 Questions，谷歌給你返回答案 Answer。那我們就先假設這兩個數據結構存的都是 <Q, A>，現在我們的 HashMap 和 LinkedList 長這樣：

然后我們進行以下操作：

• 直接從 HashMap 里讀取 Answer 即可，O(1)，沒問題；
• 新加入一組 Q&A，兩個數據結構都得加，那先要判斷一下當前的緩存里有沒有這個 Q，那我們用 HashMap 判斷，如果沒有這個 Q，加進來，都沒問題；
• 如果已經有這個 Q，HashMap 這里要更新一下 Answer，然后我們還要把 LinkedList 的那個 node 移動到最后或者最前，因為它變成了最新被使用的了嘛。

可是，怎么找 LinkedList 的這個 node 呢？一個個遍歷去找并不是我們想要的，因為要 O(n) 的時間嘛，我們想用 O(1) 的時間操作。那也就是說這樣記錄是不行的，還需要記錄 LinkedList 中每個 ListNode 的位置，這就是設計的關鍵所在。怎么設計呢？自然是在 HashMap 里記錄 ListNode 的位置這個信息了，也就是存一下每個 ListNode 的 reference。想想其實也是，HashMap 里沒有必要記錄 Answer，Answer 只需要在 LinkedList 里記錄就可以了。之后我們更新、移動每個 node 時，它的 reference 也不需要變，所以 HashMap 也不用改動，動的只是 previous, next pointer。那再一想，其實 LinkedList 里也沒必要記錄 Question，反正 HashMap 里有。這兩個數據結構是相互配合來用的，不需要記錄一樣的信息。更新后的數據結構如下：

這樣，我們才分析出來用什么數據結構，每個數據結構里存的是什么，物理意義是什么。
那我們再用圖來總結一下：

畫圖的時候邊講邊寫，每一步都從 high level 到 detail 再到代碼，把代碼模塊化。

• 比如“Welcome”是要把這個新的信息加入到 HashMap 和 LinkedList 里，那我會用一個單獨的 add() method 來寫這塊內容，那在下面的代碼里我取名為 appendHead()，更精準；
• “踢走老的”這里我也是用一個單獨的 remove() method 來寫的。

有了上面的分析，接下里直接給出設計的代碼。

LRU Cache算法實現

class LRUCache {// HashMap: <key = Question, value = ListNode>// LinkedList: <Answer>public static class Node {int key;int val;Node next;Node prev;public Node(int key, int val) {this.key = key;this.val = val;}}Map<Integer, Node> map = new HashMap<>();private Node head;private Node tail;private int cap;public LRUCache(int capacity) {cap = capacity;}public int get(int key) {Node node = map.get(key);if(node == null) {return -1;} else {int res = node.val;remove(node);appendHead(node);return res;}}public void put(int key, int value) {// 先 check 有沒有這個 keyNode node = map.get(key);if(node != null) {node.val = value;// 把這個node放在最前面去remove(node);appendHead(node);} else {node = new Node(key, value);if(map.size() < cap) {appendHead(node);map.put(key, node);} else {// 踢走老的map.remove(tail.key);remove(tail);appendHead(node);map.put(key, node);}}}private void appendHead(Node node) {if(head == null) {head = tail = node;} else {node.next = head;head.prev = node;head = node;}}private void remove(Node node) {if(head == tail) {head = tail = null;} else {if(head == node) {head = head.next;node.next = null;} else if (tail == node) {tail = tail.prev;tail.next = null;node.prev = null;} else {node.prev.next = node.next;node.next.prev = node.prev;node.prev = null;node.next = null;}}}}/** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */

總結

以上是生活随笔為你收集整理的如何设计LRU Cache算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。