运维开发网

如何用Go语言实现LRU缓存

运维开发网 https://www.qedev.com 2022-08-05 10:53 出处:网络
这篇文章主要介绍了如何利用Go语言实现LRU?Cache,LRU是Least?Recently?Used的缩写,是一种操作系统中常用的页面置换算法,下面我们一起进入文章了解更多内容吧,需要的朋友可以参

这篇文章主要介绍了如何利用Go语言实现LRU?Cache,LRU是Least?Recently?Used的缩写,是一种操作系统中常用的页面置换算法,下面我们一起进入文章了解更多内容吧,需要的朋友可以参


1 基本概念

LRU是一个常见的问题,也就是说,它是最近使用最少的。LRU是最近使用的缩写,是操作系统中常用的页面替换算法。选择最近最长时间没有使用的页面来消除。该算法为每个页面提供一个访问字段,用于记录页面自上次被访问以来所经历的时间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 amp;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) gt;= l.Capacity { oldKey := l.removeNode(head) delete(l.Map, oldKey) } node := Node{Key: key, Value: value} l.addNode(amp;node) l.Map[key] = amp;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缓存的文章到此结束。有关使用Go实现LRU缓存的更多信息

0

上一篇:

没有了:下一篇

精彩评论

暂无评论...
验证码 换一张
取 消