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中文网其他相关文章!