之前暑期實習(xí)面試的時候也被問到了，需要我們說一下思路，然后實現(xiàn)。如果讓我們簡單來實現(xiàn)一下的話，有很多的方式。比如Java就有自帶的LinkedHashMap來實現(xiàn)，但是面試官既然問了那便是不想讓你直接調(diào)用接口了。我們一般都是用哈希+雙向鏈表來實現(xiàn)。下面給出三種實現(xiàn)方式，參考leetcode題解，leetcode上面也有類似的題。

它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 。

獲取數(shù)據(jù) get(key) - 如果關(guān)鍵字 (key) 存在于緩存中，則獲取關(guān)鍵字的值（總是正數(shù)），否則返回 -1。
寫入數(shù)據(jù) put(key, value) - 如果關(guān)鍵字已經(jīng)存在，則變更其數(shù)據(jù)值；如果關(guān)鍵字不存在，則插入該組「關(guān)鍵字/值」。當(dāng)緩存容量達(dá)到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

LinkedHashMap

最容易實現(xiàn)的，但也是面試官應(yīng)該最不想看到的。畢竟這樣完全考察不到你的coding能力。

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int initialCapacity;
    public LRUCache(int initialCapacity) {
        //true表示按照訪問順序排序
        super(initialCapacity, 0.75f, true);
        this.initialCapacity = initialCapacity;
    }
    
        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<K, V> eldest) {
        if (size() > initialCapacity) {
            return true;
        }
        return false;
    }
}

哈希+隊列

用哈希來存取值，以對首是最久未使用的，對尾是最近使用來實現(xiàn)

class LRUCache {

    Map<Integer,Integer> map;
    //隊列，對首是越久未使用的，對尾是最近使用的
    Queue<Integer> queue;
    int cap;


    public LRUCache(int capacity) {
        this.map = new HashMap<>();
        this.queue = new LinkedList<>();
        this.cap = capacity;
    }
    
    public int get(int key) {
    //如果key存在，移除重新添加就能靠近隊尾
        if(queue.contains(key)){
            queue.remove(key);
            queue.add(key);
            return map.get(key);
        }else{
            return -1;
        }

    }
    
    public void put(int key, int value) {
        //如果使用的是已經(jīng)存在的key
        if(queue.contains(key)){
            queue.remove(key);
            queue.add(key);
            map.put(key,value);
            //如果緩存已經(jīng)滿了，刪除最久未使用的
        }else if(cap == 0){
            map.remove(queue.poll());
            queue.add(key);
            map.put(key,value);
        }else{
            //有空閑的位置，第一次添加，直接添加進(jìn)去
            queue.add(key);
            map.put(key,value);
            cap--;
        }

    }

}

哈希+手動實現(xiàn)雙向鏈表

面試官有時候應(yīng)該更希望看到我們手動來實現(xiàn)雙向鏈表，展示coding能力。這里以leetcode參考答案為例

class LRUCache {

    class Node{
        int key;
        int value;
        Node prev;
        Node next;
        public Node(){}
        public Node(int key,int value){this.key = key; this.value = value;}
    }

    private HashMap<Integer,Node> cache = new HashMap<>();
    private int size;
    private int capacity;
    private Node head,tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用偽頭部和偽尾部結(jié)點
        head = new Node();
        tail = new Node();
        //構(gòu)建雙向鏈表
        head.next = tail;
        tail.next = head;
    }
    
    public int get(int key) {
        Node node = cache.get(key);
        if(node == null){
            return -1;
        }
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        Node node = cache.get(key);
        if(node == null){
            //如果key不存在，創(chuàng)建一個新的結(jié)點
            Node temp = new Node(key,value);
            cache.put(key,temp);
            //將最新存進(jìn)來的結(jié)點移動至頭部
            addToHead(temp);
            ++size;
            //如果長度超出了我們的容量，將尾部的結(jié)點刪除
            if(size > capacity){
                Node tail = removeTail();
                cache.remove(tail.key);
                --size;
            }
        }else{
            //如果存在key，將原來的值覆蓋掉
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(Node node){
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node){
        removeNode(node);
        addToHead(node);
    }

    private Node removeTail(){
        Node res = tail.prev;
        removeNode(res);
        return res;
    }
}