面试中算法（LRU算法）

短命女 2024-05-28 10:15 89阅读 0赞

### 一、问题需求： ###

某公司的业务越来越复杂，我们需要抽出一个用户系统，向各个业务系统提供 用户的基本信息。 业务方对用户信息的查询频率很高，一定要注意性能问题哦！

![6eb757e28699409e8e6ac9fe4b6171cd.png][]

第一种：可以使用数据库的方式，但要求性能比较高，不符合。

第二种：在内存中创建一个哈希表作为缓存，当查找一个用户时先在哈希表中进行查询，以提高访问效率。

![d1345dbe94ba459884c2b5b6264f75d4.png][]

> 服务器宕机，是内存溢出了，用户数量越来越多，当初设计的哈希表把内存给撑爆了！
> 
> （1）再购买几台服务器，但是无money。
> 
> （2）能否删除一半用户缓存，但会影响系统性能问题。
> 
> （3）使用LRU算法来解决

### 二、LRU是什么 ###

LRU全称Least Recently Used，也就是最近**最少使用的**意思，是一种内存管理算法，该算法最早应用于Linux操作系统。

> 这个算法基于一种假设:长期不被使用的数据，在未来被用到的概率也不大。因此，当数据所占内存达到一定阈值时，我们要移除最近最少被使用的数据。

在LRU算法中，使用了一种有趣的数据结构，这种数据结构叫作**哈希链表**。

> 什么是哈希链表呢?

哈希表是由若干个Key-Value组成的。在“逻辑”上，这些Key-Value是无所谓排列顺序的，谁先谁后都一样。

![411ae52efccc45ab9374ab1e28f75f2b.png][]

在哈希链表中，这些Key-Value不再是彼此无关的了，而是被一个链条串了起来。每一个Key-Value都具有它的前驱Key-Value、后继Key-Value，就像双向链表中的节点一样。

![0e2901d60a3448b28ae135dfc3617614.png][]

这样一来，原本无序的哈希表就拥有了固定的排列顺序。

> 这哈希链表和LRU算法有什么关系呢?
> 
> 依靠哈希链表的有序性，我们可以把Key-Value按照最后的使用时间进行排序。

### **三、LRU算法的基本思路** ###

1、如果使用哈希链表来缓存用户信息，目前缓存了4个用户，这4个用户是按照被访问的时间顺序依次从链表右端插入的。

![f52e060bd1144dc78cf4b814716f46a6.png][]

2、如果访问用户5，由于哈希表中没有用户5，需要从数据库中读取，再插入缓存中。此时，链表最右端是最新被访问的用户5，最左端是最近最少被访问的用户1。

![a0c6a205f2054cd8a9e140c3904c6895.png][]

3、如果访问用户2，哈希链表中已经存在用户2，这时我们把用户2从它的前驱节点和后继节点之间移除，重新插入链表的最右端。此时，链表的最右端变成了最新被访问的用户2，最左端仍然是最近最少被访问的用户1。

![83c1b5dc5d5f473e8d75e20c8adf2118.png][]

4、如果修改用户4的信息。同样的道理，我们会把用户4从原来的位置移动到链表的最右侧，并把用户信息的值更新。这时，链表的最右端是最新被访问的用 4，最左端仍然是最近最少被访问的用户1。

![727994d26ad049c1833d536f5c755614.png][]

![73b9fdbb65124a338bbcc7445f9148b2.png][]

5、如果要访问用户6，用户6在缓存里没有，需要插入哈希链表中。**假设这时缓存容量已经达到上限，必须先删除最近最少被访问的数据**，那么位于哈希链表最左端的用户1就会被删除，然后再把用户6插入最右端的位置。

![7ddf954b2a7540eaa71774fe1a07b7d7.png][]

### **四、编码实现**  ###

class Node:
        def __init__(self,key,value):
            '''初始化数据'''
            self.key=key
            self.value=value
            #前一个节点
            self.pre=None
            #下一个节点
            self.next=None
    
    
    class HashCache:
        def __init__(self,limit):
            '''初始化数据，上限，哈希表，头节点，尾节点'''
            self.limit=limit
            self.hash={}
            self.head=None
            self.foot=None
    
        def add_node(self,node):
            '''添加节点'''
            #判断尾节点不为空
            if self.foot is not None:
                self.foot.next=node
                node.pre=self.foot
                node.next=None
            self.foot=node
            # 判断头节点为空
            if self.head is None:
                  self.head=node
    
        def remove_node(self,node):
            '''哈希表删除节点'''
            if node==self.head and node==self.foot:
                #移除唯一的节点
                self.head=None
                self.foot=None
            elif node==self.foot:
                #移除尾节点
                self.foot=self.foot.pre
                self.foot.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.pre
            return node.key
    
    
        def remove(self,key):
            '''删除节点'''
            node=self.hash.get(key)
            #删除节点
            self.remove_node(node)
            # 从哈希表中删除
            self.hash.remove(key)
    
        def refresh_node(self,node):
            '''刷新节点'''
            #如果访问的是尾节点，不移动
            if node==self.foot:
                return
            #移除节点
            self.remove_node(node)
            #重新添加节点
            self.add_node(node)
    
        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:
              #（1）判断如果超出上限，就移除
              if len(self.hash)>=self.limit:
                 old_key=self.remove_node(self.head)
                 #哈希表同时删除
                 self.hash.pop(old_key)
              #（2） 如果不存在，则添加key-value
              node=Node(key,value)
              self.add_node(node)
              self.hash[key]=node
            else:
                 #如果存在修改值，属性key-value
                 node.value=value
                 #刷新
                 self.refresh_node(node)
    
    
    if __name__ == '__main__':
        hc=HashCache(4)
        hc.put("001","用户1信息")
        hc.put("002","用户2信息")
        hc.put("003","用户3信息")
        hc.put("004","用户4信息")
        hc.put("005","用户5信息")
        print(hc.get("002"))
        hc.put("004", "用户4信息-modify")
        hc.put("006", "用户6信息")
        print(hc.get("001"))  #移除001用户
        print(hc.get("004"))  #显示修改后004用户
        print(hc.get("006"))  #显示用户6

![75d53afabe35442da81bed225732496b.png][]

[6eb757e28699409e8e6ac9fe4b6171cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/e399233e50b648a8bf3db7b8d55d0291.png
[d1345dbe94ba459884c2b5b6264f75d4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/ca76a2a879164c0da8293b6741e2a2ea.png
[411ae52efccc45ab9374ab1e28f75f2b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/2a19ebd9f95e4fe09be8f0db28a05f21.png
[0e2901d60a3448b28ae135dfc3617614.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/5bfae506e8c147f2abc32c69dd8e675e.png
[f52e060bd1144dc78cf4b814716f46a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/a307ce9b34d34c3299ddd96368dd0487.png
[a0c6a205f2054cd8a9e140c3904c6895.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/43597eb16ef84c299444f3ec4bebbbfc.png
[83c1b5dc5d5f473e8d75e20c8adf2118.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/e08f820d946d4dcc8d7308afe1143c14.png
[727994d26ad049c1833d536f5c755614.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/b9e02e0837b744cc9109e04d0f92161b.png
[73b9fdbb65124a338bbcc7445f9148b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/9b31210edab543038e77f76c685f0691.png
[7ddf954b2a7540eaa71774fe1a07b7d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/fecd5a7be4c74a93a8d2812f22c500b9.png
[75d53afabe35442da81bed225732496b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/663d8b1abc69439386a2cf3f025aee57.png