下面是2020年9月16日面試遇到的一道真實(shí)面試題。

題目

截圖自LeetCode.146LRU緩存機(jī)制

解析

LRU(Least Recently Used)最近最少使用。在O(1)時(shí)間復(fù)雜度完成獲取和寫入數(shù)據(jù)兩個(gè)操作。

• 獲取數(shù)據(jù)：定位到數(shù)據(jù)
• 寫入數(shù)據(jù)：獲取數(shù)據(jù)并且更新悔据；或者如果仍有緩存直接寫入；如果緩存不夠需要清理原有的最近最少使用的數(shù)據(jù)后，寫入新數(shù)據(jù)奶浦。

上面兩個(gè)數(shù)據(jù)操作，O(1)時(shí)間復(fù)雜度查找到數(shù)據(jù)可以使用map數(shù)據(jù)結(jié)構(gòu)添谊，除此之外還有可能會(huì)清理原有的最近最少使用的數(shù)據(jù)财喳，這樣在數(shù)據(jù)保存的基礎(chǔ)上還需要記錄數(shù)據(jù)訪問的先后順序，這個(gè)順序可以使用鏈表實(shí)現(xiàn)斩狱。那么耳高，我們定義的數(shù)據(jù)結(jié)構(gòu)就應(yīng)該兼有map和list兩種屬性。map可以直接復(fù)用JDK中的HashMap所踊，然后在這個(gè)基礎(chǔ)上泌枪，讓HashMap中節(jié)點(diǎn)具有雙向鏈表的屬性，鏈表中節(jié)點(diǎn)按照訪問時(shí)間早晚的順序排列(表頭數(shù)據(jù)是最近訪問的秕岛，表尾數(shù)據(jù)是最近最少使用的)碌燕。
在內(nèi)存中數(shù)據(jù)存儲(chǔ)應(yīng)該如下圖所示：

內(nèi)存中數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)

public class LRUNode{
    int key;
    int value;
    LRUNode prev;
    LRUNode next;

    public LRUNode(){}

    public LRUNode(int key, int value){
        this.key = key;
        this.value = value;
    }
}

代碼

兩個(gè)操作邏輯：

• get操作：如果key不存在慈鸠，返回-1；如果存在返回value灌具，并且將這個(gè)key的LRUNode移動(dòng)到鏈表的頭部(moveToHead()函數(shù))青团。
• put操作：如果key存在，更新value咖楣，將LRUNode移動(dòng)鏈表的頭部(moveToHead()函數(shù))督笆；如果key不存在，判斷當(dāng)前緩存是否已滿诱贿。如果緩存未滿娃肿，直接map中放入新數(shù)據(jù)，并且新數(shù)據(jù)要連接到鏈表的頭部(addToHead()函數(shù))；如果緩存已滿料扰，刪除鏈表的尾部節(jié)點(diǎn)(最近最少使用的)(removeTailNode()函數(shù))锨阿，放入新數(shù)據(jù)并且連接到鏈表的頭部(addToHead()函數(shù))。

public class LRUCache {
    //緩存容量
    private int capacity;
    //雙向鏈表的頭尾指針
    private LRUNode head, tail;
    //JDK的map作為存儲(chǔ)
    private Map<Integer, LRUNode> cache;
    //緩存中當(dāng)前實(shí)際的數(shù)據(jù)量
    private int size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        cache = new HashMap<>();
        //定義頭指針
        head = tail = new LRUNode();
    }

    //get操作
    public int get(int key) {
        LRUNode node = cache.get(key);
        //如果key不存在记罚，返回-1
        if (null == node){
            return -1;
        }
        //如果存在返回value墅诡，并且將這個(gè)key的LRUNode移動(dòng)鏈表的頭部
        moveToHead(node);
        return node.value;
    }

    //put操作
    public void put(int key, int value) {
        LRUNode node = cache.get(key);
        //如果key存在
        if (null != node){
            //更新value
            node.value = value;
            //將LRUNode移動(dòng)到鏈表的頭部
            moveToHead(node);
            return;
        }
        //如果key不存在
        //緩存未滿
        if (size < capacity){
            size++;
        } else {//緩存已滿，刪除鏈表的尾部節(jié)點(diǎn)
            removeTailNode();
        }
        LRUNode newNode = new LRUNode(key, value);
        //放入新數(shù)據(jù)
        cache.put(key, newNode);
        //新數(shù)據(jù)要連接到鏈表的頭部
        addToHead(newNode);
    }

    //刪除鏈表的尾部節(jié)點(diǎn)
    private void removeTailNode(){
        if (head == tail){
            return;
        }
        int key = tail.key;
        tail = tail.prev;
        tail.next = null;
        cache.remove(key);
    }

    //新數(shù)據(jù)連接到鏈表的頭部
    private void addToHead(LRUNode node){
        if (head == tail){
            head.next = node;
            node.prev = head;
            tail = node;
            return;
        }
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }

    //移動(dòng)節(jié)點(diǎn)到鏈表的頭部
    private void moveToHead(LRUNode node){
        if (node.prev == head){
            return;
        }
        LRUNode prev = node.prev;
        if (node == tail){
            prev.next = null;
            tail = prev;
        } else {
            prev.next = node.next;
            node.next.prev = prev;
        }
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }
}