Go语言入门实战-从0到1实现LRU

大家好，我是gopher_looklook，现任某独角兽企业后端开发工程师，喜欢钻研Go源码，发掘各项技术在大型Go微服务项目中的最佳实践，期待与各位牛友多多交流，一起进步！

LRU设计描述

设计和构建一个`最近最少使用(Least Recently Used)缓存，该缓存会删除最近最少使用的元素。缓存应该从键映射到值(允许插入和检索特定键对应的值)，并在初始化时指定最大容量。该缓存应该支持以下操作: 获取数据Get(key)和写入数据Put(key, value)。可以假定缓存元素的键值都是string类型。获取数据时，如果Key存在，则获取其缓存值Value,如果不存在则返回空字符串，并给出exist标识。写入数据时，如果key不存在，则写入其数据值。当缓存容量达到上限时，应该在写入新数据之前删除最近最少使用的元素，从而为新的数据腾出空间。

思路分析

根据题目描述，这是一个新手入门级别的简易LRU实现。题目的关键在于创建一个LRU对象，并为这个对象实现一个Get的方法和Put的方法。这两个方法的函数签名如下：

func (*LRUCache) Get(key string) (string, bool)

对于Get方法，每次调用时需要传入一个key,并返回这个key对应的数据value。如果key不存在，应该给出一个bool标识，表示这个key并没有存在于缓存中。

func (*LRUCache) Put(key string, value string)

对于Put方法，每次调用时，需要传入一个key和一个value。当key已经存在于缓存当中时，则用新value值覆盖旧数据；当key不存在缓存当中时，则将新键值对插入到缓存当中。插入之前，需要识别到缓存是否已经达到最大容量(capacity)。如果达到最大容量，需要先删除掉最近最少使用的元素，腾出空间插入新的键值元素。

流程图

参考代码

lru.go

package lru

// Node 定义双向链表的节点
type Node struct {
    key   string
    value string
    prev  *Node
    next  *Node
}

// LRUCache 定义LRU缓存结构
type LRUCache struct {
    capacity int
    cache    map[string]*Node
    head     *Node
    tail     *Node
}

// NewLRUCache 初始化LRU缓存
func NewLRUCache(capacity int) *LRUCache {
    lru := &LRUCache{
       capacity: capacity,
       cache:    make(map[string]*Node),
       head:     &Node{key: "", value: ""}, // 虚拟头节点
       tail:     &Node{key: "", value: ""}, // 虚拟尾节点
    }
    // 初始化时，头尾节点互相连接
    lru.head.next = lru.tail
    lru.tail.prev = lru.head
    return lru
}

// removeNode 从链表中移除一个节点
func (lru *LRUCache) removeNode(node *Node) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

// addToHead 将节点添加到链表头部
func (lru *LRUCache) addToHead(node *Node) {
    node.prev = lru.head
    node.next = lru.head.next
    lru.head.next.prev = node
    lru.head.next = node
}

// moveToHead 将节点移动到链表头部
func (lru *LRUCache) moveToHead(node *Node) {
    lru.removeNode(node)
    lru.addToHead(node)
}

// removeTail 移除链表尾部的节点
func (lru *LRUCache) removeTail() *Node {
    node := lru.tail.prev
    lru.removeNode(node)
    return node
}

// Get 获取缓存中的值
func (lru *LRUCache) Get(key string) (string, bool) {
    if node, ok := lru.cache[key]; ok {
       lru.moveToHead(node)
       return node.value, true
    }
    return "", false
}

// Put 写入缓存
func (lru *LRUCache) Put(key string, value string) {
    if lru.capacity <= 0 {
       return // 如果容量为0，直接返回
    }

    if node, ok := lru.cache[key]; ok {
       node.value = value
       lru.moveToHead(node)
    } else {
       if len(lru.cache) == lru.capacity {
          tail := lru.removeTail()
          delete(lru.cache, tail.key)
       }
       newNode := &Node{key: key, value: value}
       lru.cache[key] = newNode
       lru.addToHead(newNode)
    }
}

单元测试

lru_test.go

package lru

import (
    "testing"
)

// TestLRUCache 测试LRU缓存的基本功能
func TestLRUCache(t *testing.T) {
    lru := NewLRUCache(2) // 初始化缓存容量为2

    // 测试1: 插入和获取数据
    lru.Put("key1", "value1")
    lru.Put("key2", "value2")

    value, exist := lru.Get("key1")
    if !exist || value != "value1" {
       t.Errorf("Get key1 failed, expected: value1, got: %s", value)
    }

    value, exist = lru.Get("key2")
    if !exist || value != "value2" {
       t.Errorf("Get key2 failed, expected: value2, got: %s", value)
    }

    // 测试2: 插入新数据，触发淘汰
    lru.Put("key3", "value3") // 插入key3，应淘汰key1

    value, exist = lru.Get("key1")
    if exist {
       t.Errorf("Get key1 should fail, but it exists with value: %s", value)
    }

    value, exist = lru.Get("key3")
    if !exist || value != "value3" {
       t.Errorf("Get key3 failed, expected: value3, got: %s", value)
    }

    // 测试3: 更新已存在的数据
    lru.Put("key2", "new_value2") // 更新key2的值
    value, exist = lru.Get("key2")
    if !exist || value != "new_value2" {
       t.Errorf("Get key2 failed, expected: new_value2, got: %s", value)
    }

    // 测试4: 插入新数据，触发淘汰
    lru.Put("key4", "value4") // 插入key4，应淘汰key3

    value, exist = lru.Get("key3")
    if exist {
       t.Errorf("Get key3 should fail, but it exists with value: %s", value)
    }

    value, exist = lru.Get("key4")
    if !exist || value != "value4" {
       t.Errorf("Get key4 failed, expected: value4, got: %s", value)
    }
}

// TestLRUCacheEdgeCases 测试LRU缓存的边界情况
func TestLRUCacheEdgeCases(t *testing.T) {
    // 测试1: 缓存容量为0
    lru := NewLRUCache(0)
    lru.Put("key1", "value1")
    value, exist := lru.Get("key1")
    if exist {
       t.Errorf("Get key1 should fail for zero capacity cache, but it exists with value: %s", value)
    }

    // 测试2: 缓存容量为1
    lru = NewLRUCache(1)
    lru.Put("key1", "value1")
    value, exist = lru.Get("key1")
    if !exist || value != "value1" {
       t.Errorf("Get key1 failed, expected: value1, got: %s", value)
    }

    lru.Put("key2", "value2") // 插入key2，应淘汰key1
    value, exist = lru.Get("key1")
    if exist {
       t.Errorf("Get key1 should fail, but it exists with value: %s", value)
    }

    value, exist = lru.Get("key2")
    if !exist || value != "value2" {
       t.Errorf("Get key2 failed, expected: value2, got: %s", value)
    }
}