本文转载自微信公众号“小林编码”，作者小林编码。转载本文请联系小林编码公众号。大家好，我是小林。前几天写了一篇计算机基础之美：坚持一年，介绍了心跳服务宕机判断算法。当时只是理论分析使用LRU算法实现，没有撕代码。今天带大家手撕LRU算法，先让大家回顾一下案例，后面再讲解代码。宕机判断算法设计心跳服务主要做两件事：发现宕机的主机；发现在线的主机。这个心跳服务的关键是判断宕机的算法。如果使用暴力遍历所有主机来寻找超时的主机，面对只有几百台主机是没有问题的，但是这个算法会随着主机数量的增加而增加，程序的性能也会减少。会急剧下降。因此，我们应该设计一种能够应对超大集群规模的宕机判断算法。我们先想一想，心跳包要管理什么数据结构呢？心跳包中的内容有主机上报的时间信息，也就是有时间关系，所以可以用“双向链表”组成一个先进先出的队列，这样定时心跳包的关系被保留。由于采用的数据结构是双向链表，所以在队尾插入和在队头删除的时间复杂度为O(1)。如果有新的心跳包，就插入到双向链表的尾部，那么最旧的心跳包就在双向链表的头部，所以找宕机的主机时，只要看最老的心跳包在双向链表头部的Packet，是否距离现在超过5秒，如果超过5秒，则认为主机宕机，然后将其从双向链表中删除。细心的同学一定发现了一个问题，就是如果某个主机的心跳包已经在队列中了，那么下次该主机的心跳包怎么处理呢？为了保持队列中的心跳包是主机的最新报告，所以先找到主机旧的心跳包，将其删除，将新的心跳包插入到双向链表的尾部。问题是在队列中发现了主机的旧心跳包。由于数据结构是双向链表，所以这个查询过程的时间复杂度是O(N)。也就是说，队列中的元素越多，对程序性能的影响就越大，我们必须优化这个。查询效率最好的数据结构是“哈希表”，时间复杂度只有O(1)，所以我们可以加入这个数据结构进行优化。哈希表的Key是主机的IP地址，Value包含主机在双向链表中的节点，这样我们就可以很容易的通过哈希表找到主机在双向链表中的位置。这样，每当收到一个心跳包时，首先判断它是否在哈希表中。如果哈希表中不存在，说明有新主机上线，先插入到双向链表的尾部，然后以主机的IP为Key，将主机的节点插入到双向链表中链表作为Value放入哈希表中。如果在哈希表中存在，则说明该主机已经上线。首先通过查询哈希表，在双向链表中找到主机旧心跳包的节点，然后通过这个节点从双向链表中删除，最后从双向链表中删除。新的心跳包插入到双向链表的尾部，同时更新哈希表。可以看出，以上操作都是O(1)。不管集群有多大，时间复杂度都不会增加，但是代价就是内存占用会增加。这就是用空间换取时间的方式。有一个详细的问题。不知道你有没有发现。为什么队列的数据结构使用双向链表而不是单向链表？因为双向链表比单向链表多了一个前置指针，所以可以用它来查找前一个节点。,那么在删除中间节点的时候直接删除就可以了,如果删除中间的时候是单向链表的话,我们还得遍历找到要删除的节点的前一个节点才能完成删除操作,中间有太多遍历操作。既然引入了哈希表，那么当我们判断某台主机宕机时（查看双向链表头部的主机是否超时），除了从双向链表中删除外，还必须将其删除从哈希表。要从哈希表中删除主机，首先我们需要知道主机的IP，因为这是哈希表的键。双向链表中存储的内容必须包含主机的IP信息。为了更快查询主机IP，双向链表中存储的内容可以是键值对（Key-Value），其中Key为主机IP，Value为主机信息。这样当发现双向链表头部的节点超时时，由于该节点的内容是键值对，可以快速从该节点获取主机的IP，并且可以从哈希表中获取主机的IP信息。主机信息被删除。至此，设计了一个高性能的宕机判断算法，主要使用数据结构：哈希表+双向链表。通过这种组合，查询+删除+插入操作的时间复杂度为O(1)。以空间换时间的思想，这就是数据结构和算法的美妙之处！熟悉算法的同学应该能感觉到。上面的算法是一个LRU-like算法，用来剔除最近和使用时间最长的元素。该算法应用广泛，操作系统、Redis、MySQL都采用该算法。手撕LRU算法在很多大厂面试的时候，经常会考察LRU算法，甚至要求手撕出来。之前有小伙伴在面试鹅厂的时候不得不手写LRU算法。今天就带大家用C++语言手撕LRU算法。我们将使用上面讨论的两种数据结构“哈希表+双向链表”来实现算法。为了实现LRU算法，链表的头部必须是最近访问过或新加入的数据，而链表的尾部必须保持最长未访问过的，这样我们剔除就会很简单longestunvisited，然后使用哈希表快速查找节点。双向链表存储键值对。typedefstd::pair
