在第一節(jié)中已經(jīng)實(shí)現(xiàn)了雙向鏈表DoubleLinkedList類，本節(jié)我們基于雙向鏈表實(shí)現(xiàn)LRU（Least Recently Used最近最少使用）緩存置換算法。Redis的淘汰機(jī)制就包括LRU算法，用來淘汰那些最近最少使用的數(shù)據(jù)，具體怎么使用可在redis的配置文件中設(shè)置。

一、LRU算法的實(shí)現(xiàn)

邏輯很簡單，get和put兩種操作，其中g(shù)et時如果元素存在則將節(jié)點(diǎn)從當(dāng)前位置移到鏈表頭部，表示最近被訪問到的節(jié)點(diǎn)；put時也是，不管節(jié)點(diǎn)之前存不存在都要移動到鏈表頭部。同樣通過一個map來實(shí)現(xiàn)查找時的O(1)復(fù)雜度。

class LRUCache(object):

? ? def __init__(self, capacity=0xffffffff):
? ? ? ? """
? ? ? ? LRU緩存置換算法 最近最少使用
? ? ? ? :param capacity:
? ? ? ? """
? ? ? ? self.capacity = capacity
? ? ? ? self.size = 0
? ? ? ? self.map = {}
? ? ? ? self.list = DoubleLinkedList(capacity)

? ? def get(self, key):
? ? ? ? """
? ? ? ? 獲取元素
? ? ? ? ? ? 獲取元素不存在 返回None
? ? ? ? ? ? 獲取元素已存在 將節(jié)點(diǎn)從當(dāng)前位置刪除并添加至鏈表頭部
? ? ? ? :param key:
? ? ? ? :return:
? ? ? ? """
? ? ? ? # 元素不存在
? ? ? ? if key not in self.map:
? ? ? ? ? ? return None

? ? ? ? node = self.map.get(key)
? ? ? ? self.list.remove(node)
? ? ? ? self.list.append_front(node)

? ? ? ? return node.value

? ? def put(self, key, value):
? ? ? ? """
? ? ? ? 添加元素
? ? ? ? ? ? 被添加的元素已存在 更新元素值并已到鏈表頭部
? ? ? ? ? ? 被添加的元素不存在
? ? ? ? ? ? ? ? 鏈表容量達(dá)到上限 刪除尾部元素
? ? ? ? ? ? ? ? 鏈表容量未達(dá)上限 添加至鏈表頭部
? ? ? ? :param key:
? ? ? ? :param value:
? ? ? ? :return:
? ? ? ? """
? ? ? ? if key in self.map:
? ? ? ? ? ? node = self.map.get(key)
? ? ? ? ? ? node.value = value
? ? ? ? ? ? self.list.remove(node)
? ? ? ? ? ? self.list.append_front(node)
? ? ? ? else:
? ? ? ? ? ? if self.size >= self.capacity:
? ? ? ? ? ? ? ? old_node = self.list.remove()
? ? ? ? ? ? ? ? del self.map[old_node.key]
? ? ? ? ? ? ? ? self.size -= 1

? ? ? ? ? ? node = Node(key, value)
? ? ? ? ? ? self.map[key] = node
? ? ? ? ? ? self.list.append_front(node)
? ? ? ? ? ? self.size += 1

? ? ? ? return node

? ? def print(self):
? ? ? ? """
? ? ? ? 打印當(dāng)前鏈表
? ? ? ? :return:
? ? ? ? """
? ? ? ? self.list.print()

二、測試邏輯

if __name__ == '__main__':
? ? lru_cache = LRUCache(3)
? ? lru_cache.put(1, 1)
? ? lru_cache.print()
? ? lru_cache.put(2, 2)
? ? lru_cache.print()
? ? print(lru_cache.get(1))
? ? lru_cache.print()
? ? lru_cache.put(3, 3)
? ? lru_cache.print()
? ? lru_cache.put(1, 100)
? ? lru_cache.print()
? ? lru_cache.put(4, 4)
? ? lru_cache.print()
? ? print(lru_cache.get(1))
? ? lru_cache.print()

測試結(jié)果: