package LRU
import "fmt"
// LRU represent Least Recently Used strategy
// means
// cap 固定的双向链表
// 每次插入均在头部,已经存在的元素则更新元素结点并移至头部,不存在则新建结点插入,超容则删掉最后一个结点
// 每次查询则移动待查元素到头部(更新使用频率) 不存在
type Node struct {
prev, next *Node
// 代表当前 LRU 的归属
list *LRU
key string
value interface{}
}
type LRU struct {
root *Node
cap int
len int
}
func NewLRU(cap int) *LRU {
l := &LRU{
root: &Node{},
cap: cap,
}
l.root.prev = l.root
l.root.next = l.root
l.root.list = l
return l
}
// Get 获得缓存数据
// 获取到则将该节点移动至链表头部
// 为获取到则 nil
func (l *LRU) Get(key string) interface{} {
defer l.debug()
n := l.get(key)
if n == nil {
return nil
}
return n.value
}
func (l *LRU) get(key string) *Node {
for n := l.root.next; n != l.root; n = n.next {
if n.key == key {
n.prev.next = n.next
n.next.prev = n.prev
n.next = l.root.next
l.root.next.prev = n
l.root.next = n
n.prev = l.root
return n
}
}
return nil
}
// 将 key 构造为结点插入头部,若存在对应的 key 则更新结点值
// 缓存满则删掉最后结点(LRU)最少使用
func (l *LRU) Put(key string, value interface{}) {
defer l.debug()
n := l.get(key)
if n != nil {
n.value = value
return
}
// 缓存 cap 满
// delete the last node and l.len--
if l.len == l.cap {
last := l.root.prev
last.prev.next = l.root
l.root.prev = last.prev
last.prev = nil
last.next = nil
last.list = nil
l.len--
}
// construct newNode to insert the head of the list
// update the l.len and newNode'list
node := &Node{
key: key,
value: value,
}
head := l.root.next
head.prev = node
node.next = head
node.prev = l.root
l.root.next = node
l.len++
node.list = l
}
func (l *LRU) debug() {
fmt.Println("lru len: ", l.len)
fmt.Println("lru cap: ", l.cap)
for n := l.root.next; n != l.root; n = n.next {
fmt.Printf("%s:%v -> ", n.key, n.value)
}
fmt.Println()
}
【Golang 数据结构】实现 LRU
2021-10-08