用Python手动实现LRU算法
说到 LRU 算法，就不得不提哈希链表。
哈希链表
在开始介绍哈希链表前，我们先简单的回顾一下哈希表。
1. 哈希表的读操作
哈希表和我们现实世界中的“词典”很像，都是以一个“键值对（key-value）”的形式存在，比如我们像要查看“わたし”所对应的中文意思是什么，我们只需要通过“わたし”这个“键”在词典中找到与之对应的值即中文的“我”即可，而不需要从字典的第一页开始一页一页的翻，因此它的时间复杂度是 O(1)。
还记得自己学生时代，总是习惯在字典的侧面用笔将五十音图按照顺序涂上颜色，这样方便更快的查找。
我们查找“わたし”这三个假名，还是有点慢，因为它是三个字符，但是如果我们将他转换成页数，假设每个单词单独一页。然后通过这个页码找单词是不是会更快一些呢？
回到编程的世界，则存在一个叫做哈希函数的东西。在 Python 的语言中每一个对象都有一个与之对应的哈希值(hash 值)，无论什么类型的对象，它的 hash 值都是一个整数对象。而值(value)则保存在一个数组里面。转换方式其实很简单：
index=hash(key)%size
size 就是我们保存值的数组的大小
但是，由于直接取 hash 值，有可能会出现负数的情况，比如我们“わたし”这个 key 的 hash 值就是“-6935749861035834984”。用负数进行模运算是比较麻烦的一件事。
通常我们是用每一个元素的 ASCII 码相加，再运行模运算。
例如我们上面的那个例子，如果我们用来保存中文“我”的数组大小是 8，而“わたし”的每个值的 ASCII 码分别是 12431，12383，12375
因此我们得到的“わたし”在数组中的下标是
index=（12431+12383+12375）%8
index=37189%8
index=5
这样我们便可以通过这个下标在数组中更快的找到“我”这个元素。
介绍完哈希表的的读（get），我们再看看怎么将一个值保存进哈希表，即写（put）的操作
2. 哈希表的写操作
比如我们希望将 YYDS 这个网络词语添加到字典中。
- 利用上面介绍的方法将 YYDS 转换成数组下标 1
- 如果数组中 1 的位置没有元素，则将“永远的神”保存在这个位置
- 但是如果，这个位置有内容了怎么办，这个中情况我们通常叫做哈希冲突。通常有两种方式解决这个问题，一个是开放寻址方法（Python 用的就是这种），另一个就是链表法。
- 放寻址方法：从当前位置向后找，直到找到为空的位置，然后保存数据
- 链表法：通过修改链表的 head 和 next 来保存数据
3. 哈希链表
其实就是将 hash 和双向链表结合在了一起。这个更方便数据的操作。
时间复杂度期望值：查找，删除，更新, 插入都是 O(1)。
即数据分布很平均，没有相同 hash 值
时间复杂度最坏值：查找，删除，更新, 插入都是 O(n)。
即所有的 hash 值都是重复的
LRU 算法实现
在介绍玩 hash 表后，我们来看一个业务场景。
我们需要对公司的所有员工信息进行管理，各个部门都会使用这个数据，因此为了减少数据的频繁访问，我们将数据保存在内存中的一个 hash 表中。这样数据的查询速度要快很多。但是随着人员增加，日积月累，在不扩展硬件的情况下，总有一天我们的内存会溢出，那么该怎么解决这个问题呢?
这便引出了我们今天的主角-----LRU 算法。
它的核心思想是在有新数据添加进来，且预先分配的空间已满时删除访问最少的那个数据，从而保证数据的正常。
- 这是员工数据在 hash 缓存中的，按照被访问的时间顺序，一次从右端开始插入
- 这时来了新员工，且分配的内存空间还充足的情况，就会变成下图所示
- 如果我们访问二号员工，它就会先将二号删除，然后在右端重新插入
- 接着又来一个新员工，但是已经没有足够的内存了，因此我们需要将最左端好久没有访问的数据删除，然后将 6 号员工插入到右端。
这个便是我们的 LRU 算法的核心原理了。
Python 中的 collections.OrderedDict 其实已经对哈希链表进行了很好的实现，但是为了学习我们还是来手动实现一下。
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.pre = None
self.next = None
class LRUCache:
def __init__(self, limit):
self.limit = limit
self.hash = {}
self.head = None
self.end = None
def get(self, key):
node = self.hash.get(key)
if node is None:
return None
self.refresh_node(node)
return node.value
def put(self, key, value):
node = self.hash.get(key)
if node is None:
# 如果key不存在，插入key-value
if len(self.hash) >= self.limit:
old_key = self.remove_node(self.head)
self.hash.pop(old_key)
node = Node(key, value)
self.add_node(node)
self.hash[key] = node
else:
# 如果key存在，刷新key-value
node.value = value
self.refresh_node(node)
def refresh_node(self, node):
# 如果访问的是尾节点，无需移动节点
if node == self.end:
return
# 移除节点
key = self.remove_node(node)
self.hash.pop(key)
# 重新插入节点
self.put(node.key, node.value)
def remove_node(self, node):
if node == self.head and node == self.end:
# 移除唯一的节点
self.head = None
self.end = None
elif node == self.end:
# 移除节点
self.end = self.end.pre
self.end.next = None
elif node == self.head:
# 移除头节点
self.head = self.head.next
self.head.pre = None
else:
# 移除中间节点
node.pre.next = node.pre
node.next.pre = node.next
return node.key
def add_node(self, node):
if self.end is not None:
self.end.next = node
node.pre = self.end
node.next = None
self.end = node
if self.head is None:
self.head = node
if __name__ == "__main__":
lruCache = LRUCache(5)
lruCache.put("001", "用户1信息")
lruCache.put("002", "用户2信息")
lruCache.put("003", "用户3信息")
lruCache.put("004", "用户4信息")
lruCache.put("005", "用户5信息")
print("----------初始化完成后的排序----------")
print(lruCache.hash.keys())
print("----------查询完002后的排序----------")
print(lruCache.get("002"))
print(lruCache.hash.keys())
print("----------添加新员工后的排序----------")
lruCache.put("006", "用户6信息")
print(lruCache.hash.keys())
- 发表于:
- 本文为 InfoQ 中文站特供稿件
- 首发地址：https://www.infoq.cn/article/0d41a384f2b963e05e9f580c8
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
