LRU緩存淘汰算法
LRU是最近最少使用策略的縮寫脉漏。
雙向鏈表實(shí)現(xiàn)LRU
將Cache的所有位置都用雙鏈表連接起來(lái)岭辣，當(dāng)一個(gè)位置被訪問(wèn)(get/put)之后，通過(guò)調(diào)整鏈表的指向匪蝙，將該位置調(diào)整到鏈表尾的位置吓著，新加入的Cache直接加到鏈表尾。
這樣歉井，在多次操作后柿祈，最近被訪問(wèn)(get/put)的，就會(huì)被向鏈表尾方向移動(dòng)哩至，而沒(méi)有訪問(wèn)的躏嚎，向鏈表前方移動(dòng)，鏈表頭則表示最近最少使用的Cache菩貌。
package main
import (
"fmt"
)
type Node struct{
Key interface{}
Value interface{}
pre *Node
next *Node
}
type LRUCache struct {
limit int
HashMap map[interface{}]*Node
head *Node
end *Node
}
func(l *LRUCache)removeNode(node *Node)interface{}{
if node == l.end{
l.end = l.end.pre
l.end.next = nil
} else if node == l.head{
l.head = l.head.next
l.head.pre = nil
} else {
node.pre.next = node.next
node.next.pre = node.pre
}
return node.Key
}
func (l *LRUCache)addNode(node *Node){
if l.end != nil {
l.end.next = node
node.pre = l.end
node.next = nil
}
l.end = node
if l.head == nil {
l.head = node
}
}
func (l *LRUCache)refreshNode(node *Node){
if node == l.end{
return
}
l.removeNode(node) // 從鏈表中的任意位置移除原來(lái)的位置
l.addNode(node) // 添加到鏈表的尾部
}
// 構(gòu)造
func Constructor(capacity int)LRUCache{
lruCache := LRUCache{limit: capacity}
lruCache.HashMap = make(map[interface{}]*Node, capacity)
return lruCache
}
// 獲取
func (l *LRUCache)Get(key interface{})interface{}{
if v, ok := l.HashMap[key]; ok {
l.refreshNode(v)
return v.Value
} else {
return -1
}
}
func (l *LRUCache)Put(key, value interface{}){
if v, ok := l.HashMap[key]; !ok{
if len(l.HashMap) >= l.limit {
oldkey := l.removeNode(l.head)
delete(l.HashMap, oldkey)
}
node := Node{Key:key, Value:value}
l.addNode(&node)
l.HashMap[key] = &node
} else {
v.Value = value
l.refreshNode(v)
}
}
func (l *LRUCache)getCache(){
for n := l.head; n != nil; n = n.next{
fmt.Println(n.Key, n.Value)
}
}
func main(){
cache := Constructor(3)
cache.Put(11, 1)
cache.Put(22, 2)
cache.Put(33, 3)
cache.Put(44, 4)
v := cache.Get(33)
fmt.Println(v)
fmt.Println("========== 獲取數(shù)據(jù)之后 ===============")
cache.getCache()
}
