用 Python 手动实现 LRU 算法
![用Python手动实现LRU算法](https://static001.geekbang.org/infoq/29/2973072ccdf009d632fecd310defae0b.png)
说到 LRU 算法,就不得不提哈希链表。
哈希链表
在开始介绍哈希链表前,我们先简单的回顾一下哈希表。
1. 哈希表的读操作
哈希表和我们现实世界中的“词典”很像,都是以一个“键值对(key-value)”的形式存在,比如我们像要查看“わたし”所对应的中文意思是什么,我们只需要通过“わたし”这个“键”在词典中找到与之对应的值即中文的“我”即可,而不需要从字典的第一页开始一页一页的翻,因此它的时间复杂度是 O(1)。
还记得自己学生时代,总是习惯在字典的侧面用笔将五十音图按照顺序涂上颜色,这样方便更快的查找。
我们查找“わたし”这三个假名,还是有点慢,因为它是三个字符,但是如果我们将他转换成页数,假设每个单词单独一页。然后通过这个页码找单词是不是会更快一些呢?
回到编程的世界,则存在一个叫做哈希函数的东西。在 Python 的语言中每一个对象都有一个与之对应的哈希值(hash 值),无论什么类型的对象,它的 hash 值都是一个整数对象。而值(value)则保存在一个数组里面。转换方式其实很简单:
size 就是我们保存值的数组的大小
但是,由于直接取 hash 值,有可能会出现负数的情况,比如我们“わたし”这个 key 的 hash 值就是“-6935749861035834984”。用负数进行模运算是比较麻烦的一件事。
![](https://static001.geekbang.org/infoq/ed/edc0e677917637e313cf583b1dc47ffa.png)
通常我们是用每一个元素的 ASCII 码相加,再运行模运算。
例如我们上面的那个例子,如果我们用来保存中文“我”的数组大小是 8,而“わたし”的每个值的 ASCII 码分别是 12431,12383,12375
![](https://static001.geekbang.org/infoq/ef/ef3021eecf9d6e858ec59202e0499cdb.png)
因此我们得到的“わたし”在数组中的下标是
这样我们便可以通过这个下标在数组中更快的找到“我”这个元素。
介绍完哈希表的的读(get),我们再看看怎么将一个值保存进哈希表,即写(put)的操作
2. 哈希表的写操作
比如我们希望将 YYDS 这个网络词语添加到字典中。
利用上面介绍的方法将 YYDS 转换成数组下标 1
![](https://static001.geekbang.org/infoq/57/57b38bf4de7526e5fbe8315e67e88866.png)
如果数组中 1 的位置没有元素,则将“永远的神”保存在这个位置
但是如果,这个位置有内容了怎么办,这个中情况我们通常叫做哈希冲突。通常有两种方式解决这个问题,一个是开放寻址方法(Python 用的就是这种),另一个就是链表法。
放寻址方法:从当前位置向后找,直到找到为空的位置,然后保存数据
链表法:通过修改链表的 head 和 next 来保存数据
3. 哈希链表
其实就是将 hash 和双向链表结合在了一起。这个更方便数据的操作。
时间复杂度期望值:查找,删除,更新, 插入都是 O(1)。
即数据分布很平均,没有相同 hash 值
时间复杂度最坏值:查找,删除,更新, 插入都是 O(n)。
即所有的 hash 值都是重复的
LRU 算法实现
在介绍玩 hash 表后,我们来看一个业务场景。
我们需要对公司的所有员工信息进行管理,各个部门都会使用这个数据,因此为了减少数据的频繁访问,我们将数据保存在内存中的一个 hash 表中。这样数据的查询速度要快很多。但是随着人员增加,日积月累,在不扩展硬件的情况下,总有一天我们的内存会溢出,那么该怎么解决这个问题呢?
这便引出了我们今天的主角-----LRU 算法。
它的核心思想是在有新数据添加进来,且预先分配的空间已满时删除访问最少的那个数据,从而保证数据的正常。
这是员工数据在 hash 缓存中的,按照被访问的时间顺序,一次从右端开始插入
![](https://static001.geekbang.org/infoq/2f/2fb7fdeed936bff78cdeafeeafebc2bc.png)
这时来了新员工,且分配的内存空间还充足的情况,就会变成下图所示
![](https://static001.geekbang.org/infoq/99/9933daf0e13576bed54164e0e89bd732.png)
如果我们访问二号员工,它就会先将二号删除,然后在右端重新插入
![](https://static001.geekbang.org/infoq/24/24627bf9cbe6de7cdd545caac411b3da.png)
![](https://static001.geekbang.org/infoq/32/32bfa97e23c10d27e8955ec0b44b8039.png)
接着又来一个新员工,但是已经没有足够的内存了,因此我们需要将最左端好久没有访问的数据删除,然后将 6 号员工插入到右端。
![](https://static001.geekbang.org/infoq/15/15c9ae08b2b84b9745f9f0abd9b891ab.png)
![](https://static001.geekbang.org/infoq/82/828b2567f03ddc1409200a6521926424.png)
这个便是我们的 LRU 算法的核心原理了。
Python 中的 collections.OrderedDict 其实已经对哈希链表进行了很好的实现,但是为了学习我们还是来手动实现一下。
![](https://static001.geekbang.org/infoq/15/15a39042e0c7319489d04af791b3ee78.png)
版权声明: 本文为 InfoQ 作者【IT蜗壳-Tango】的原创文章。
原文链接:【http://xie.infoq.cn/article/0d41a384f2b963e05e9f580c8】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论 (1 条评论)