算法之美-LRU

Algorithms To Live By Comments

问题背景

LRU(Least Recently Used)，最近最少使用。根据时间维度来选择将要淘汰的元素，即删除掉最长时间没被访问的元素。

实现一个LRU算法需要解决的问题：

  1. 一个存储最近使用元素的结构，能够快速定位到元素(map)
  2. 如何计算元素被最少使用了，当添加或更新元素的时候方便查询最少使用元素(双向链表)
  3. 最近最少使用存在数量上限。(容量capacity)

实现原理

  • 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
  • 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置
algori-Live-1

删除节点

algori-live-lru-1

删除的时候链表和map中的都需要删除

新增节点

algori-live-lru-2

注意：

  1. list节点中也要存储Map的key

技术内幕

代码路径：core/collection/cache.go

对象定义

1
2
3
4
5
6
7
8
9
10
11
12
13
lru interface {
	add(key string)			//新增
	remove(key string)	//删除
}

emptyLru struct{}

keyLru struct {
	limit    int				//容量限制
	evicts   *list.List	//双向链表
	elements map[string]*list.Element	//map根据key存储双向链表位置
	onEvict  func(key string)	//自定义触发函数
}

删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func (klru *keyLru) remove(key string) {
	if elem, ok := klru.elements[key]; ok {	//通过map判断元素是否存在
		klru.removeElement(elem)	//删除节点
	}
}

func (klru *keyLru) removeOldest() {
	elem := klru.evicts.Back()	//获取尾部节点
	if elem != nil {
		klru.removeElement(elem)
	}
}

func (klru *keyLru) removeElement(e *list.Element) {
	klru.evicts.Remove(e)		//删除双向链表节点
	key := e.Value.(string)
	delete(klru.elements, key)		//删除map中节点
	klru.onEvict(key)				//触发自定义逻辑
}

添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func (klru *keyLru) add(key string) {
   if elem, ok := klru.elements[key]; ok {	//如果元素存在则将节点移动到链表头
      klru.evicts.MoveToFront(elem)
      return
   }

   // Add new item
   elem := klru.evicts.PushFront(key)			//放入链表头部
   klru.elements[key] = elem							//存放节点

   // Verify size not exceeded
   if klru.evicts.Len() > klru.limit {		//如果节点数量超过限制，则删除尾部节点
      klru.removeOldest()
   }
}

参考链接

  1. https://talkgo.org/t/topic/2280