背景
在我們這個日益追求高效的世界，我們對任何事情的等待都顯得十分的浮躁，網頁頁面重新整理不出來，好煩，電腦開啟執行程式慢，又是好煩!那怎麼辦，技術的產生不就是我們所服務麼，今天我們就聊一聊快取這個技術，並使用我們熟知的資料結構--用連結串列實現LRU快取淘汰演算法。
在學習如何使用連結串列實現LRU快取淘汰演算法前，我們先提出幾個問題，大家好好思考下，問題如下：
什麼是快取，快取的作用?快取的淘汰策略有哪些?如何使用連結串列實現LRU快取淘汰演算法，有什麼特點，如何最佳化?好了，我們帶著上面的問題來學進行下面的學習。
1、什麼是快取，快取的作用是什麼?快取可以簡單地理解為儲存資料的一個副本，以便於後續能夠快速地進行訪問。以計算機的使用場景為例，當cpu要訪問記憶體中的一條資料時，它會先在快取裡查詢，如果能夠找到則直接使用，如果沒找到，則需要去記憶體裡查詢;
同樣的，在資料庫的訪問場景中，當專案系統需要查詢資料庫中的某條資料時，可以先讓請求查詢快取，如果命中，就直接返回快取的結果，如果沒有命中，就查詢資料庫， 並將查詢結果放入快取，下次請求時查詢快取命中，直接返回結果，就不用再次查詢資料庫。
透過以上兩個例子，我們發現無論在哪種場景下，都存在這樣一個順序：先快取，後記憶體;先快取，後資料庫。但是快取的存在也佔用了一部分記憶體空間，所以快取是典型的以空間換時間，犧牲資料的實時性，卻滿足計算機執行的高效性。
仔細想一下，我們日常開發中遇到快取的例子還挺多的。
作業系統的快取減少與磁碟的互動
資料庫快取減少對資料庫的查詢
Web伺服器快取減少對應用伺服器的請求
客戶瀏覽器的快取減少對網站的訪問
2、快取有哪些淘汰策略?快取的本質是以空間換時間，那麼快取的容量大小肯定是有限的，當快取被佔滿時，快取中的那些資料應該被清理出去，那些資料應該被保留呢?這就需要快取的淘汰策略來決定。
事實上，常用的快取的淘汰策略有三種：先進先出演算法(First in First out FIFO);淘汰一定時期內被訪問次數最少的頁面(Least Frequently Used LFU);淘汰最長時間未被使用的頁面(Least Recently Used LRU)
這些演算法在不同層次的快取上執行時具有不同的效率，需要結合具體的場景來選擇。
2.1 FIFO演算法FIFO演算法即先進先出演算法，常採用佇列實現。在快取中，它的設計原則是：如果一個數據最先進入快取中，則應該最早淘汰掉。
FIFO演算法
新訪問的資料插入FIFO佇列的尾部，佇列中資料由隊到隊頭按順序順序移動
2.2 LRU演算法LRU演算法是根據對資料的歷史訪問次數來進行淘汰資料的，通常使用連結串列來實現。在快取中，它的設計原則是：如果資料最近被訪問過，那麼將來它被訪問的機率也很高。
LRU演算法
新加入的資料插入到連結串列的頭部每當快取命中時(即快取資料被訪問)，則將資料移到連結串列頭部當來連結串列已滿的時候，將連結串列尾部的資料丟棄2.3 LFU演算法LFU演算法是根據資料的歷史訪問頻率來淘汰資料，因此，LFU演算法中的每個資料塊都有一個引用計數，所有資料塊按照引用計數排序，具有相同引用計數的資料塊則按照時間排序。在快取中，它的設計原則是：如果資料被訪問多次，那麼將來它的訪問頻率也會更高。
LFU演算法
新加入資料插入到佇列尾部(引用計數為1;佇列中的資料被訪問後，引用計數增加，佇列重新排序;當需要淘汰資料時，將已經排序的列表最後的資料塊刪除。3、如何使用連結串列實現快取淘汰，有什麼特點，如何最佳化?在上面的文章中我們理解了快取的概念及淘汰策略，其中LRU演算法是筆試/面試中考察比較頻繁的，我秋招的時候，很多公司都讓我手寫了這個演算法，為了避免大家採坑，下面，我們就手寫一個LRU快取淘汰演算法。
我們都知道連結串列的形式不止一種，我們應該選擇哪一種呢?
思考三分鐘........
好了，公佈答案!
事實上，連結串列按照不同的連線結構可以劃分為單鏈表、迴圈連結串列和雙向連結串列。
單鏈表每個節點只包含一個指標，即後繼指標。單鏈表有兩個特殊的節點，即首節點和尾節點，用首節點地址表示整條連結串列，尾節點的後繼指標指向空地址null。效能特點：插入和刪除節點的時間複雜度為O(1)，查詢的時間複雜度為O(n)。迴圈連結串列除了尾節點的後繼指標指向首節點的地址外均與單鏈表一致。適用於儲存有迴圈特點的資料，比如約瑟夫問題。雙向連結串列節點除了儲存資料外，還有兩個指標分別指向前一個節點地址(前驅指標prev)和下一個節點地址(後繼指標next)首節點的前驅指標prev和尾節點的後繼指標均指向空地址。雙向連結串列相較於單鏈表的一大優勢在於：找到前驅節點的時間複雜度為O(1)，而單鏈表只能從頭節點慢慢往下找，所以仍然是O(n).而且，對於插入和刪除也是有最佳化的。
演算法思路維護一個雙向連結串列，儲存所有快取的值，並且最老的值放在連結串列最後面。
3.1 LRU快取淘汰演算法極客時間王爭的《資料結構與演算法之美》給出了一個使用有序單鏈表實現LRU快取淘汰演算法，程式碼如下：
public class LRUBaseLinkedList<T> { /** * 預設連結串列容量 */ private final static Integer DEFAULT_CAPACITY = 10; /** * 頭結點 */ private SNode<T> headNode; /** * 連結串列長度 */ private Integer length; /** * 連結串列容量 */ private Integer capacity; public LRUBaseLinkedList() { this.headNode = new SNode<>(); this.capacity = DEFAULT_CAPACITY; this.length = 0; } public LRUBaseLinkedList(Integer capacity) { this.headNode = new SNode<>(); this.capacity = capacity; this.length = 0; } public void add(T data) { SNode preNode = findPreNode(data); // 連結串列中存在，刪除原資料，再插入到連結串列的頭部 if (preNode != null) { deleteElemOptim(preNode); intsertElemAtBegin(data); } else { if (length >= this.capacity) { //刪除尾結點 deleteElemAtEnd(); } intsertElemAtBegin(data); } } /** * 刪除preNode結點下一個元素 * * @param preNode */ private void deleteElemOptim(SNode preNode) { SNode temp = preNode.getNext(); preNode.setNext(temp.getNext()); temp = null; length--; } /** * 連結串列頭部插入節點 * * @param data */ private void intsertElemAtBegin(T data) { SNode next = headNode.getNext(); headNode.setNext(new SNode(data, next)); length++; } /** * 獲取查詢到元素的前一個結點 * * @param data * @return */ private SNode findPreNode(T data) { SNode node = headNode; while (node.getNext() != null) { if (data.equals(node.getNext().getElement())) { return node; } node = node.getNext(); } return null; } /** * 刪除尾結點 */ private void deleteElemAtEnd() { SNode ptr = headNode; // 空連結串列直接返回 if (ptr.getNext() == null) { return; } // 倒數第二個結點 while (ptr.getNext().getNext() != null) { ptr = ptr.getNext(); } SNode tmp = ptr.getNext(); ptr.setNext(null); tmp = null; length--; } private void printAll() { SNode node = headNode.getNext(); while (node != null) { System.out.print(node.getElement() + ","); node = node.getNext(); } System.out.println(); } public class SNode<T> { private T element; private SNode next; public SNode(T element) { this.element = element; } public SNode(T element, SNode next) { this.element = element; this.next = next; } public SNode() { this.next = null; } public T getElement() { return element; } public void setElement(T element) { this.element = element; } public SNode getNext() { return next; } public void setNext(SNode next) { this.next = next; } } public static void main(String[] args) { LRUBaseLinkedList list = new LRUBaseLinkedList(); Scanner sc = new Scanner(System.in); while (true) { list.add(sc.nextInt()); list.printAll(); } } } 這段程式碼不管快取有沒有滿，都需要遍歷一遍連結串列，所以這種基於連結串列的實現思路，快取訪問的時間複雜度為 O(n)。
3.2使用雜湊表最佳化LRU事實上，這個思路還可以繼續最佳化，我們可以把單鏈表換成雙向連結串列，並引入散列表。
雙向連結串列支援查詢前驅，保證操作的時間複雜度為O(1)引入散列表記錄每個資料的位置，將快取訪問的時間複雜度降到O(1)雜湊表查詢較快，但是資料無固定的順序;連結串列倒是有順序之分。插入、刪除較快，但是查詢較慢。將它們結合，就可以形成一種新的資料結構--雜湊連結串列(LinkedHashMap)
雜湊表+雙向連結串列
力扣上146題-LRU快取機制剛好可以拿來練手，題圖如下：
題目：運用你所掌握的資料結構，設計和實現一個 LRU (最近最少使用) 快取機制 。
實現 LRUCache 類：LRUCache(int capacity) 以正整數作為容量 capacity 初始化 LRU 快取
int get(int key) 如果關鍵字 key 存在於快取中，則返回關鍵字的值，否則返回 -1 。
思路：我們的思路就是雜湊表+雙向連結串列
雜湊表用於滿足題目時間複雜度O(1)的要求，雙向連結串列用於儲存順序雜湊表鍵值型別：雙向連結串列的節點中除了value外還需要包含key，因為在刪除最久未使用的資料時，需要透過連結串列來定位hashmap中應當刪除的鍵值對一些操作：雙向連結串列中，在後面的節點表示被最近訪問新加入的節點放在連結串列末尾，addNodeToLast(node)若容量達到上限，去除最久未使用的資料，removeNode(head.next)若資料新被訪問過，比如被get了或被put了新值，把該節點挪到連結串列末尾，moveNodeToLast(node)為了操作的方便，在雙向連結串列頭和尾分別定義一個head和tail節點。程式碼class LRUCache { private int capacity; private HashMap<Integer, ListNode> hashmap; private ListNode head; private ListNode tail; private class ListNode{ int key; int val; ListNode prev; ListNode next; public ListNode(){ } public ListNode(int key, int val){ this.key = key; this.val = val; } } public LRUCache(int capacity) { this.capacity = capacity; hashmap = new HashMap<>(); head = new ListNode(); tail = new ListNode(); head.next = tail; tail.prev = head; } private void removeNode(ListNode node){ node.prev.next = node.next; node.next.prev = node.prev; } private void addNodeToLast(ListNode node){ node.prev = tail.prev; node.prev.next = node; node.next = tail; tail.prev= node; } private void moveNodeToLast(ListNode node){ removeNode(node); addNodeToLast(node); } public int get(int key) { if(hashmap.containsKey(key)){ ListNode node = hashmap.get(key); moveNodeToLast(node); return node.val; }else{ return -1; } } public void put(int key, int value) { if(hashmap.containsKey(key)){ ListNode node = hashmap.get(key); node.val = value; moveNodeToLast(node); return; } if(hashmap.size() == capacity){ hashmap.remove(head.next.key); removeNode(head.next); } ListNode node = new ListNode(key, value); hashmap.put(key, node); addNodeToLast(node); } } 巨人的肩膀：
[1]資料結構與演算法之美-王爭
[2]力扣-LRU快取機制(146題)