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的文章就介绍到这了,更多相关Go实现LRU Cache内容请搜索源码搜藏网以前的文章或继续浏览下面的相关文章希望大家以后多多支持源码搜藏网！