最近最少使用的緩存機(jī)制，完整實(shí)現(xiàn)

你好，我是zhenguo

今天結(jié)合一道leetcode有意思的題目，設(shè)計(jì)和實(shí)現(xiàn)一個(gè)  LRU (最近最少使用) 緩存機(jī)制，順便和讀者們加強(qiáng)下雙向鏈表、字典這些數(shù)據(jù)結(jié)構(gòu)的應(yīng)用能力。鏈表增刪操作時(shí)間復(fù)雜度都是O(1)，這是它最強(qiáng)的地方，尤其追求卓越性能的算法場(chǎng)景，應(yīng)用廣泛。同時(shí)，在面試中也經(jīng)常會(huì)考察到。但是，鏈表比較容易出錯(cuò)，如果在項(xiàng)目中應(yīng)用，務(wù)必要多多測(cè)試。

1 問(wèn)題

運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)和實(shí)現(xiàn)一個(gè)  LRU (最近最少使用) 緩存機(jī)制 。實(shí)現(xiàn) LRUCache 類(lèi)：

LRUCache(int capacity) 以正整數(shù)作為容量 capacity 初始化 LRU 緩存 

int get(int key)  如果關(guān)鍵字 key 存在于緩存中，則返回關(guān)鍵字的值，否則返回 -1 。

void put(int key, int value) 如果關(guān)鍵字已經(jīng)存在，則變更其數(shù)據(jù)值；如果關(guān)鍵字不存在，則插入該組「關(guān)鍵字-值」。

當(dāng)緩存容量達(dá)到上限時(shí)，它應(yīng)該在寫(xiě)入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

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

鏈接：https://leetcode-cn.com/problems/lru-cache

2 鏈表

這道題最高效的O(1)實(shí)現(xiàn)需要基于鏈表結(jié)構(gòu)，因此再溫習(xí)一下鏈表的基本操作。

鏈表是一種節(jié)點(diǎn)傳遞結(jié)構(gòu)，所謂的"傳遞"是靠next變量，以此建立指向下一個(gè)節(jié)點(diǎn)的關(guān)系，可以理解為一條邊，僅此而已。

如果想令j節(jié)點(diǎn)指向i節(jié)點(diǎn)，需要如何做？如果對(duì)鏈表不熟悉，可能想當(dāng)然的這么操作：

node_j.next = node_i

上面操作后實(shí)現(xiàn)效果如下：

這是不對(duì)的，節(jié)點(diǎn)i指向節(jié)點(diǎn)j的邊還存在，這不是我們想要的結(jié)果！因此，我們需要摘除這條邊，那么如何摘除？實(shí)際這才是鏈表的靈活之處，所謂的摘除只不過(guò)是一個(gè)None賦值操作：

node_i.next = None

上面賦值實(shí)現(xiàn)的效果如下：

你看到嗎？剪斷后，節(jié)點(diǎn)i和節(jié)點(diǎn)j之間不再有鏈接關(guān)系。所以j節(jié)點(diǎn)指向i節(jié)點(diǎn)的完整代碼如下：

node_i.next = None
node_j.next = node_i

3 實(shí)現(xiàn)思路

下面我們?cè)倩仡^問(wèn)題，要想在O(1)時(shí)間復(fù)雜度內(nèi)求解，需要借助字典和雙向鏈表，問(wèn)題涉及的主要操作包括：

(1). put操作 加入鍵值對(duì)分兩種情況討論：

• (1).1 鍵不存在
• (1).2 鍵存在

(2).get操作，get操作除了具備dict.get的功能外，此處需要定制一個(gè)新的功能，即最近使用的節(jié)點(diǎn)需要移動(dòng)到熱點(diǎn)區(qū)域。而我們知道鏈表的增刪時(shí)間復(fù)雜度都是O(1)，所以根據(jù)這個(gè)定制化需求，使用鏈表是再自然不過(guò)的了！

4 完整代碼

class Node(object):
    """
    定義雙向鏈表
    """
    def __init__(self, val, pre, next):
        self.val = val
        self.pre = pre
        self.next = next

LRUCache緩存類(lèi)：

class LRUCache:
    def __init__(self, capacity: int):
        self.cache_dict = {}
        self.linked_dict = {}
        self.capacity = capacity
        self.head, self.tail = None, None

put操作對(duì)應(yīng)代碼，主要解決三種情況，這和題目是完整一一對(duì)應(yīng)的，分別為：

• 如果關(guān)鍵字已經(jīng)存在，則變更其數(shù)據(jù)值
• 如果關(guān)鍵字不存在，則插入該組「關(guān)鍵字-值」
• 當(dāng)緩存容量達(dá)到上限時(shí)，它應(yīng)該在寫(xiě)入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

    def put(self, key: int, value: int) -> None:
        if key in self.cache_dict:  # 如果關(guān)鍵字已經(jīng)存在，則變更其數(shù)據(jù)值
            self.cache_dict[key] = value
            self._move_to_tail(key)
        elif len(self.cache_dict) < self.capacity:  # 如果關(guān)鍵字不存在，則插入該組「關(guān)鍵字-值」
            self.cache_dict[key] = value
            self.linked_dict[key] = Node(key, None, None)
            if not self.head:
                self.head = self.linked_dict[key]
            if self.tail:
                self.tail.next = self.linked_dict[key]

            tmp = self.tail
            self.tail = self.linked_dict[key]
            if tmp:
                self.linked_dict[key].pre = tmp
                tmp.next = self.linked_dict[key]

        else:  # 當(dāng)緩存容量達(dá)到上限時(shí)，
            # 它應(yīng)該在寫(xiě)入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。
            self.cache_dict[key] = value
            self.linked_dict[key] = Node(key, None, None)
            del_key = self.head.val
            self.cache_dict.pop(del_key)
            pre, next = self.linked_dict[del_key].pre, self.linked_dict[del_key].next
            if not pre and not next:  # 刪除節(jié)點(diǎn)無(wú)頭無(wú)尾
                self.head = self.linked_dict[key]
            elif not pre:  # 刪除元素是頭節(jié)點(diǎn)
                next.pre = None
                self.head = next
            elif not next:  # 刪除元素是尾節(jié)點(diǎn)
                pre.next = None
                self.tail = pre
            else:
                pre.next = next
                next.pre = pre

            # 然后在尾部連接上key節(jié)點(diǎn)
            self.tail.next = self.linked_dict[key]
            self.linked_dict[key].pre = self.tail
            self.linked_dict[key].next = None
            self.tail = self.linked_dict[key]
            # 最后再?gòu)膌inked_dict中移除key
            self.linked_dict.pop(del_key)

get操作，

    def get(self, key: int) -> int:
        if key in self.linked_dict and self.tail != self.linked_dict[key]:
            self._move_to_tail(key)
        return self.cache_dict.get(key, -1)

簡(jiǎn)單重構(gòu)一下，抽離出一個(gè)移動(dòng)節(jié)點(diǎn)i到tail處的方法_move_to_tail：

def _move_to_tail(self, key):
        """
        移動(dòng)key節(jié)點(diǎn)到tail
        :param key:
        :return:
        """
        pre, next = self.linked_dict[key].pre, self.linked_dict[key].next
        # 從鏈表中隔斷key節(jié)點(diǎn)
        if pre and next:
            pre.next = next
            next.pre = pre
        elif next:
            next.pre = None
            self.head = next
        # 如果key節(jié)點(diǎn)不在尾部，則移動(dòng)key節(jié)點(diǎn)到尾部
        if self.tail != self.linked_dict[key]:
            self.linked_dict[key].pre = self.tail
            tmp = self.tail
            self.tail = self.linked_dict[key]
            if tmp:
                tmp.next = self.tail
            self.linked_dict[key].next = None

5 后記

鏈表操作比較容易出錯(cuò)，平時(shí)需要多加練習(xí)，才能在實(shí)際項(xiàng)目和面試中，使用得心應(yīng)手。

其實(shí)鏈表的應(yīng)用極為廣泛，包括我們熟知的版本管理軟件git，里面的多分支和某個(gè)分支的管理，都是基于鏈表操作的。牢固的掌握鏈表才算是深度掌握算法和數(shù)據(jù)結(jié)構(gòu)的第一步。