首页  >  文章  >  后端开发  >  golang lru实现

golang lru实现

王林
王林原创
2023-05-19 10:16:37617浏览

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实现的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
上一篇:golang整型除法下一篇:广州golang需求