LRU緩存淘汰算法
LRU是最近最少使用策略的縮寫，是根據(jù)數(shù)據(jù)的歷史訪問(wèn)記錄來(lái)進(jìn)行淘汰數(shù)據(jù)，其核心思想是“如果數(shù)據(jù)最近被訪問(wèn)過(guò)，那么將來(lái)被訪問(wèn)的幾率也更高”。
雙向鏈表實(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。
當(dāng)達(dá)到緩存容量上限時(shí)，鏈表的最后位置就是最少被訪問(wèn)的Cache，我們只需要?jiǎng)h除鏈表最后的Cache便可繼續(xù)添加新的Cache。
代碼實(shí)現(xiàn)
type Node struct {
Key int
Value int
pre *Node
next *Node
}
type LRUCache struct {
limit int
HashMap map[int]*Node
head *Node
end *Node
}
func Constructor(capacity int) LRUCache{
lruCache := LRUCache{limit:capacity}
lruCache.HashMap = make(map[int]*Node, capacity)
return lruCache
}
func (l *LRUCache) Get(key int) int {
if v,ok:= l.HashMap[key];ok {
l.refreshNode(v)
return v.Value
}else {
return -1
}
}
func (l *LRUCache) Put(key int, value int) {
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) refreshNode(node *Node){
if node == l.end {
return
}
l.removeNode(node)
l.addNode(node)
}
func (l *LRUCache) removeNode(node *Node) int{
if node == l.end {
l.end = l.end.pre
}else if node == l.head {
l.head = l.head.next
}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
}
}
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
您可能感興趣的文章:- java LRU算法介紹與用法示例
- 工程師必須了解的LRU緩存淘汰算法以及python實(shí)現(xiàn)過(guò)程
- JS 實(shí)現(xiàn)緩存算法的示例（FIFO/LRU）
- Nodejs基于LRU算法實(shí)現(xiàn)的緩存處理操作示例
- c++實(shí)現(xiàn)的常見(jiàn)緩存算法和LRU
- Android圖片緩存之Lru算法（二）
- Python實(shí)現(xiàn)LRU算法的2種方法
- JAVA實(shí)現(xiàn)LRU算法的參考示例
