如何利用Go语言实现LRU Cache
更新时间:2022年3月6日 19:18 点击:338 作者:红帽海绵宝宝
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内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/Mr_YanMingXin/article/details/12302253
上一篇: 一文搞懂Go Exec 僵尸与孤儿进程
下一篇: golang生成vcf通讯录格式文件详情
相关文章
- 在程序员中,尤其是go新手,经常听到的一个讨论话题是:如何处理错误,这篇文章主要给大家介绍了关于Go应用中优雅处理Error的一些相关技巧,需要的朋友可以参考下...2021-09-08
Django def clean()函数对表单中的数据进行验证操作
这篇文章主要介绍了Django def clean()函数对表单中的数据进行验证操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-07-09PHP分布式框架如何使用Memcache同步SESSION教程
本教程主要讲解PHP项目如何用实现memcache分布式,配置使用memcache存储session数据,以及memcache的SESSION数据如何同步。 至于Memcache的安装配置,我们就不讲了,以前...2016-11-25- 这篇文章主要介绍了golang官方嵌入文件到可执行程序,本文通过示例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-02-20
- 这篇文章主要介绍了go浮点数转字符串保留小数点后N位解决办法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2020-05-11
- 这篇文章主要介绍了Go语言使用读写OPC详解,图文讲解的很清晰,有感兴趣的同学可以学习下...2021-03-05
- memche消息队列的原理就是在key上做文章,用以做一个连续的数字加上前缀记录序列化以后消息或者日志。然后通过定时程序将内容落地到文件或者数据库。php实现消息队列的用处比如在做发送邮件时发送大量邮件很费时间的问...2014-05-31
- 这篇文章主要介绍了Go项目的目录结构,对基础目录做了讲解,对项目开发中的其它目录也一并做了介绍,需要的朋友可以参考下...2020-05-01
- string与[]byte经常需要互相转化,普通转化会发生底层数据的复制,下面这篇文章主要给大家介绍了关于Go中string与[]byte高效互转的相关资料,文中通过示例代码介绍的非常详细,需要的朋友可以参考下...2021-09-20
- Go 语言提供的基础容器,免不了要查询容器中的数据,那么是如何实现遍历的呢?本文将会介绍几种常用容易的遍历及其使用。感兴趣的可以了解一下...2021-06-13
- 这篇文章主要介绍了创建第一个Go语言程序Hello,Go!本文详细的给出项目创建、代码编写的过程,同时讲解了GOPATH、Go install等内容,需要的朋友可以参考下...2020-05-01
- 这篇文章主要介绍了在Django中使用MQTT的方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-05-10
- 这篇文章主要介绍了go语言中的Carbon库时间处理,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-02-05
SpringCache 分布式缓存的实现方法(规避redis解锁的问题)
这篇文章主要介绍了SpringCache 分布式缓存的实现方法(规避redis解锁的问题),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2020-11-20- 这篇文章主要介绍了go嵌套匿名结构体的初始化详解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-16
解决导入django_filters不成功问题No module named 'django_filter'
这篇文章主要介绍了解决导入django_filters不成功问题No module named 'django_filter',具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-07-15- 本文着重介绍如何在XCODE中,通过C++开发在IOS环境下运行的缓存功能。算法基于LRU,最近最少使用,需要的朋友可以参考下...2020-04-25
- 本文主要介绍了Django项目连接MongoDB的三种方法,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-09-27
详解如何使用Docker部署Django+MySQL8开发环境
这篇文章主要介绍了详解如何使用Docker部署Django+MySQL8开发环境,文中通过示例代码以及图文介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面来一起学习学习吧...2020-07-19- 这篇文章主要介绍了Go语言json编码驼峰转下划线、下划线转驼峰的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-09