LRUCache 全稱為 Least Recently Used Cache ，用Java實現(xiàn)的話，可以很簡單地用LinkedHashMap來實現(xiàn)。但如果面試過程中碰到面試官出這道題，大概率是希望你不借助過多的工具類，而是把一個LRUCache內(nèi)部的get、put等方法給寫一遍，以證實你是真的理解了。。

首先明確我們需要用到的數(shù)據(jù)結構：

1、hash表

為保證時間復雜度在O(1)，hash表是必不可少的，它的作用就是充當緩存的容器；

2、雙向鏈表

雙向鏈表的每個節(jié)點都具備指向前驅(qū)節(jié)點和指向后驅(qū)節(jié)點的兩個指針，其雙向查詢的特點使得我們能夠讓一個（新/舊）節(jié)點以O(1)的時間復雜度快速入到鏈表的頭部或尾部。而如果只是單向的鏈表，我們無法保證O(1)的時間復雜度的（比如刪除隊尾節(jié)點的操作，即使一開始定義了隊尾節(jié)點，但是因為其單向的特點，刪除時還是需要從頭節(jié)點遍歷到隊尾的前一個節(jié)點，讓其next指針指向空，才能將隊尾刪除）。

接下來一起看下代碼中的邏輯：

• 構造器

1、我們將構造器傳進來的capacity參數(shù)作為緩存允許的最大容量，同時初始化當前緩存的數(shù)量size為0；

2、定義頭部節(jié)點head和尾部節(jié)點tail兩個dummyNode，這是鏈表類題目的常用技巧，為的是避免處理頭節(jié)點為空的邊界問題，同時要初始化好head和tail節(jié)點互相指向的關聯(lián)關系；

• get方法

根據(jù)key查詢是否存在于緩存之中，不存在則直接返回null；如果存在，我們就要維護一下鏈表，將該節(jié)點移動到鏈表頭部（同理，用尾部來作為最新節(jié)點的存放位置也是可以的），表示該節(jié)點最近被訪問到了。

• put方法

判斷該key是否存在于緩存之中

1、如果不存在

• 首先先新建一個節(jié)點放入hash表中，同時將這個節(jié)點添加到鏈表的頭部，表示該節(jié)點最近被訪問到了；
• 放入緩存后，我們要判斷加上這個節(jié)點后，緩存的容量是否超過設定的最大容量，如果是，就要刪掉鏈表中的尾部節(jié)點，并根據(jù)尾部節(jié)點的key，將其從hash表中remove掉

2、如果存在

• 移動該節(jié)點到鏈表頭部，并更新節(jié)點中的value即可。

除此之外，對于鏈表節(jié)點的添加、移動、刪除等操作，我們最好將方法單獨抽離開來，這樣做好處有兩個：

一是可以對抽離開的方法進行復用；

二是在寫get、put方法時，可以專注于緩存整體的維護邏輯，而不用關注到鏈表這一層數(shù)據(jù)結構，降低懵逼的風險。。

代碼如下

import java.util.HashMap;
import java.util.Map;

public class LRUCache {

    Map<Integer, DLinkedNode> cache ;
    int size;
    int capacity;
    DLinkedNode head, tail ;

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(3);
        lruCache.put(1, 2);
        lruCache.put(2, 2);
        lruCache.put(3, 2);
        lruCache.get(1);
        lruCache.put(4, 2);
        System.out.println(lruCache.cache.keySet());// [1, 3, 4]
    }

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        cache = new HashMap<>();
        // 維護兩個dummy node（始終在頭尾）
        this.head = new DLinkedNode();
        this.tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.v;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            node = new DLinkedNode(key, value);
            cache.put(key, node);
            // 移動到頭部
            addToHead(node);
            if (++size > capacity) {
                // 丟棄tail
                DLinkedNode tail = removeTail();
                cache.remove(tail.k);
                --size;
            }
        } else {
            // 替換并放到頭部
            node.v = value;
            moveToHead(node);
        }
    }

    /**
     * 將節(jié)點移動到頭部
     */
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    /**
     * 刪除節(jié)點
     */
    private void removeNode(DLinkedNode node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }

    /**
     * 添加到頭部
     */
    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    /**
     * 刪除尾部節(jié)點
     */
    private DLinkedNode removeTail() {
        DLinkedNode node = tail.prev;
        removeNode(node);
        return node;
    }

    /**
     * 雙向鏈表
     */
    class DLinkedNode {
        DLinkedNode prev;
        DLinkedNode next;
        // key作用體現(xiàn)在干掉tail的時候可以通過node的key去remove哈希表中的元素
        int k;
        int v;

        public DLinkedNode() {
        }

        public DLinkedNode(int k, int v) {
            this.k = k;
            this.v = v;
        }

    }
}