小林手撕 LRU 算法!
时间:2021-08-19 15:44:46
手机看文章
扫描二维码
随时随地手机看文章
[导读]大家好,我是小林。前几天,我写一篇感受计算机基础之美的文章:坚持一年了里面介绍了个心跳服务的宕机判断算法,当时只是理论分析了下使用LRU算法来实现,没有手撕代码。今天,就带大家手撕LRU算法,先让大家回顾下案例,然后后面就进行代码讲解。宕机判断算法的设计心跳服务主要做两件事情:发...
大家好,我是小林。前几天,我写一篇感受计算机基础之美的文章:坚持一年了里面介绍了个心跳服务的宕机判断算法,当时只是理论分析了下使用 LRU 算法来实现,没有手撕代码。今天,就带大家手撕 LRU 算法,先让大家回顾下案例,然后后面就进行代码讲解。
要将主机从哈希表删除,首先我们要知道主机的 IP,因为这是哈希表的 Key。双向链表存储的内容必须包含主机的 IP 信息,那为了更快查询到主机的 IP,双向链表存储的内容可以是一个键值对(Key-Value),其 Key 就是主机的 IP,Value 就是主机的信息。这样,在发现双向链表中头部的节点超时了,由于节点的内容是键值对,于是就能快速地从该节点获取主机的 IP ,知道了主机的 IP 信息,就能把哈希表中该主机信息删除。至此,就设计出了一个高性能的宕机判断算法,主要用了数据结构:哈希表 双向链表,通过这个组合,查询 删除 插入操作的时间复杂度都是 O(1),以空间换时间的思想,这就是数据结构与算法之美!熟悉算法的同学应该感受出来了,上面这个算法就是类 LRU 算法,用于淘汰最近最久使用的元素的场景,该算法应用范围很广的,操作系统、Redis、MySQL 都有使用该算法。
宕机判断算法的设计
心跳服务主要做两件事情:- 发现宕机的主机;
- 发现上线的主机。
- 如果不存在哈希表里,说明是新主机上线,先将其插入到双向链表的头部,然后将该主机的 IP 作为 Key,主机在双向链表的节点作为 Value 插入到哈希表。
- 如果存在哈希表里,说明主机已经上线过,先通过查询哈希表,找到该主机在双向链表里旧的心跳包的节点,然后就可以通过该节点将其从双向链表中删除,最后将新的心跳包插入到双向链表的队尾,同时更新哈希表。
要将主机从哈希表删除,首先我们要知道主机的 IP,因为这是哈希表的 Key。双向链表存储的内容必须包含主机的 IP 信息,那为了更快查询到主机的 IP,双向链表存储的内容可以是一个键值对(Key-Value),其 Key 就是主机的 IP,Value 就是主机的信息。这样,在发现双向链表中头部的节点超时了,由于节点的内容是键值对,于是就能快速地从该节点获取主机的 IP ,知道了主机的 IP 信息,就能把哈希表中该主机信息删除。至此,就设计出了一个高性能的宕机判断算法,主要用了数据结构:哈希表 双向链表,通过这个组合,查询 删除 插入操作的时间复杂度都是 O(1),以空间换时间的思想,这就是数据结构与算法之美!熟悉算法的同学应该感受出来了,上面这个算法就是类 LRU 算法,用于淘汰最近最久使用的元素的场景,该算法应用范围很广的,操作系统、Redis、MySQL 都有使用该算法。
手撕 LRU 算法
在很多大厂面试的时候,经常会考察 LRU 算法,甚至会要求手写出来,之前就有朋友在面试鹅厂的时候,当初就要手写 LRU 算法。今天,就带大家用 C 语言手撕 LRU 算法,我们就采用上面讨论的「哈希表 双向链表」这两个数据结构来实现该算法。为了要实现 LRU 算法, 链表的队头要保持是最近访问或者新加入的数据,链表的队尾要保持是最久未被访问的,这样我们在淘汰最久未访问的时候会很简单,然后哈希表用于快速查找节点。双向链表,存放的内容是键值对。typedef std::pair<int key, std::string value> Pair;
typedef std::list List;
哈希表,存放的是链表节点。typedef std::map<int key, typename List::iterator> Map;
知道了数据结构后,然后实现两个函数,分别是 put
用于加入数据,get
用户获取数据,我这里定义了个 LRUCache
模板类,如下:接下来,看看存放数据的 put
方法实现的方式,如下:说一下 put 方法的实现思路。首先,通过哈希表查找是否存在该 Key:- 如果存在则表示有老数据,那么就需要将老数据先从链表和哈希表里删除,然后再将新的数据重新加入到链表的队头,同时该链表节点存放到哈希表里,这样链表里就维护了该 key 数据是最热的。
- 如果哈希表不存在该 Key,则认为是新的数据,直接将其加入到链表的队头,并把该链表节点更新到哈希表里。
get
方法的实现方式,如下:首先先在哈希表中查找是否存在该 key:- 如果不存在,则返回 false;
- 如果存在,则链表要将数据删除,然后再数据加入到链表队头,目的是为了维持链表队头是最近访问的数据。
3
的 LRUCache 对象,然后使用 put 函数加入 3 组 key-value,这时链表的顺序是 key:3(队头) -> key:2 -> key:1(队尾)。然后通过 get 访问 key:1
的元素,这时链表的顺序变为 key:1(队头) -> key:3 -> key:2(队尾)。接着,put 加入 key:4
元素,由于链表的大小超过了定义的 LRUCache 的容量,于是就会移除队尾的元素,也就是 key:2
。最后看到,就无法访问 key:2 元素的了,运行结果如下。好了,LRU 算法手撕就到了啦。我是小林,今天你比昨天更博学了吗?