golang lru实现-Golang-PHP中文网

golang lru实现

王林

发布： 2023-05-19 10:16:37

原创

513人浏览过

lru（least recently used）算法是一种常见的缓存替换策略。在缓存达到预设上限时，缓存会自动淘汰最近最少使用的数据，以释放出空间。

在 Golang 中，我们可以使用双向链表和哈希表来实现 LRU 缓存。在本文中，我们将介绍如何使用这两种数据结构实现 LRU 缓存。

双向链表的作用在于维护缓存的数据顺序，每次插入新数据或者访问数据时，都将对该数据进行提前。同时，在缓存达到上限时，我们可以从链表的末端删除最近最少使用的数据。

哈希表的作用在于加速数据的查找，每次进行数据访问时，通过哈希表中存储的数据索引，我们可以快速地查找到相应的缓存数据。因此，我们将在实现过程中对哈希表进行操作。

接下来，我们将讲解如何实现基于双向链表和哈希表的 LRU 缓存。我们定义一个 LRUCache 结构体，并声明链表头和链表尾指针，以及哈希表 map 和缓存容量 capacity。

立即学习“go语言免费学习笔记（深入）”；

type LRUCache struct {
    head, tail *entry  // 链表头和链表尾指针
    cache      map[int]*entry  // 哈希表存储缓存中的数据
    capacity   int     // 缓存容量
}

登录后复制

接下来，我们将定义双向链表节点的结构体。

type entry struct {
    key, value int        // 存储节点的键值对
    prev, next *entry    // 前驱和后继指针
}

登录后复制

这里，我们使用 prev 和 next 分别表示节点的前驱和后继指针，key 和 value 分别表示该节点的键值对。

接下来，我们将定义 LRUCache 的构造函数 NewLRUCache，并传入缓存容量 capacity。

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        cache:    make(map[int]*entry),
        capacity: capacity,
    }
}

登录后复制

在构造函数中，我们将初始化哈希表和缓存容量。

接下来，我们将定义 LRUCache 的 Get 和 Put 方法来实现数据的访问和存储。

VisualizeAI

用AI把你的想法变成现实

查看详情

Get 方法的实现：

func (c *LRUCache) Get(key int) int {
    if elem, ok := c.cache[key]; ok {
        // 更新节点位置
        c.moveToHead(elem)
        return elem.value
    }
    return -1
}

登录后复制

首先，我们从哈希表中查找是否存在相应的数据，如果存在，则将节点移到链表的头部，并返回节点存储的值。否则，返回 -1。

下面是 moveToHead 方法的实现：

func (c *LRUCache) moveToHead(elem *entry) {
    if elem == c.head {
        return
    } else if elem == c.tail {
        c.tail = elem.prev
    } else {
        elem.prev.next = elem.next
        elem.next.prev = elem.prev
    }

    elem.prev = nil
    elem.next = c.head
    c.head.prev = elem
    c.head = elem
}

登录后复制

该方法接收一个节点指针 elem，用于将该节点移到链表头部。首先，如果该节点已经是链表头部，则返回；否则，如果该节点是链表尾部，则更新链表尾部指针 tail；否则，将该节点从链表中删除，并将该节点放到链表头部。

Put 方法的实现：

func (c *LRUCache) Put(key, value int) {
    if elem, ok := c.cache[key]; ok {
        elem.value = value
        c.moveToHead(elem)
    } else {
        // 创建新节点
        elem := &entry{key: key, value: value}
        c.cache[key] = elem
        if c.head == nil {
            c.head = elem
            c.tail = elem
        } else {
            // 在链表头部插入新节点
            elem.next = c.head
            c.head.prev = elem
            c.head = elem
        }
        // 判断缓存是否达到预设上限
        if len(c.cache) > c.capacity {
            // 删除链表尾部节点和哈希表中的数据
            delete(c.cache, c.tail.key)
            c.tail = c.tail.prev
            c.tail.next = nil
        }
    }
}

登录后复制

首先，我们从哈希表中查找是否存在相应的数据，如果存在，则更新节点存储的值，并调用 moveToHead 方法将该节点移到链表的头部。否则，创建一个新的节点，并将该节点插入到链表的头部。如果缓存达到预设上限，则删除链表的尾部节点和哈希表中的数据。

最后，我们将完整的代码整合到一起：

type LRUCache struct {
    head, tail *entry
    cache      map[int]*entry
    capacity   int
}

type entry struct {
    key, value int
    prev, next *entry
}

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        cache:    make(map[int]*entry),
        capacity: capacity,
    }
}

func (c *LRUCache) Get(key int) int {
    if elem, ok := c.cache[key]; ok {
        // 更新节点位置
        c.moveToHead(elem)
        return elem.value
    }
    return -1
}

func (c *LRUCache) moveToHead(elem *entry) {
    if elem == c.head {
        return
    } else if elem == c.tail {
        c.tail = elem.prev
    } else {
        elem.prev.next = elem.next
        elem.next.prev = elem.prev
    }

    elem.prev = nil
    elem.next = c.head
    c.head.prev = elem
    c.head = elem
}

func (c *LRUCache) Put(key, value int) {
    if elem, ok := c.cache[key]; ok {
        elem.value = value
        c.moveToHead(elem)
    } else {
        // 创建新节点
        elem := &entry{key: key, value: value}
        c.cache[key] = elem
        if c.head == nil {
            c.head = elem
            c.tail = elem
        } else {
            // 在链表头部插入新节点
            elem.next = c.head
            c.head.prev = elem
            c.head = elem
        }
        // 判断缓存是否达到预设上限
        if len(c.cache) > c.capacity {
            // 删除链表尾部节点和哈希表中的数据
            delete(c.cache, c.tail.key)
            c.tail = c.tail.prev
            c.tail.next = nil
        }
    }
}

登录后复制

在本文中，我们已经介绍了如何使用双向链表和哈希表来实现 LRU 缓存算法。通过这种算法的实现，我们可以有效地管理缓存，优化数据的访问效率。

以上就是golang lru实现的详细内容，更多请关注php中文网其它相关文章！