快捷導(dǎo)航

LRUCache的實(shí)現(xiàn)原理及利用python實(shí)現(xiàn)的方法

更新時(shí)間：2017年11月21日 09:45:41 作者：蒂米

LruCache 是 Android 的一個內(nèi)部類，提供了基于內(nèi)存實(shí)現(xiàn)的緩存，而下面這篇文章主要給大家介紹了關(guān)于LRUCache的實(shí)現(xiàn)原理以及利用python實(shí)現(xiàn)的方法，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友可以參考借鑒，下面來一起看看吧。

簡介

LRU(Least Recently Used)最近最少使用，最近有時(shí)間和空間最近的歧義，所以我更喜歡叫它近期最少使用算法。它的核心思想是，如果一個數(shù)據(jù)被訪問過，我們有理由相信它在將來被訪問的概率就越高。于是當(dāng)LRU緩存達(dá)到設(shè)定的最大值時(shí)將緩存中近期最少使用的對象移除。LRUCache內(nèi)部使用LinkedHashMap來存儲key-value鍵值對，并將LinkedHashMap設(shè)置為訪問順序來體現(xiàn)LRU算法。

無論是對某個key的get，還是set都算做是對該key的一次使用。當(dāng)set一個不存在的key，并且LRU Cache中key的數(shù)量超過cache size的時(shí)候，需要將使用時(shí)間距離現(xiàn)在最長的那個key從LRU Cache中清除。

LRU Cache實(shí)現(xiàn)

在Java中，LRUCache是通過LinkedHashMap實(shí)現(xiàn)的。鄙人照貓畫虎，實(shí)現(xiàn)一個Python版的LRU Cache（可能和其他大神的實(shí)現(xiàn)有所區(qū)別）。

首先，需要說明的是：

LRU Cache對象內(nèi)部會維護(hù)一個雙端循環(huán)鏈表的頭節(jié)點(diǎn)

LRU Cache對象內(nèi)部會維護(hù)一個dict

內(nèi)部dict的value都是Entry對象，每個Entry對象包含：

key的hash_code（hash_code = hash(key)，在本實(shí)現(xiàn)中，hash_code相同的不同key，會被當(dāng)作一個key來處理。因此，對于自定義類，應(yīng)該實(shí)現(xiàn)魔術(shù)方法：__hash__）
v - (key, value)對中的value
prev - 前一個對象
next - 后一個對象

具體實(shí)現(xiàn)是：

當(dāng)從LRU Cache中g(shù)et一個key的時(shí)候：

計(jì)算該key的hash_code
從內(nèi)部dict中獲取到entry
將該entry移動到雙端循環(huán)鏈表的第一個位置
返回entry.value

當(dāng)向LRU Cache中set一個(key, value)對的時(shí)候：

計(jì)算該key的hash_code，

從LRU Cache的內(nèi)部dict中，取出該hash_code對應(yīng)的old_entry（可能不存在），然后根據(jù)(key, value)對生成一個new_entry，之后執(zhí)行：

dict[hash_code] = new_entry
將new_entry提到雙端循環(huán)鏈表的第一個位置
如果old_entry存在，則從鏈表中刪除old_entry
如果是新增了一個(key, value)對，并且cache中key的數(shù)量超過了cache size，那么將雙端鏈表的最后一個元素刪除（該元素就是那個最近最少被使用的元素），并且從內(nèi)部dict中刪除該元素

HashMap的實(shí)現(xiàn)原理

（面試過程中也經(jīng)常會被問到）：數(shù)組和鏈表組合成的鏈表散列結(jié)構(gòu)，通過hash算法，盡量將數(shù)組中的數(shù)據(jù)分布均勻，如果hashcode相同再比較equals方法，如果equals方法返回false，那么就將數(shù)據(jù)以鏈表的形式存儲在數(shù)組的對應(yīng)位置，并將之前在該位置的數(shù)據(jù)往鏈表的后面移動，并記錄一個next屬性，來指示后移的那個數(shù)據(jù)。

注意：數(shù)組中保存的是entry（其中保存的是鍵值）

Python實(shí)現(xiàn)

class Entry:
 def __init__(self, hash_code, v, prev=None, next=None):
 self.hash_code = hash_code
 self.v = v
 self.prev = prev
 self.next = next

 def __str__(self):
 return "Entry{hash_code=%d, v=%s}" % (
  self.hash_code, self.v)
 __repr__ = __str__

class LRUCache:
 def __init__(self, max_size):
 self._max_size = max_size
 self._dict = dict()
 self._head = Entry(None, None)
 self._head.prev = self._head
 self._head.next = self._head

 def __setitem__(self, k, v):
 try:
  hash_code = hash(k)
 except TypeError:
  raise

 old_entry = self._dict.get(hash_code)
 new_entry = Entry(hash_code, v)
 self._dict[hash_code] = new_entry

 if old_entry:
  prev = old_entry.prev
  next = old_entry.next
  prev.next = next
  next.prev = prev

 head = self._head
 head_prev = self._head.prev
 head_next = self._head.next

 head.next = new_entry
 if head_prev is head:
  head.prev = new_entry
 head_next.prev = new_entry
 new_entry.prev = head
 new_entry.next = head_next

 if not old_entry and len(self._dict) > self._max_size:
  last_one = head.prev
  last_one.prev.next = head
  head.prev = last_one.prev
  self._dict.pop(last_one.hash_code)

 def __getitem__(self, k):
 entry = self._dict[hash(k)]
 head = self._head
 head_next = head.next
 prev = entry.prev
 next = entry.next

 if entry.prev is not head:
  if head.prev is entry:
  head.prev = prev
  head.next = entry

  head_next.prev = entry
  entry.prev = head
  entry.next = head_next

  prev.next = next
  next.prev = prev

 return entry.v

 def get_dict(self):
 return self._dict

if __name__ == "__main__":
 cache = LRUCache(2)
 inner_dict = cache.get_dict()

 cache[1] = 1
 assert inner_dict.keys() == [1], "test 1"
 cache[2] = 2
 assert sorted(inner_dict.keys()) == [1, 2], "test 2"
 cache[3] = 3
 assert sorted(inner_dict.keys()) == [2, 3], "test 3"
 cache[2]
 assert sorted(inner_dict.keys()) == [2, 3], "test 4"
 assert inner_dict[hash(2)].next.v == 3
 cache[4] = 4
 assert sorted(inner_dict.keys()) == [2, 4], "test 5"
 assert inner_dict[hash(4)].v == 4, "test 6"

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，如果有疑問大家可以留言交流，謝謝大家對腳本之家的支持。

您可能感興趣的文章: