如何实现LRU缓存?

面试官:来了,老弟,LRU缓存实现一下?

我:直接LinkedHashMap就好了。

面试官:不要用现有的实现,自己实现一个。

我:.....

面试官:回去等消息吧....


大家好,我是程序员学长,今天我们来聊一聊LRU缓存的问题。

Tips: LRU在计算机软件中无处不在,希望大家一定要了解透彻。

问题描述

设计LRU(最近最少使用)缓存结构,该结构在构造时确定大小,假设大小为K,并有如下两个功能
1. set(key, value):将记录(key, value)插入该结构
2. get(key):返回key对应的value值

分析问题

根据问题描述,我们可以知道LRU缓存中包含两种操作,即Set和Get操作。

对于Set操作来说,分为两种情况。

  1. 如果缓存中已经存在。把缓存中对应的该元素移动到缓存头部。
  2. 如果缓存中不存在。把该元素添加到缓存头部。此时如果缓存的大小超过限制的大小,需要删除缓存中末尾的元素。

对于Get操作来说,也分为两种情况。

  1. 如果缓存中存在。把缓存中的该元素移动到缓存头部,并返回对应的value值。
  2. 如果缓存中不存在。直接返回-1。

综上所述:对于一个LRU缓存来说,主要包含以下三种操作。

  1. 查找一个元素。
  2. 在缓存末尾删除一个元素。
  3. 在缓存头部添加一个元素。

所以,我们最容易想到的就是使用一个链表来实现LRU缓存。我们可以维护一个有序的单链表,越靠近链表尾部的结点是越早访问的。当我们进行Set操作时,我们从链表头开始顺序遍历。遍历的结果有两种情况。

  1. 如果此数据已经在链表中,我们遍历得到这个数据对应的结点,然后将其从这个位置移动到链表的头部。
  2. 如果此数据不在链表中,又会分为两种情况。如果此时链表没有满,我们直接将该结点插入到链表头部。如果此时链表已经满了,我们从链表尾部删除一个结点,然后将新的数据结点插入到链表头部。

当我们进行Get操作时,我们从链表头开始顺序遍历。遍历的结果有两种情况。

  1. 如果此数据在链表中。我们遍历得到这个数据对应的结点,然后将其从这个位置移动到链表的头部,并返回这个结点对应的value。
  2. 如果此数据不在链表中。我们直接返回-1。

下面我们来看一下代码如何实现。

class LinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.next = None

class LRUCache():
    def __init__(self, capacity: int):
        # 使用伪头部节点
        self.capacity=capacity
        self.head = LinkedNode()
        self.head.next=None
        self.size = 0

    def get(self, key: int) -> int:

        cur=self.head.next
        pre=self.head

        while cur!=None:
            if cur.key==key:
                pre.next = cur.next
                cur.next = self.head.next
                self.head.next = cur
                break
            pre=pre.next
            cur=cur.next

        if cur!=None:
            return cur.value
        else:
            return -1

    def put(self, key: int, value: int) -> None:

        cur = self.head.next
        pre = self.head
        
        #缓存没有元素,直接添加
        if cur==None:
            node = LinkedNode()
            node.key = key
            node.value = value
            self.head.next = node
            self.size = self.size + 1
            return

        #缓存有元素,判断是否存在于缓存中
        while cur!=None:
            #表示已经存在
            if cur.key == key:
                #把该元素反正链表头部
                cur.value=value
                pre.next = cur.next
                cur.next = self.head.next
                self.head.next = cur
                break

            #代表当前元素时最后一个元素
            if cur.next==None:
                #如果此时缓存已经满了,淘汰最后一个元素
                if self.size==self.capacity:
                    pre.next=None
                    self.size=self.size-1
                node=LinkedNode()
                node.key=key
                node.value=value
                node.next=self.head.next
                self.head.next=node
                self.size=self.size+1
                break
                
            pre = pre.next
            cur=cur.next

这样我们就用单链表实现了一个LRU缓存,我们接下来分析一下缓存访问的时间复杂度。对于Set来说,不管缓存有没有满,我们都需要遍历一遍链表,所以时间复杂度是O(n)。对于Get操作来说,也是需要遍历一遍链表,所以时间复杂度也是O(n)。

优化

从上面的分析,我们可以看到。如果用单链表来实现LRU,不论是Set还是Get操作,都需要遍历一遍链表,来查找当前元素是否存在于缓存中,时间复杂度为O(n),那我们可以优化吗?我们知道,使用hash表,我们查找元素的时间复杂度可以减低到O(1),如果我们可以用hash表,来替代上述的查找操作,那不就可以减低时间复杂度吗?根据这个逻辑,所以我们采用hash表和链表的组合方式来实现一个高效的LRU缓存。

class LinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = dict()
        self.head = LinkedNode()
        self.tail = LinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    def get(self, key: int):
        #如果key不存在,直接返回-1
        if key not in self.cache:
            return -1
        #通过hash表定位位置,然后删除,省去遍历查找过程
        node = self.cache[key]
        self.moveHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            # 如果key不存在,创建一个新的节点
            node = LinkedNode(key, value)
            # 添加进哈希表
            self.cache[key] = node
            self.addHead(node)
            self.size += 1
            if self.size > self.capacity:
                # 如果超出容量,删除双向链表的尾部节点
                removed = self.removeTail()
                # 删除哈希表中对应的项
                self.cache.pop(removed.key)
                self.size -= 1
        else:
            node = self.cache[key]
            node.value = value
            self.moveHead(node)

    def addHead(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def moveHead(self, node):
        self.removeNode(node)
        self.addHead(node)

    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

总结

LRU缓存不论在工作中还是面试中,我们都会经常碰到。希望这篇文章能对你有所帮助。

你知道的越多,你的思维也就越开阔,我们下期再见。

上一篇:LRU最近最少使用代码实现


下一篇:Linux 安装python 模块及库