Go 语言实现 LRU 算法

业余杂谈 herman 246浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:codedq,发送下载链接帮助你免费下载!
本博客日IP超过2000,PV 3000 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:codedq,之前的微信号好友位已满,备注:返现
饿了么大量招人,我内推!Java 方向!薪资不设上限,工作年龄不限!工作地点限魔都,可电话面试!简历,发我微信:codedq
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领

LRU(The Least Recently Used,最近最久未使用算法)是一种常见的缓存算法,在很多分布式缓存系统(如Redis, Memcached)中都有广泛使用。

LRU算法的思想是:如果一个数据在最近一段时间没有被访问到,那么可以认为在将来它被访问的可能性也很小。因此,当空间满时,最久没有访问的数据最先被置换(淘汰)。

LRU算法的描述: 设计一种缓存结构,该结构在构造时确定大小,假设大小为 K,并有两个功能:

  1. set(key,value):将记录(key,value)插入该结构。当缓存满时,将最久未使用的数据置换掉。
  2. get(key):返回key对应的value值。

Java 实现:最朴素的思想就是用数组+时间戳的方式,不过这样做效率较低。因此,我们可以用双向链表(LinkedList)+哈希表(HashMap)实现(链表用来表示位置,哈希表用来存储和查找),在Java里有对应的数据结构LinkedHashMap。

下面是针对 Go 语言的 LRU 算法实现。

package problem0146

// 双向链表结构
type LinkNode struct {
	key, value int
	pre, next  *LinkNode
}

// LRU结构
type LRUCache struct {
	m          map[int]*LinkNode
	cap        int
	head, tail *LinkNode
}

func Constructor(capacity int) LRUCache {
	head := &LinkNode{0, 0, nil, nil}
	tail := &LinkNode{0, 0, nil, nil}
	head.next = tail
	tail.pre = head
	return LRUCache{make(map[int]*LinkNode, capacity), capacity, head, tail}
}

func (this *LRUCache) moveToHead(node *LinkNode) {
	this.removeNode(node)
	this.addNode(node)
}

func (this *LRUCache) removeNode(node *LinkNode) {
	node.pre.next = node.next
	node.next.pre = node.pre
}

func (this *LRUCache) addNode(node *LinkNode) {
	head := this.head
	node.next = head.next
	node.next.pre = node
	node.pre = head
	head.next = node
}

// 如果有,将这个元素移动到首位置,返回值
// 如果没有,返回-1
func (this *LRUCache) Get(key int) int {
	if v, exist := this.m[key]; exist {
		this.moveToHead(v)
		return v.value
	} else {
		return -1
	}
}

// 如果元素存在,将其移动到最前面,并更新值
// 如果元素不存在,插入到元素首,放入map(判断容量)
func (this *LRUCache) Put(key int, value int) {
	tail := this.tail
	cache := this.m
	if v, exist := cache[key]; exist {
		v.value = value
		this.moveToHead(v)
	} else {
		v := &LinkNode{key, value, nil, nil}
		if len(this.m) == this.cap {
			delete(cache, tail.pre.key)
			this.removeNode(tail.pre)
		}
		this.addNode(v)
		cache[key] = v
	}
}

思路比代码更重要,想通原理,实现起来 so easy!

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号1:xmtxtt(5000人已满),微信号2:xttblog(5000人已满),微信号3:codedq(超3800)。备注:“1”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!

本文原文出处:业余草: » Go 语言实现 LRU 算法