LRU，Least Recently Used的缩写，即“最近最少使用”，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。这里，我们基于 LeetCode 146. LRU 缓存 ，使用Golang实现，并使其Get、Put操作的时间复杂度均为O(1)。

思路很简单，使用HashMap保存Cache，保证其Get的复杂度为O(1)，使用一个双向链表，保证Put操作维护使用顺序时的时间复杂度为O(1)。

  • Get

    • key存在

      • 将节点移至最前面
      • 返回value

    • key不存在

      • 返回不存在

  • Put

    • Key存在

      • 将节点移至最前面
      • 更新Value

    • Key不存在

      • 长度未到上限

        • 直接将节点放至最前面

      • 长度打到上限

        • 删除最后面的节点
        • 将节点放到最前面

代码实现：

package lru

type LRUCache struct {
    cache map[int]*LRUNode    // 保存cache的hashMap
    cap   int                // 容量
    head  *LRUNode             // 虚拟头节点
    end   *LRUNode             // 虚拟尾结点
}

// 双向链表节点
type LRUNode struct {
    key   int            // Key
    value int            // Value
    pre   *LRUNode        // 前节点
    next  *LRUNode        // 后节点
}

// 初始化
func Constructor(capacity int) LRUCache {
    cache := LRUCache{
        cache: make(map[int]*LRUNode),
        cap:   capacity,
        head:  newLRUNode(0, 0),
        end:   newLRUNode(0, 0),
    }
    cache.head.next = cache.end
    cache.end.pre = cache.head
    return cache
}

// Get操作
func (c *LRUCache) Get(key int) int {
    // 查询节点
    node, ok := c.cache[key]
    // 不存在，返回-1
    if !ok {
        return -1
    }
    // 存在，将节点移到前面
    node.removeNode()
    node.moveToHead(c.head)
    return node.value
}

// Put操作
func (c *LRUCache) Put(key int, value int) {
    // 查询节点
    node, ok := c.cache[key]
    // 节点存在，将节点移到前面，并更新节点
    if ok {
        node.removeNode()
        node.moveToHead(c.head)
        node.value = value
        return
    }
    // 节点不存在，需要插入
    node = newLRUNode(key, value)
    // 判断当前长度，若小于容量，直接插入头部
    if len(c.cache) < c.cap {
        c.cache[key] = node
        node.moveToHead(c.head)
        return
    }
    // 大于等于容量，删除尾部并插入到头部
    c.cache[key] = node
    delete(c.cache, c.end.pre.key)
    c.end.pre.removeNode()
    node.moveToHead(c.head)
    return
}

// 创建节点
func newLRUNode(key int, value int) *LRUNode {
    return &LRUNode{
        key:   key,
        value: value,
    }
}

// 节点移除
func (n *LRUNode) removeNode() {
    n.pre.next = n.next
    n.next.pre = n.pre
    n.pre = nil
    n.next = nil
}

// 移到虚拟头节点后面（将节点放到前面）
func (n *LRUNode) moveToHead(head *LRUNode) {
    head.next.pre = n
    n.pre = head
    n.next = head.next
    head.next = n
}

运行结果：

（所以我为什么这样都要水一篇博客）

最后修改：2022 年 11 月 11 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏