本題考察的LRU緩存機制,HashMap和鏈表

題目描述

運用你所掌握的數(shù)據(jù)結(jié)構(gòu)，設(shè)計和實現(xiàn)一個 LRU (最近最少使用) 緩存機制。它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 。

獲取數(shù)據(jù) get(key) - 如果密鑰 (key) 存在于緩存中，則獲取密鑰的值（總是正數(shù)），否則返回 -1。
寫入數(shù)據(jù) put(key, value) - 如果密鑰不存在，則寫入其數(shù)據(jù)值。當(dāng)緩存容量達到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最近最少使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

進階:
你是否可以在 O(1) 時間復(fù)雜度內(nèi)完成這兩種操作？

示例:

LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 該操作會使得密鑰 2 作廢
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 該操作會使得密鑰 1 作廢
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

題目思考

首先我們應(yīng)該了解LRU算法的原理。LRU算法總結(jié)來說就是：一個數(shù)據(jù)很久沒有訪問，那么這個數(shù)據(jù)在以后也很少訪問。對于這樣的很久沒有訪問的數(shù)據(jù)，如果緩存空間不足，就把那些很久沒有使用的數(shù)據(jù)清除。

那怎么樣實現(xiàn)這樣一種算法呢？我們可以為每一個數(shù)據(jù)標(biāo)記一個時間戳，標(biāo)記了最近一次使用的時間，然后不斷更新時間戳，緩存沒用空間的時候刪除距離現(xiàn)在最久的時間戳。這樣的方法可以用數(shù)組，鏈表來實現(xiàn)，時間復(fù)雜度一般是O(n)。

或者可以不用表示時間戳，我們僅根據(jù)數(shù)據(jù)的使用時間對數(shù)據(jù)進行排序，最近使用的排在前面，很久沒有使用的排在后面。刪除數(shù)據(jù)從后面開始刪除。在查找數(shù)據(jù)的時候可以使用HashMap。這樣，時間復(fù)雜度就可以簡化成O(1)。

說了這么多，我們把細節(jié)總結(jié)一下，說一下算法的具體實現(xiàn)。

1.首先我們應(yīng)該維護一個雙向鏈表，在這個鏈表中，我們應(yīng)該使鏈表中的數(shù)據(jù)這樣排列：越近使用的數(shù)據(jù)越排在前面，越久沒有使用的數(shù)據(jù)排在后面。此外，鏈表中的所有數(shù)據(jù)緩存在一個HashMap中。

2.我們插入一個數(shù)據(jù)的時候，首先查找HashMap中是否有這個數(shù)據(jù)？

2.1 如果沒有這個數(shù)據(jù)，我們要判斷現(xiàn)在HashMap中是否還有剩余空間？如果沒有剩余空間，需要將雙向鏈表中最后一個數(shù)據(jù)刪除（在HashMap中也要刪除這個數(shù)據(jù)，注意刪除的時候空指針等異常情況）。然后將要插入的數(shù)據(jù)放到雙向鏈表的頭部。

2.2 如果有這個數(shù)據(jù)，我們首先應(yīng)該將這個數(shù)據(jù)與它的前驅(qū)和后驅(qū)斷開（注意可能造成空指針異常的情況），然后將這個數(shù)據(jù)插入到頭結(jié)點。

3. 當(dāng)我們需要獲取一個數(shù)據(jù)的時候，查找HashMap中是否有這個數(shù)據(jù)？

3.1 如果有這個數(shù)據(jù)， 我們首先應(yīng)該將這個數(shù)據(jù)與它的前驅(qū)和后驅(qū)斷開（注意可能造成空指針異常的情況），然后將這個數(shù)據(jù)插入到頭結(jié)點。

3.2 如果沒有這個數(shù)據(jù)，返回-1。

代碼

class LRUCache {
    /**
    * 需要實現(xiàn)以下
    * 1.維護一個雙向鏈表，還有他的頭結(jié)點和尾結(jié)點
    * 2.插入數(shù)據(jù)時，首先判斷cache中是否有該結(jié)點？如果沒有，檢查緩存是否還有空間？如果沒有空間，清除雙線鏈表的尾部結(jié)點。將該結(jié)點插入到雙向鏈表的頭部
    * 3.根據(jù)key獲得數(shù)據(jù)的時候，查看cache中是否有key對應(yīng)的結(jié)點？如果有，將該結(jié)點插入到頭結(jié)點前面，返回數(shù)據(jù)：：如果沒有，返回-1。
    */
    private int capacity;
    private LinkNode first;
    private LinkNode last;
    private HashMap<Integer,LinkNode> cache;
    public LRUCache(int capacity) {
        this.capacity=capacity;
        cache = new HashMap<Integer,LinkNode>(capacity);
    }
    
    public int get(int key) {
        LinkNode res=cache.get(key);
        if(res==null){
            return -1;
        }
        moveNodeToFirst(res);
        return res.val;
    }
    
    public void put(int key, int value) {
        LinkNode temp=cache.get(key);
        if(temp==null){
            if(cache.size()>=capacity){
                removeLastNode();
            }
            temp=new LinkNode();
            temp.key=key;
        }
        temp.val=value;
        moveNodeToFirst(temp);
        cache.put(key,temp);
    }
    
    private void removeLastNode(){
        LinkNode temp=last;
        last=last.pre;
        if(last!=null){
            last.next=null;
        }else{
            first=last=null;
        }
        cache.remove(temp.key);
    }
    
    private void moveNodeToFirst(LinkNode node){
        if(first==node) return;
        if(node.pre!=null){
            node.pre.next=node.next;
        }
        if(node.next!=null){
            node.next.pre=node.pre;
        }
        if(node==last){
            last=last.pre;
        }
        if(last==null){
            last=first=node;
            return;
        }
        node.next=first;
        first.pre=node;
        node.pre=null;
        first=node;
    }
}

class LinkNode{
    LinkNode pre;
    LinkNode next;
    int key;
    int val;
}