Go implements LRU cache

1 Basic concepts

LRU It's a platitude , Least recently used ,LRU yes Least Recently Used Abbreviation , Is a commonly used page replacement algorithm in the operating system , Select the most recent unused page to weed out . The algorithm gives each page an access field , Used to record the time of a page since it was last visited t, When a page has to be eliminated , Select one of the existing pages t The most valuable , That is, the most recently used pages are eliminated .

Realization LRU Basic data structure ：Map+LinkedList

General rules ：

• When adding data , Place the new data node in the header pointer , Delete when the tail node is greater than the maximum length .
• When deleting data , First according to Map The rules for searching , Then delete according to the linked list rules .
• When finding data , according to Map Search for , If not, return null , If yes, return the value of the data and move it to the header node .

2 Code implementation

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              // Page initialization size 
   Size     int              // Actual page size 
   Map      map[string]*Node // Concrete 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 Test use

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

Reference article ：

https://blog.csdn.net/u010647109/article/details/83746784