怎么用Go語言實現LRU?Cache

小編給大家分享一下怎么用Go語言實現LRU Cache，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

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

看完了這篇文章，相信你對“怎么用Go語言實現LRU Cache”有了一定的了解，如果想了解更多相關知識，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！