title: LRU缓存机制Go语言实现
date: 2021-05-23 23:29:40
tags:

  • go

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表示双向链表的一个节点。

  1. package LRU
  3. import "container/list"
  5. type LRUCache struct {
  6.     Capacity   int
  7.     DoubleList *list.List
  8.     Hashtable  map[int]*list.Element
  9. }
  11. func New(cap int) *LRUCache {
  12.     return &LRUCache{
  13.         Capacity:   cap,
  14.         DoubleList: list.New(),
  15.         Hashtable:  make(map[int]*list.Element),
  16.     }
  17. }
  19. func (l *LRUCache) Get(key int) int {
  20.     v, ok := l.Hashtable[key]
  21.     if ok {
  22.         l.DoubleList.MoveToFront(v)
  23.         return key
  24.     }
  25.     return -1
  26. }
  28. func (l *LRUCache) Set(key int) {
  29.     //查找key，如果已经存在，则把该节点放到链表头
  30.     v, ok := l.Hashtable[key]
  31.     if ok {
  32.         l.DoubleList.MoveToFront(v)
  33.         return
  34.     }
  35.     //如果不存在，判断当前map大小
  36.     currLen := len(l.Hashtable)
  37.     //map已满，删除链表尾节点，将新节点插入表头
  38.     if currLen >= l.Capacity {
  39.         del := l.DoubleList.Back().Value
  40.         l.DoubleList.Remove(l.DoubleList.Back())
  41.         delete(l.Hashtable, del.(int))
  42.     }
  43.     //map未满，直接插入表头
  44.     ins := l.DoubleList.PushFront(key)
  45.     l.Hashtable[key] = ins
  46.     return
  47. }