題目信息

鏈接：leetcode-cn.com/problem

題目描述：

運用你所掌握的數據結構，設計和實現一個 LRU (最近最少使用) 緩存機制。它應該支持以下操作： 獲取數據 get 和 寫入數據 put 。

獲取數據 get(key) - 如果密鑰 (key) 存在於緩存中，則獲取密鑰的值（總是正數），否則返回 -1。寫入數據 put(key, value) - 如果密鑰不存在，則寫入其數據值。

當緩存容量達到上限時，它應該在寫入新數據之前刪除最近最少使用的數據值，從而為新的數據值留出空間。

PS：描述信息中」刪除最近最少使用的數據值「表達可能會讓人產生誤解，此題中想表達的是」刪除最長時間未使用的數據值「。

示例:

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

題目分析

在解題前，我們先對題目進行充分的分析。根據題幹描述的信息，這是一道偏重於數據結構的題。

我們可以從題中所需的 key-value 類型數據中得出我們可能需要使用的數據結構是哈希表（Hash Table）。基礎的哈希表雖具備讀寫 key-value 數據的功能，但是 key 的存儲是無序的，而本題中當 LRU 存滿時，再次存儲時需要刪除掉最久未使用的數據，這就需要我們的數據結構能夠保存特定的順序信息。因此，我們可以考慮一種有序的哈希表。

通常，我們會使用雙向鏈表去記錄哈希表中鍵的順序，每個鍵都有擁有指向前一個鍵的指針和指向後一個鍵的指針。

來源：Wikipedia-雙向鏈表

當我們進行 set & get 操作時，只需要把當前節點調整到鏈表尾，而需要 pop 操作的時候，將鏈表首彈出即可。

實現分析

在 Java 中，LinkedHashMap 是上述有序哈希表（雙向鏈表+哈希表）的實現，網上有許多關於 LinkedHashMap 源碼的講解，例如：LinkedHashMap 的實現原理。

在 Python 中，有一種類似的實現，是 OrderedDict 。和 Java 中的 LinkedHashMap 不同，OrderedDict 只會在 set 新鍵時進行順序的調整，當鍵已經出現在 OrderedDict 時，其原生實現並不會主動調整順序，需要我們使用額外的方法進行主動調整。

我們當然也可以手動造一個新的輪子來完整實現該數據結構，但是在我們真正學會了該數據結構後，實現也並不是特別難的事情。此處我採用了自己的思路，將實現輪子的精力花在了研讀源碼上。

代碼實現

利用已有的輪子，能通過非常簡潔的方式完成本問題，這也是 Python 的魅力所在吧哈哈。

from collections import OrderedDict

class LRUCache:
"""Implement LRUCache using OrderedDict"""
def __init__(self, capacity: int):
self._ordered_dict = OrderedDict()
self._capacity = capacity

def get(self, key: int) -> int:
self._move_to_end_if_exist(key)

return self._ordered_dict.get(key, -1)

def put(self, key: int, value: int) -> None:
self._move_to_end_if_exist(key)

self._ordered_dict[key] = value
if len(self._ordered_dict) > self._capacity:
self._ordered_dict.popitem(last=False) # popitem支持彈出頭部或尾部

def _move_to_end_if_exist(self, key: int) -> None:
if key in self._ordered_dict:
self._ordered_dict.move_to_end(key)

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

源碼分析

由於我們使用的輪子實現的該功能，所以想學習到數據結構的精髓還是應該去翻閱源碼，因此我們分析一下 OrderedDict 的核心源碼。

OrderedDict 是一個繼承自 dict 的對象，在 Python 中，dict 就是用哈希表實現的，因此 OrderedDict 本質上是一種更加強大的哈希表。

class OrderedDict(dict):
Dictionary that remembers insertion order
···

在 set 方法中，實現了雙向鏈表插入操作。

def __setitem__(self, key, value,
dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):
od.__setitem__(i, y) <==> od[i]=y
# Setting a new item creates a new link at the end of the linked list,
# and the inherited dictionary is updated with the new key/value pair.
if key not in self:
self.__map[key] = link = Link()
root = self.__root
last = root.prev
link.prev, link.next, link.key = last, root, key
last.next = link
root.prev = proxy(link)
dict_setitem(self, key, value)

在 del 方法中，實現了雙向鏈表刪除操作。

def __delitem__(self, key, dict_delitem=dict.__delitem__):
od.__delitem__(y) <==> del od[y]
# Deleting an existing item uses self.__map to find the link which gets
# removed by updating the links in the predecessor and successor nodes.
dict_delitem(self, key)
link = self.__map.pop(key)
link_prev = link.prev
link_next = link.next
link_prev.next = link_next
link_next.prev = link_prev
link.prev = None
link.next = None

此外還有 popitem 和 move_to_end 等 API 的實現，因為哈希表的實現已經通過繼承 dict 完成，所以這些 API 的核心都在於雙向鏈表的添加和刪除。

def popitem(self, last=True):
Remove and return a (key, value) pair from the dictionary.

Pairs are returned in LIFO order if last is true or FIFO order if false.

if not self:
raise KeyError(dictionary is empty)
root = self.__root
if last:
link = root.prev
link_prev = link.prev
link_prev.next = root
root.prev = link_prev
else:
link = root.next
link_next = link.next
root.next = link_next
link_next.prev = root
key = link.key
del self.__map[key]
value = dict.pop(self, key)
return key, value

def move_to_end(self, key, last=True):
Move an existing element to the end (or beginning if last==False).

Raises KeyError if the element does not exist.
When last=True, acts like a fast version of self[key]=self.pop(key).


link = self.__map[key]
link_prev = link.prev
link_next = link.next
soft_link = link_next.prev
link_prev.next = link_next
link_next.prev = link_prev
root = self.__root
if last:
last = root.prev
link.prev = last
link.next = root
root.prev = soft_link
last.next = link
else:
first = root.next
link.prev = root
link.next = first
first.prev = soft_link
root.next = link

主要參考資料

  1. Python官方文檔 —— OrderedDict
  2. LinkedHashMap 的實現原理

推薦閱讀：

相關文章