Go 中使用 map 实现高效的数据缓存

在 Go 语言中,使用 map 结合 LRU(Least Recently Used) 缓存算法,可以实现高效的数据缓存。以下是一个示例实现:

import (
    "container/list"
    "sync"
)

type Cache struct {
   
    capacity int
    mu       sync.Mutex
    list     *list.List
    m        map[string]*list.Element
}

type entry struct {
   
    key   string
    value interface{
   }
}

func NewCache(capacity int) *Cache {
   
    return &Cache{
   
        capacity: capacity,
        list:     list.New(),
        m:        make(map[string]*list.Element, capacity),
    }
}

func (c *Cache) Get(key string) (value interface{
   }, ok bool) {
   
    c.mu.Lock()
    defer c.mu.Unlock()

    if elem, ok := c.m[key]; ok {
   
        c.list.MoveToFront(elem)
        return elem.Value.(*entry).value, true
    }
    return nil, false
}

func (c *Cache) Put(key string, value interface{
   }) {
   
    c.mu.Lock()
    defer c.mu.Unlock()

    if elem, ok := c.m[key]; ok {
   
        c.list.MoveToFront(elem)
        elem.Value.(*entry).value = value
        return
    }

    if c.list.Len() == c.capacity {
   
        old := c.list.Back()
        c.list.Remove(old)
        delete(c.m, old.Value.(*entry).key)
    }

    elem := c.list.PushFront(&entry{
   key, value})
    c.m[key] = elem
}

这个缓存实现使用了 sync.Mutex 来确保线程安全,并使用 container/list 包中的双向链表来维护 LRU 顺序。

主要流程如下:

1. Get(key) 方法先获取读锁,然后在 map 中查找键对应的值。如果找到,则将对应的链表节点移到链表头部,并返回值。
2. Put(key, value) 方法先获取写锁,然后在 map 中查找键是否存在:
   • 如果存在,则将对应的链表节点移到链表头部,并更新值。
   • 如果不存在且缓存已满,则删除链表末尾的节点及其在 map 中的记录,然后添加新的节点到链表头部。

这种结构可以提供 O(1) 时间复杂度的 Get 和 Put 操作,并能自动淘汰最久未使用的数据,非常适用于缓存场景。

此外,您也可以使用 Go 标准库中的 sync.Map 类型,它自带了并发安全的 Load、Store 和 Delete 方法,从而无需自行实现锁机制。