Go语言实现LRU算法的核心思想和实现过程
简介
LRU (Least Recently Used)是一种常见的缓存淘汰策略,即当缓存空间已满时,把最近最少使用的元素先淘汰掉,以此来保证缓存空间的有效利用。本文将讲述如何使用Go语言来实现LRU算法的核心思想和实现过程。
核心思想
LRU算法的核心思想是基于链表+哈希表的组合实现。具体来说,我们可以维护一个双向链表和一个哈希表,链表中每个节点维护缓存中的一个元素,链表头节点表示最近使用的元素,链表尾节点表示最久未使用的元素。哈希表中的key存储元素的键,value存储链表节点的指针,表示元素在链表中的位置。
当有新的元素加入缓存时,我们需要做以下操作:
- 先去哈希表中查找该元素是否已经在缓存中。
- 如果不在缓存中,需要新建一个链表节点,并将其加入到链表头,同时将元素键和节点指针存入哈希表中。
- 如果已经在缓存中,需要将元素所对应的节点移动到链表头。
当缓存满了需要淘汰元素时,我们需要将链表尾部的节点(即最久未使用的元素)从链表中删除,并将其在哈希表中的记录一并删除。
实现过程
具体来看,我们需要定义如下两个结构体:
type node struct {
key, val int
prev, next *node
}
type LRUCache struct {
capacity int
size int
head, tail *node
cache map[int]*node
}
其中,node表示链表节点,包含元素的键值、前驱指针和后继指针。LRUCache表示整个LRU缓存,包含缓存容量、当前缓存大小、链表头、链表尾和哈希表cache。
新建一个LRUCache对象时,首先需要初始化链表头和链表尾,并将其都指向同一个空节点。同时,需要初始化哈希表。
func Constructor(capacity int) LRUCache {
head, tail := &node{0, 0, nil, nil}, &node{0, 0, nil, nil}
head.next, tail.prev = tail, head
return LRUCache{
capacity: capacity,
head: head,
tail: tail,
cache: make(map[int]*node),
}
}
接下来,我们需要实现以下几个方法:
get方法
根据元素的键获取元素的值。如果键不存在则返回-1。
该方法的实现过程如下:
- 先去哈希表中查找元素。
- 如果找不到则返回-1。
- 如果找到了,将元素所对应的节点移动到链表头,然后返回元素的值。
func (lru *LRUCache) get(key int) int {
if node, ok := lru.cache[key]; ok {
lru.moveToHead(node)
return node.val
}
return -1
}
put方法
将一个元素插入LRU缓存。如果元素的键已存在则更新其值,否则插入新元素。如果缓存满了就淘汰最久未使用的元素。
该方法的实现过程如下:
- 先去哈希表中查找元素。
- 如果找到了,则更新元素的值,并将元素所对应的节点移动到链表头即可。
- 如果没找到,则新建一个节点,并将该节点插入到链表头和哈希表中。
- 如果插入新元素后缓存已满,则需要淘汰最久未使用的元素。先删除链表尾部的节点,再在哈希表中删除对应的记录即可。
func (lru *LRUCache) put(key, value int) {
if node, ok := lru.cache[key]; ok {
node.val = value
lru.moveToHead(node)
} else {
node := &node{key: key, val: value}
lru.cache[key] = node
lru.addToHead(node)
lru.size++
if lru.size > lru.capacity {
removed := lru.removeTail()
delete(lru.cache, removed.key)
lru.size--
}
}
}
moveToHead方法
将指定的节点移动到链表头。
func (lru *LRUCache) moveToHead(node *node) {
lru.removeNode(node)
lru.addToHead(node)
}
removeNode方法
从双向链表中删除指定节点。
func (lru *LRUCache) removeNode(node *node) {
node.prev.next = node.next
node.next.prev = node.prev
}
addToHead方法
将指定节点添加到双向链表的头部。
func (lru *LRUCache) addToHead(node *node) {
node.prev = lru.head
node.next = lru.head.next
lru.head.next.prev = node
lru.head.next = node
}
removeTail方法
从双向链表中删除最久未使用的节点(即链表尾节点)。
func (lru *LRUCache) removeTail() *node {
node := lru.tail.prev
lru.removeNode(node)
return node
}
示例说明
我们可以使用如下代码测试该LRU算法实现的正确性:
func main() {
lru := Constructor(2)
lru.put(1, 1)
lru.put(2, 2)
fmt.Println(lru.get(1)) // 输出1
lru.put(3, 3)
fmt.Println(lru.get(2)) // 输出-1
lru.put(4, 4)
fmt.Println(lru.get(1)) // 输出-1
fmt.Println(lru.get(3)) // 输出3
fmt.Println(lru.get(4)) // 输出4
}
该示例代码中,我们新建了一个缓存容量为2的LRUCache对象,并不断插入和查询元素。最终输出的结果符合预期,证明该LRU算法的实现过程是正确的。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Go语言实现LRU算法的核心思想和实现过程 - Python技术站