用 Python 手动实现 LRU 算法

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

哈希链表

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

1. 哈希表的读操作

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

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

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

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

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

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

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

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

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

这样我们便可以通过这个下标在数组中更快的找到“我”这个元素。

介绍完哈希表的的读（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 = keyself.value = valueself.pre = Noneself.next = None

class LRUCache:def init(self, limit):self.limit = limitself.hash = {}self.head = Noneself.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())