作者：沈熠辉

来源：恒生LIGHT云社区

Redis使用场景

现在公司的业务越来越复杂，我们需要抽出一个用户系统，向各个业务系统提供用户的基本信息。

业务方对用户信息的查询频率很高，一定要注意性能问题哦。

用户信息当然是存放在数据库里，但是由于我们对用户系统的性能要求比较高，显然不能在每一次请求时都去查询数据库。

所以，在内存中创建了一个哈希表作为缓存，每当查找一个用户时会先在哈希表中进行查询，以此来提高访问的性能。

很快发现了个问题

线上服务器宕机了！

糟了，是内存溢出了，用户数量越来越多，当初设计的哈希表把内存给撑爆了，赶紧重启吧！

可是以后该怎么办呢？我们能不能给服务器的硬件升级，或者加几台服务器呀？

那我能不能在内存快耗尽的时候，随机删掉一半用户缓存呢？

唉，这样也不妥，如果删掉的用户信息，正好是被高频查询的用户，会影响系统性能的。

你听说过LRU算法吗？

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

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

原来如此，这个算法正好对我的用户系统有帮助！可以在内存不够时，从哈希表中移除一部分很少被访问的用户。

可是，我怎么知道哈希表中哪些Key-Value最近被访问过，哪些没被访问过？总不能给每一个Value加上时间戳，然后遍历整个哈希表吧？

这就能展现LRU算法的精妙所在了。在LRU算法中，使用了一种有趣的数据结构，这种数据结构叫作哈希链表。

什么是哈希链表呢？

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

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

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

可是，这哈希链表和LRU算法有什么关系呢？

依靠哈希链表的有序性，我们可以把Key-Value按照最后的使用时间进行排序。

让我们以用户信息的需求为例，来演示一下LRU算法的基本思路。

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

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

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

以上，就是LRU算法的基本思路。

明白了，这真是个巧妙的算法！那么LRU算法怎么用代码来实现呢？

简单实现

class LRUCache:
    def __init__(self,limit):
        self.limit=limit
        self.hash={}
        self.head=None
        self.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 remove(self,key):
        node=self.hash.get(key)
        self.remove_node(node)
        self.hash.remove(key)
    def refresh_node(self,node):
        #如果访问的是尾节点,无需移动节点
        if node==self.end:
           return
        #移除节点
        self.remove_node(node)
        #重新插入节点
        self.add_node(node)
    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.pre
        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
​
class Node:
    def __init__(self,key,value):
        self.key=key
        self.value=value
        self.pre=None
        self.next=None
​
lruCache=LRUCache(5)
​
lruCache.put("001","用户1信息")
lruCache.put("002","用户2信息")
lruCache.put("003","用户3信息")
lruCache.put("004","用户4信息")
lruCache.put("005","用户5信息")
​
print(lruCache.get("002"))