LRU go 实现

本文主要介绍 LRU 的 golang 版本的实现

LRU 简介

首先 LRU 算法的全称是 Least Recently Used 即最近最少未使用，是一种很典型的页面置换算法，相应的还有 LFU、先进先出算法等

LRU 实现

使用 hashTable + 双向链表实现

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

核心操作的步骤:

• set(key, value)，首先在 HashMap 找到 Key 对应的节点，如果节点存在，更新节点的值，并把这个节点移动队头。如果不存在，需要构造新的节点，并且尝试把节点塞到队头，如果LRU空间不足，则通过 tail 淘汰掉队尾的节点，同时在 HashMap 中移除 Key
• get(key)，通过 HashMap 找到 LRU 链表节点，把节点插入到队头，返回缓存的值

type CacheNode struct {
    Key, Value interface{}
}

func (cnode *CacheNode) NewCacheNode(k, v interface{}) *CacheNode {
    return &CacheNode{k, v}
}

type LRUCache struct {
    Capacity int
    dlist    *list.List
    cacheMap map[interface{}]*list.Element
}

func NewLRUCache(cap int) *LRUCache {
    return &LRUCache{
        Capacity: cap,
        dlist:    list.New(),
        cacheMap: make(map[interface{}]*list.Element)}
}

func (lru *LRUCache) Size() int {
    return lru.dlist.Len()
}

func (lru *LRUCache) Set(k, v interface{}) error {

    if lru.dlist == nil {
        return errors.New("LRUCache结构体未初始化")
    }

    if pElement, ok := lru.cacheMap[k]; ok {
        lru.dlist.MoveToFront(pElement)
        pElement.Value.(*CacheNode).Value = v
        return nil
    }

    newElement := lru.dlist.PushFront(&CacheNode{k, v})
    lru.cacheMap[k] = newElement

    if lru.dlist.Len() > lru.Capacity {
        //移掉最后一个
        lastElement := lru.dlist.Back()
        if lastElement == nil {
            return nil
        }
        cacheNode := lastElement.Value.(*CacheNode)
        delete(lru.cacheMap, cacheNode.Key)
        lru.dlist.Remove(lastElement)
    }
    return nil
}

func (lru *LRUCache) Get(k interface{}) (v interface{}, ret bool, err error) {

    if lru.cacheMap == nil {
        return v, false, errors.New("LRUCache结构体未初始化")
    }

    if pElement, ok := lru.cacheMap[k]; ok {
        lru.dlist.MoveToFront(pElement)
        return pElement.Value.(*CacheNode).Value, true, nil
    }
    return v, false, nil
}

func (lru *LRUCache) Remove(k interface{}) bool {

    if lru.cacheMap == nil {
        return false
    }

    if pElement, ok := lru.cacheMap[k]; ok {
        cacheNode := pElement.Value.(*CacheNode)
        delete(lru.cacheMap, cacheNode.Key)
        lru.dlist.Remove(pElement)
        return true
    }
    return false
}

这里使用了 golang 自带的 list 库，其实底层就是一个双向链表

下面使用我们自己实现的双向链表来实现

type Node struct {
    Key int
    Value int
    pre, next *Node
}

type LUrCache struct {
    limit int
    HashMap map[int]*Node
    head, end *Node
}
func Constructor(capacity int) LRUCache {
    lruCache := LRUCache{limit:capacity}
    lruCache.HashMap = make(map[int]*Node, capacity)
    return lruCache
}

func (l *LRUCache) Get(key int) int {
    if v,ok:= l.HashMap[key];ok {
        l.refreshNode(v)
        return v.Value
    }else {
        return -1
    }
}

func (l *LRUCache) Put(key int, value int) {
    if v,ok := l.HashMap[key];!ok{
        if len(l.HashMap) >= l.limit{
            oldKey := l.removeNode(l.head)
            delete(l.HashMap, oldKey)
        }
        node := Node{Key:key, Value:value}
        l.addNode(&node)
        l.HashMap[key] = &node
    }else {
        v.Value = value
        l.refreshNode(v)
    }
}

func (l *LRUCache) refreshNode(node *Node) {
    if node == l.end {
        return
    }
    l.removeNode(node)
    l.addNode(node)
}

func (l *LRUCache) removeNode(node *Node) int {
    if node == l.end  {
        l.end = l.end.pre
        l.end.next = nil
    }else if node == l.head {
        l.head = l.head.next
        l.head.pre = nil
    }else {
        node.pre.next = node.next
        node.next.pre = node.pre
    }
    return node.Key
}

func (l *LRUCache) addNode(node *Node) {
    if l.end != nil {
        l.end.next = node
        node.pre = l.end
        node.next = nil
    }
    l.end = node
    if l.head == nil {
        l.head = node
    }
}