golang lru实现

时间：2023-05-19 12:00

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

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

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

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

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

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 方法来实现数据的访问和存储。

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实现的详细内容，更多请关注Gxl网其它相关文章！