算法(8): LRU 策略

LeetCode No.146 LRU缓存机制

LRU（Least Recent Used）策略：优先淘汰最近最少使用的数据，常用于缓存淘汰机制，如Linux系统的内存淘汰、Redis的缓存淘汰等。

基于哈希表和双向链表实现LRU

核心思路是，利用双向链表存储键值对，哈希表存储键在链表中对应的节点指针，如下图所示

这样的好处是使访问和更新操作时间复杂度都在O(1)。

PUT操作

• 判断哈希表中key是否已存在，如果存在为修改操作：
  1. 将链表节点修改为新的键值对
  2. 将节点移到头部
• 如果不存在为新增操作，此时如果容量已满，需要淘汰数据
  1. 取出链表尾节点，删除哈希表中对应key
  2. 删除链表尾节点
  3. 在链表头部添加新的节点
  4. 将新的链表头节点加到哈希表
• 如果容量没有满，直接添加节点，执行上述步骤3、4即可

GET操作

• 判断哈希表中key是否存在，如果存在将节点移动到链表头部，返回对应的值
• 如果不存在直接返回nil值

Go语言实现

使用Go内建map类型和container包的list（双向链表）

import (
    "container/list"
)

type Pair struct {
    key int
    val int
}

type LRUCache struct {
    cap int
    list *list.List
    kv map[int]*list.Element
}


func Constructor(capacity int) LRUCache {
    return LRUCache{
        cap: capacity,
        list: list.New(),
        kv: make(map[int]*list.Element),
    }
}


func (this *LRUCache) Get(key int) int {
    if v, ok := this.kv[key]; ok == true {
        this.list.MoveToFront(v)
        return v.Value.(Pair).val
    } else {
        return -1
    }
}


func (this *LRUCache) Put(key int, value int)  {
    if elem, ok := this.kv[key]; ok == true {
        elem.Value = Pair{key: key, val: value}
        this.list.MoveToFront(elem)
        return
    }
    if this.list.Len() >= this.cap {
        delete(this.kv, this.list.Back().Value.(Pair).key)
        this.list.Remove(this.list.Back())
    }
    this.list.PushFront(Pair{key: key, val: value})
    this.kv[key] = this.list.Front()
}