用 Python 手动实现 LRU 算法

IT蜗壳-Tango

关注

发布于: 2021 年 06 月 26 日

说到 LRU 算法，就不得不提哈希链表。

哈希链表

在开始介绍哈希链表前，我们先简单的回顾一下哈希表。

1. 哈希表的读操作

哈希表和我们现实世界中的“词典”很像，都是以一个“键值对（key-value）”的形式存在，比如我们像要查看“わたし”所对应的中文意思是什么，我们只需要通过“わたし”这个“键”在词典中找到与之对应的值即中文的“我”即可，而不需要从字典的第一页开始一页一页的翻，因此它的时间复杂度是 O(1)。

还记得自己学生时代，总是习惯在字典的侧面用笔将五十音图按照顺序涂上颜色，这样方便更快的查找。

我们查找“わたし”这三个假名，还是有点慢，因为它是三个字符，但是如果我们将他转换成页数，假设每个单词单独一页。然后通过这个页码找单词是不是会更快一些呢？

回到编程的世界，则存在一个叫做哈希函数的东西。在 Python 的语言中每一个对象都有一个与之对应的哈希值(hash 值)，无论什么类型的对象，它的 hash 值都是一个整数对象。而值(value)则保存在一个数组里面。转换方式其实很简单：

i n d e x = h a s h (k e y) % s i z e

size 就是我们保存值的数组的大小

但是，由于直接取 hash 值，有可能会出现负数的情况，比如我们“わたし”这个 key 的 hash 值就是“-6935749861035834984”。用负数进行模运算是比较麻烦的一件事。

通常我们是用每一个元素的 ASCII 码相加，再运行模运算。

例如我们上面的那个例子，如果我们用来保存中文“我”的数组大小是 8，而“わたし”的每个值的 ASCII 码分别是 12431，12383，12375

因此我们得到的“わたし”在数组中的下标是

i n d e x = （ 12431 + 12383 + 12375 ） % 8

i n d e x = 37189 % 8

i n d e x = 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())