LRU 缓存

常用综合题型

说明

哈希表定位键，双向链表维护最近使用顺序；Go 可用 container/list 实现。

分析

map 让键能直接定位链表节点，链表头表示最近使用、尾部表示最久未使用。Get 与 Put 都把访问项移到头部；容量超限时删除尾节点。

容量2时Get(a)把a移回表头，再插c应淘汰b。map与链表必须始终包含相同成员；查中也会修改次序，因此并发Get并非纯读取，需要保护整个联合操作。

查看图表代码

适用前提与边界

两个结构必须同步更新，否则会出现悬挂索引或错误淘汰。 本例容量小于等于0时Put不保存条目；Get也会移动链表节点，并发访问必须保护map与链表的联合修改。

示例输入与调用

cache := NewLRU(2)
	cache.Put("a", 1)
	cache.Put("b", 2)
	value, ok := cache.Get("a")
	fmt.Println(value, ok)

运行输出

1 true

完整 Go 示例

package main

import (
	"fmt"
	"container/list"
)

type Entry struct {
	Key   string
	Value int
}
type LRU struct {
	cap   int
	order *list.List
	items map[string]*list.Element
}

func NewLRU(capacity int) *LRU {
	return &LRU{capacity, list.New(), map[string]*list.Element{}}
}
func (c *LRU) Get(key string) (int, bool) {
	e := c.items[key]
	if e == nil {
		return 0, false
	}
	c.order.MoveToFront(e)
	return e.Value.(Entry).Value, true
}
func (c *LRU) Put(key string, value int) {
	if c.cap <= 0 {
		return
	}
	if e := c.items[key]; e != nil {
		e.Value = Entry{key, value}
		c.order.MoveToFront(e)
		return
	}
	c.items[key] = c.order.PushFront(Entry{key, value})
	if c.order.Len() > c.cap {
		e := c.order.Back()
		delete(c.items, e.Value.(Entry).Key)
		c.order.Remove(e)
	}
}

func main() {
	cache := NewLRU(2)
	cache.Put("a", 1)
	cache.Put("b", 2)
	value, ok := cache.Get("a")
	fmt.Println(value, ok)
}