LRU

概念

LRU 全称是 Least Recently Used，即最近最久未使用算法，它是页面置换算法的一种。

原理

LRU 算法根据数据的历史访问记录来进行淘汰数据，其核心思想是「如果数据最近被访问过，那么将来被访问的几率也更高」。

演示

假设内存只能容纳3个页大小，按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间，在上面的，是最近访问的，在下面的是，最远时间访问的。

设计

• 基于 HashMap 和 双向链表实现
• 设计思路：可以使用 HashMap 存储 key，这样可以做到 save 和 get key的时间都是 O(1)，而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点，如图所示：

• 其中 head 代表双向链表的表头，tail 代表尾部。首先预先设置 LRU 的容量，如果存储满了，可以通过 O(1) 的时间淘汰掉双向链表的尾部，每次新增和访问数据，都可以通过 O(1)的效率把新的节点增加到对头，或者把已经存在的节点移动到队头。

• 预设大小是 3 ，演示LRU在存储和访问过程中的变化。我们对这个LRU缓存的操作序列如下：

• 1. save(key1, 7) save(key2, 0) save(key3, 1) save(key4, 2)
• 2. get(key2) save(key5, 3) get(key2) save(key6, 4)
• 3. LRU双向链表变化如下：

-

• 两个核心操作：

• 1. save(key, value)，首先在 HashMap 找到 Key 对应的节点，如果节点存在，更新节点的值，并把这个节点移动队头。如果不存在，需要构造新的节点，并且尝试把节点塞到队头，如果LRU空间不足，则通过 tail 淘汰掉队尾的节点，同时在 HashMap 中移除 Key。
• 2. get(key)，通过 HashMap 找到 LRU 链表节点，因为根据LRU 原理，这个节点是最新访问的，所以要把节点插入到队头，然后返回缓存的值。

• 代码实现

package mylru

type DLinkerNode struct {
    key       string
    value     interface{}
    pre, post *DLinkerNode
}
type LRUCache struct {
    head, tail      *DLinkerNode
    capacity, count int
    cache           map[string]*DLinkerNode
}

// 根据key,value创建一个新节点
func newDLinkerNode(key string, value interface{}) *DLinkerNode {
    return &DLinkerNode{
        key:   key,
        value: value,
    }
}

// 创建一个容量为capacity的LRU缓存
func NewLRUCache(capacity int) *LRUCache {
    lru := &LRUCache{
        head:     newDLinkerNode("", struct{}{}),
        tail:     newDLinkerNode("", struct{}{}),
        capacity: capacity,
        cache:    make(map[string]*DLinkerNode),
    }
    lru.head.post = lru.tail
    lru.tail.pre = lru.head
    return lru
}

/**
根据key值查询查询LRU缓存中的元素
*/
func (lru *LRUCache) Get(key string) (interface{}, bool) {
    node, ok := lru.cache[key]
    if !ok {
        return nil, ok
    }
    lru.moveToHead(node)
    return node.value, true
}

/**
向LRU缓存中添加元素
第一个返回值代表删除的元素的value 第二个返回值表示是否添加成功
*/
func (lru *LRUCache) Put(key string, value interface{}) (interface{}, bool) {
    node, ok := lru.cache[key]
    // 存在->更新value值并移至头部
    if ok {
        node.value = value
        lru.moveToHead(node)
        return nil, false
    }
    // 不存在->创建节点,添加至头部
    node = newDLinkerNode(key, value)
    lru.addToHead(node)
    // 更新cache
    lru.cache[key] = node
    lru.count++
    // size超过限定的容量
    if lru.Size() > lru.capacity {
        //删除尾部节点
        removeNode := lru.removeTail()
        //更新cache
        delete(lru.cache, removeNode.key)
        lru.count--
        return removeNode.value, true
    }
    return nil, true
}

/**
删除LRU缓存中key对应的元素
*/
func (lru *LRUCache) Del(key string) (interface{}, bool) {
    node, ok := lru.cache[key]
    if !ok { // 不存在
        return nil, ok
    }
    // 存在则移除该节点
    lru.removeNode(node)
    // 更新cache
    delete(lru.cache, key)
    lru.count--
    return node.value, true
}

// 将节点移至头部
func (lru *LRUCache) moveToHead(node *DLinkerNode) {
    lru.removeNode(node)
    lru.addToHead(node)
}

// 移除对应的节点
func (lru *LRUCache) removeNode(node *DLinkerNode) {
    node.pre.post = node.post
    node.post.pre = node.pre
    node.pre = nil
    node.post = nil
}

// 添加一个节点到头部
func (lru *LRUCache) addToHead(node *DLinkerNode) {
    node.pre = lru.head
    node.post = lru.head.post
    lru.head.post.pre = node
    lru.head.post = node
}

// 移除尾部节点
func (lru *LRUCache) removeTail() *DLinkerNode {
    node := lru.tail.pre
    lru.removeNode(node)
    return node
}