LRU缓存机制Go语言实现

2021-05-23

LRU缓存机制

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

设计思路

LRU算法需要对数据结构进行查询和插入、删除操作，对序列化数据结构来说，一般采取数组/链表的数据结构。两者差异对比如下：

数组 查询比较快，但是对于增删来说是一个不是一个好的选择
链表 查询比较慢，但是对于增删来说十分方便，时间复杂度为O(1)

因此，要想实现快速查询、增删，可以使用hash+链表的形式。hash表存储链表节点，可以在O(1)时间复杂度内查找；链表保持表头的节点是最近使用的节点，表尾的节点是最久为使用节点，这样在淘汰页面的时候直接将链表尾的节点淘汰就可以了，每次访问页面后将其放在链表头。

代码实现

Golang中的双向链表在container/list这个包下，Go语言标准库中文文档中有详细的介绍，这里不再赘述。

hash表可以直接使用Golang提供的map，这里定义为map[int]*list.Element类型。其中key是int型，表示页面号，*list.Element表示双向链表的一个节点。

package LRU

import "container/list"

type LRUCache struct {
	Capacity   int
	DoubleList *list.List
	Hashtable  map[int]*list.Element
}

func New(cap int) *LRUCache {
	return &LRUCache{
		Capacity:   cap,
		DoubleList: list.New(),
		Hashtable:  make(map[int]*list.Element),
	}
}

func (l *LRUCache) Get(key int) int {
	v, ok := l.Hashtable[key]
	if ok {
		l.DoubleList.MoveToFront(v)
		return key
	}
	return -1
}

func (l *LRUCache) Set(key int) {
	//查找key，如果已经存在，则把该节点放到链表头
	v, ok := l.Hashtable[key]
	if ok {
		l.DoubleList.MoveToFront(v)
		return
	}
	//如果不存在，判断当前map大小
	currLen := len(l.Hashtable)
	//map已满，删除链表尾节点，将新节点插入表头
	if currLen >= l.Capacity {
		del := l.DoubleList.Back().Value
		l.DoubleList.Remove(l.DoubleList.Back())
		delete(l.Hashtable, del.(int))
	}
	//map未满，直接插入表头
	ins := l.DoubleList.PushFront(key)
	l.Hashtable[key] = ins
	return
}