1 基本概念
LRU是一个老生常谈的问题，即最近最少使用，LRU是Least Recently Used的缩写，是一种操作系统中常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。
实现LRU基本的数据结构：Map+LinkedList
一般规则：
- 添加数据时，将新增数据节点放在头指针，尾结点部分大于最大长度时删除。
- 删除数据时，先按照Map的规则进行查找，再根据链表规则进行删除。
- 查找数据时，按照Map进行查找，没有则返回空，有则返回该数据的值并移动到头节点。
2 代码实现
package main
import "fmt"
var head *Node
var end *Node
type Node struct {
Key string
Value string
pre *Node
next *Node
}
func (n *Node) Init(key string, value string) {
n.Key = key
n.Value = value
}
type LRUCache struct {
Capacity int //页面初始化大小
Size int //页面实际大小
Map map[string]*Node //具体的cache
}
func GetLRUCache(capacity int) *LRUCache {
lruCache := LRUCache{Capacity: capacity}
lruCache.Map = make(map[string]*Node, capacity)
return &lruCache
}
func (l *LRUCache) get(key string) string {
if v, ok := l.Map[key]; ok {
l.refreshNode(v)
return v.Value
} else {
return "null"
}
}
func (l *LRUCache) put(key, value string) {
if v, ok := l.Map[key]; !ok {
if len(l.Map) >= l.Capacity {
oldKey := l.removeNode(head)
delete(l.Map, oldKey)
}
node := Node{Key: key, Value: value}
l.addNode(&node)
l.Map[key] = &node
} else {
v.Value = value
l.refreshNode(v)
}
}
func (l *LRUCache) refreshNode(node *Node) {
if node == end {
return
}
l.removeNode(node)
l.addNode(node)
}
func (l *LRUCache) removeNode(node *Node) string {
if node == end {
end = end.pre
} else if node == head {
head = head.next
} else {
node.pre.next = node.next
node.next.pre = node.pre
}
return node.Key
}
func (l *LRUCache) addNode(node *Node) {
if end != nil {
end.next = node
node.pre = end
node.next = nil
}
end = node
if head == nil {
head = node
}
}3 测试使用
func main() {
lruCache := GetLRUCache(3)
lruCache.put("001", "1")
lruCache.put("002", "2")
lruCache.put("003", "3")
lruCache.put("004", "4")
lruCache.put("005", "5")
lruCache.get("002")
fmt.Println(lruCache.get("001"))
fmt.Println(lruCache.get("002"))
fmt.Print(lruCache.Map)
}参考文章：
