lru golang 算法

admin

0
文章

0
评论

2024-10-16 21:32:20 编程来源：ZONE.CI 全球网 0 阅读模式

LRU算法的实现

LRU（Least Recently Used）算法是一种常用的缓存淘汰策略，它的核心思想是将最近不常访问的数据淘汰出缓存空间，从而为新的数据腾出位置。在Go语言中，我们可以使用双向链表和哈希表来实现LRU算法。

双向链表的实现

双向链表是一种特殊的链表结构，每个节点包含指向前一个节点和后一个节点的指针。在LRU算法中，我们可以使用双向链表来维护被访问的数据的顺序。

首先，我们需要定义一个双向链表节点的结构体：

type Node struct {
    key   int
    value int
    prev  *Node
    next  *Node
}

然后，我们可以定义一个LRU缓存的数据结构，其中包含双向链表的头节点和尾节点：

type LRUCache struct {
    capacity int
    size     int
    cache    map[int]*Node
    head     *Node
    tail     *Node
}

LRUCache结构体中的cache字段是一个哈希表，用于快速定位数据在链表中的位置。head字段和tail字段分别指向链表的头节点和尾节点。

LRU算法的实现

在LRUCache结构体中，我们可以定义一些方法来实现LRU算法的逻辑。

首先，我们需要一个方法来将数据插入到缓存中：

func (c *LRUCache) put(key int, value int) {
    // 如果缓存中已经存在该数据
    if node, ok := c.cache[key]; ok {
        node.value = value
        c.moveToHead(node)
    } else {
        node := &Node{key: key, value: value}
        c.cache[key] = node
        c.addToHead(node)
        
        // 如果缓存已满，移除尾节点
        if c.size >= c.capacity {
            removed := c.removeTail()
            delete(c.cache, removed.key)
        } else {
            c.size++
        }
    }
}

put方法首先判断数据是否已经存在于缓存中，如果存在，则更新该数据的值，并将其移动到链表的头部；否则，创建一个新的节点，并将其添加到链表的头部。如果缓存已满，会将链表的尾节点移除，并从哈希表中删除相应的键值对。

其次，我们需要一个方法来获取数据：

func (c *LRUCache) get(key int) int {
    if node, ok := c.cache[key]; ok {
        c.moveToHead(node)
        return node.value
    } else {
        return -1
    }
}

get方法首先判断数据是否存在于缓存中，如果存在，则将其移动到链表的头部，并返回该数据的值；否则，返回-1。