Python实现LRU Cache：基于双端链表与哈希表的原理详解
本文详细解析LRU（近期最少使用）缓存算法的核心原理，并展示如何在Python中通过双端循环链表与哈希表结合的方式实现LRUCache。文章深入探讨了get和set操作的内部逻辑，包括节点移动、哈希冲突处理及容量溢出时的淘汰机制，为理解缓存设计提供清晰的技术参考。
简介
LRU（Least Recently Used，近期最少使用）是一种常用的缓存淘汰策略。尽管“最近”一词在时间或空间维度上可能存在歧义，但更准确的理解是“近期最少使用”。其核心逻辑在于：若某个数据近期被访问过，则推测其未来被访问的概率也较高。因此，当缓存容量达到预设上限时，系统会移除那些在近期最少被使用的数据对象。在Java等语言中，LRUCache通常基于LinkedHashMap实现，并通过设置访问顺序来体现LRU特性。
无论是执行get操作还是set操作，均视为对该key的一次访问。当向LRU Cache中插入一个不存在的key，且当前缓存中的key数量超过设定的cache size时，系统必须移除那个距离当前时间最久未被使用的key。
LRU Cache实现
在Java生态中，LRUCache的标准实现依赖于LinkedHashMap。此处，我们参照其设计思路，尝试用Python实现一个LRU Cache版本（具体实现细节可能与某些现有库存在差异）。
首先，需要明确以下内部结构：
LRU Cache对象内部维护一个双端循环链表的头节点（Head Node）。
LRU Cache对象内部同时维护一个字典（dict）结构。
该内部字典的值均为Entry对象，每个Entry对象包含以下字段：
- key的hash_code（即hash(key)的值。在本实现中，若不同key产生相同的hash_code，则被视为同一个key处理。因此，对于自定义类，务必实现__hash__魔术方法以确保正确性）。
- v：即(key, value)对中的value部分。
- prev：指向前一个Entry对象的指针。
- next：指向后一个Entry对象的指针。
具体实现逻辑如下：
当从LRU Cache中获取（get）一个key时：
- 计算该key对应的hash_code。
- 从内部字典中查找并获取对应的entry。
- 将该entry移动到双端循环链表的第一个位置（即最近使用位置）。
- 返回entry.value。
当向LRU Cache中设置（set）一个(key, value)对时：
计算该key的hash_code。
从LRU Cache的内部字典中，取出该hash_code对应的old_entry（若存在）。随后，基于(key, value)生成一个新的new_entry，并执行以下操作：
- 更新字典：dict[hash_code] = new_entry。
- 将new_entry移动到双端循环链表的第一个位置。
- 如果old_entry存在，则从链表中将其删除。
- 若是新增了一个(key, value)对，且此时缓存中key的数量超过了cache size，则删除双端链表的最后一个元素（该元素即为最近最少使用的元素），并从内部字典中同步删除该元素。
HashMap的实现原理
（此知识点在面试中常被考察）：HashMap底层由数组和链表组合而成的散列结构构成。通过hash算法，尽量将数据均匀分布到数组中；若发生hashcode相同的情况，则进一步比较equals方法。若equals返回false，则将数据以链表形式存储在数组对应位置，并将原在该位置的数据向后移动，同时记录next属性以指向下一个数据节点。
注意：数组中保存的是entry对象，其中存储了具体的键值对。
Python实现
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"
总结
以上就是本文的全部内容，希望这些内容对大家的学习或工作具有一定的参考价值。如有任何疑问，欢迎留言交流，感谢大家对本站的支持。
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
