LRU

LRU(Least Recent Used), 是一种缓存置换算法, 当需要置换时, 将最近最少使用的元素置换出缓存.

如果是 Java 的话, 可以直接继承 LinkedHashMap, 修改 removeOldest() 方法即可. Go 中没有这个实现, 可以自己通过 map 和 双向链表实现一个 LinkedHashMap. 用这种方法实现的 LRU 算法, 读写的时间复杂度都为 $O(1)$, 空间复杂度为 $O(n)$.

算法中, 主要的操作其实是双向列表中节点的添加与删除. 针对 LRU 的部分, 则是每次添加或者更新都将添加/修改的节点放到头节点, 这样最近最少使用的节点自然是在尾节点. 同时, 如果容量已满, 就需要进行置换, 删除尾节点.

以下为 go 实现的 LRU:

type LRUCache struct {
    capacity int
    size     int
    cache    map[int]*BiLinkedNode
    head     *BiLinkedNode
    tail     *BiLinkedNode
}

func NewLRUCache(capacity int) *LRUCache {
    cache := &LRUCache{
    capacity: capacity,
        size:     0,
        cache:    make(map[int]*BiLinkedNode),
        head:     NewBiLinkedNode(0, 0),
        tail:     NewBiLinkedNode(0, 0),
    }

     cache.head.Next = cache.tail
     cache.tail.Prev = cache.head

     return cache
}

func (c *LRUCache) Get(key int) int {
    if _, ok := c.cache[key]; !ok {
        return -1
    }

    node := c.cache[key]
    c.moveToHead(node)
    return node.Value
}

func (c *LRUCache) Put(key int, value int) {
    if _, ok := c.cache[key]; !ok {
        node := NewBiLinkedNode(key, value)
        c.cache[key] = node
        c.addToHead(node)
        c.size ++

        if c.size > c.capacity {
            removed := c.removeTail()
            delete(c.cache, removed.Key)
            c.size--
     }

     return
    }

    node := c.cache[key]
    node.Value = value
    c.moveToHead(node)
}

func (c *LRUCache) addToHead(node *BiLinkedNode) {
    node.Prev = c.head
    node.Next = c.head.Next
    c.head.Next.Prev = node
    c.head.Next = node
}

func (c *LRUCache) removeNode(node *BiLinkedNode) {
    node.Prev.Next = node.Next
    node.Next.Prev = node.Prev
}

func (c *LRUCache) moveToHead(node *BiLinkedNode) {
    c.removeNode(node)
    c.addToHead(node)
}

func (c *LRUCache) removeTail() *BiLinkedNode {
    node := c.tail.Prev
    c.removeNode(node)

    return node
}

type BiLinkedNode struct {
    Key   int
    Value int
    Prev  *BiLinkedNode
    Next  *BiLinkedNode
}

func NewBiLinkedNode(k, v int) *BiLinkedNode {
    return &BiLinkedNode{
        Key:   k,
        Value: v,
    }
}