LRU是一個老生常談的問題，即最近最少使用，LRU是Least Recently Used的縮寫，是一種操作系統(tǒng)中常用的頁面置換算法，選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經歷的時間 t，當須淘汰一個頁面時，選擇現(xiàn)有頁面中其 t 值最大的，即最近最少使用的頁面予以淘汰。

實現(xiàn)LRU基本的數(shù)據(jù)結構：Map+LinkedList

一般規(guī)則：

添加數(shù)據(jù)時，將新增數(shù)據(jù)節(jié)點放在頭指針，尾結點部分大于最大長度時刪除。
刪除數(shù)據(jù)時，先按照Map的規(guī)則進行查找，再根據(jù)鏈表規(guī)則進行刪除。
查找數(shù)據(jù)時，按照Map進行查找，沒有則返回空，有則返回該數(shù)據(jù)的值并移動到頭節(jié)點。

2 代碼實現(xiàn)

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)
}

到此這篇關于如何利用Go語言實現(xiàn)LRU Cache的文章就介紹到這了,更多相關Go實現(xiàn)LRU Cache內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: