【日拱一卒】链表—

LRU

Redis的内存淘汰机制好几种，如ttl、random、lru。

lru（less recently used）即最近最少使用策略，表示在最近一段时间内最少被使用到的Redis键，如果遇到内存不足，会有限淘汰这部分键来腾出更多空间。

今天就来说说lru这种淘汰策略是如何通过链表这种结构实现的。

难点

在链表结构中，如何表示最近访问的节点和如何表示最久没有访问的节点？

如何判定一个链表中是否存在要查找的节点？

如何向链表结构插入节点，并放在最近最新的节点位置？

如果在链表中删除一个节点？

思路

结合上面的难点，我们可以构建一个可以解决问题的链表模型。

如何表示最近访问的节点和如何表示最久没有访问的节点

可以设计一个双向链表，头结点表示最近访问的节点，尾结点表示最久没有访问的节点。使用双向链表是为了查找和定位更加方便。

如何判定一个链表中是否存在要查找的节点

解决这个问题，最直接的思路就是遍历整个链表，依次匹配如果找到相同的值，对应的节点就是待查找的节点，如果遍历完整个链表，还是没有找到，表示该链表不存在该节点。

还有一种思路是将链表的所有节点存放到一个map结合中，查找的时候直接通过map的key进行查找即可。

如何向链表结构插入节点，并放在最近最新的节点位置

结合前面几篇，我们知道，链表的插入和删除是非常方便的，但是在lru问题背景下，如果插入节点并保证是最新的位置呢？显然最新的节点是要放到头结点的。

另外需要注意的点是，插入之前需要先查找这个节点是否存在链表中，如果存在需要先删除。

如果在链表中删除一个节点

删除一个节点的前置步骤应该是先判定一个节点是否存在链表中，如果存在删除即可，如果不存在则无需删除。

通过以上几个问题，我们大概可以构想出几个原子函数

初始化双向链表结构
查找指定节点
插入指定节点
删除指定节点

下面我们主要看如何实现这几个函数就可以了，主要代码如下

type LRUCache struct {

	Cap  int

	Map  map[int]*Node

	Head *Node

	Last *Node

}

type Node struct {

	Val  int

	Key  int

	Pre  *Node

	Next *Node

}

func Constructor(capacity int) LRUCache {

	cache := LRUCache{

		Cap:  capacity,

		Map:  make(map[int]*Node, capacity),

		Head: &Node{},

		Last: &Node{},

	}

	cache.Head.Next = cache.Last

	cache.Last.Pre = cache.Head

	return cache

}

func (this *LRUCache) Get(key int) int {

	node, ok := this.Map[key]

	if !ok {

		return -1

	}

	this.remove(node)

	this.setHeader(node)

	return node.Val

}

func (this *LRUCache) Put(key int, value int) {

	node, ok := this.Map[key]

	if ok {

		this.remove(node)

	} else {

		if len(this.Map) == this.Cap {

			delete(this.Map, this.Last.Pre.Key)

			this.remove(this.Last.Pre)

		}

		node = &Node{Val: value, Key: key}

		this.Map[node.Key] = node

	}

	node.Val = value

	this.setHeader(node)

}

func (this *LRUCache) setHeader(node *Node) {

	this.Head.Next.Pre = node

	node.Next = this.Head.Next

	this.Head.Next = node

	node.Pre = this.Head

}

func (this *LRUCache) remove(node *Node) {

	node.Pre.Next = node.Next

	node.Next.Pre = node.Pre

}

初始化的双向链表如上图所示，一个节点包括数据部分data，前继节点pre和后继节点next。

所有节点数据放入map集合中。

Get()方法会在map中查找，如果不存在，则直接返回。如果存在，则调用remove先删除该节点，再调用setHeader将节点放入头结点。

Put()方法会首先在map中查找对应节点，如果找到，则先调用remove删除方法删除改节点，并调用setHeader方法将节点放入头结点。

至此一个lru的淘汰策略使用一个双向链表就实现了。

链表总结

前面几篇，分别介绍了通过链表结构如何实现链表反转、判断链表是否有环、链表结构的回文判断、有序链表的合并以及本篇的lru实现。

链表具备插入删除方便，但是查找效率较低的特性。

以下是对于链表结构的梳理

如果您觉得阅读本文对您有帮助，请点一下“推荐”按钮，您的“推荐”将是我最大的写作动力！如果您想持续关注我的文章，请扫描二维码，关注JackieZheng的微信公众号，我会将我的文章推送给您，并和您一起分享我日常阅读过的优质文章。

巴特西

【日拱一卒】链表——如何实现lru

LRU

难点

思路

链表总结

最新文章

热门文章