怎么用Go语言实现LRU Cache

小编给大家分享一下怎么用Go语言实现LRU Cache，希望大家阅读完这篇文章之后都有所收获，下面让我们一起去探讨吧！

1 基本概念

LRU是一个老生常谈的问题，即最近最少使用，LRU是Least Recently Used的缩写，是一种操作系统中常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

实现LRU基本的数据结构：Map+LinkedList

一般规则：

• 添加数据时，将新增数据节点放在头指针，尾结点部分大于最大长度时删除。

• 删除数据时，先按照Map的规则进行查找，再根据链表规则进行删除。

• 查找数据时，按照Map进行查找，没有则返回空，有则返回该数据的值并移动到头节点。

2 代码实现

package mainimport "fmt"var head *nodevar end *Nodetype 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”有了一定的了解，如果想了解更多相关知识，欢迎关注编程网精选频道，感谢各位的阅读！