0x01. 说明

• 本文源码来源于互联网，本人保证公开部分不涉及任何公司的敏感信息，本人保证不传播任何敏感信息。
• 本文仅用于学术交流，请勿在商业用途中使用此源码，此源码并未执行任何开源授权。

0x02. 介绍

LRU全称为Least Recently Used，为内存管理算法的一种。通过淘汰最近最少使用的KEY来实现内存置换。

LRU的规则是最近调用的key排在列表的最前面。例如：set 3,set 4,set 5, 内存中key的排列应该是 543。然后get 4，内存刷新为453，再set 1，内存刷新为145。【注，排列顺序为阅读顺序，最左边为顶部】
从描述中可以看出，最近读取，最近更新的key，会排到队列的最顶部，该key之前的首尾会连接起来保持顺序。那么实现这种数据结构成为双向链表。

对于双向链表，了解数据结构的同学肯定不陌生，本着解读的目的，我们来介绍下什么是双向链表。

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

有一点需要注意的是，队列的顶部和底部并不是相连的（LRU不是循环双向链表），所以我们需要有一个head指针，和tail指针来保存头尾信息。

对于双向链表的实现不是本文讨论的重点，在这里略过。我们重点是解读LRU的实现。

0x03. LRU Cache实现

从上面的示意图中，我们需要定义一个结构体，包含四个元素，next指针，prev指针，key和value字段。在golang中可以使用interface{}作为泛型支持。
实现如下：

type Element struct {
    prev, next *Element
    Key        interface{}
    Value      interface{}
}

整个LRUCache的结构如下，head为头指针，tail为尾指针，capacity为队列长度，【为什么要指定长度，因为是内存置换，属于虚拟内存，所以肯定是要限制长度来使用的】。
cache 为字典结构存储Element元素（以我的理解其中Element.key 为冗余设计，应该是可以省略Element.key字段）。

type LRUCache struct {
    cache    map[interface{}]*Element
    head     *Element
    tail     *Element
    capacity int
}

那么剩下的就是实现几个方法，『内存开辟』，『设置值』，『更新队列』，『删除元素』。具体实现可以看下面的源代码

package lrucache

// Element - node to store cache item
type Element struct {
    prev, next *Element
    Key        interface{}
    Value      interface{}
}

// Next - fetch older element
func (e *Element) Next() *Element {
    return e.next
}

// Prev - fetch newer element
func (e *Element) Prev() *Element {
    return e.prev
}

// LRUCache - a data structure that is efficient to insert/fetch/delete cache items [both O(1) time complexity]
type LRUCache struct {
    cache    map[interface{}]*Element
    head     *Element
    tail     *Element
    capacity int
}

// New - create a new lru cache object
func New(capacity int) *LRUCache {
    return &LRUCache{make(map[interface{}]*Element), nil, nil, capacity}
}

// Put - put a cache item into lru cache
func (lc *LRUCache) Put(key interface{}, value interface{}) {
    if e, ok := lc.cache[key]; ok {
        e.Value = value
        lc.refresh(e)
        return
    }

    if lc.capacity == 0 {
        return
    } else if len(lc.cache) >= lc.capacity {
        // evict the oldest item
        delete(lc.cache, lc.tail.Key)
        lc.remove(lc.tail)
    }

    e := &Element{nil, lc.head, key, value}
    lc.cache[key] = e
    if len(lc.cache) != 1 {
        lc.head.prev = e
    } else {
        lc.tail = e
    }
    lc.head = e
}

// Get - get value of key from lru cache with result
func (lc *LRUCache) Get(key interface{}) (interface{}, bool) {
    if e, ok := lc.cache[key]; ok {
        lc.refresh(e)
        return e.Value, ok
    }
    return nil, false
}

// Delete - delete item by key from lru cache
func (lc *LRUCache) Delete(key interface{}) {
    if e, ok := lc.cache[key]; ok {
        delete(lc.cache, key)
        lc.remove(e)
    }
}

// Range - calls f sequentially for each key and value present in the lru cache
func (lc *LRUCache) Range(f func(key, value interface{}) bool) {
    for i := lc.head; i != nil; i = i.Next() {
        if !f(i.Key, i.Value) {
            break
        }
    }
}

// Update - inplace update
func (lc *LRUCache) Update(key interface{}, f func(value *interface{})) {
    if e, ok := lc.cache[key]; ok {
        f(&e.Value)
        lc.refresh(e)
    }
}

// Front - get front element of lru cache
func (lc *LRUCache) Front() *Element {
    return lc.head
}

// Back - get back element of lru cache
func (lc *LRUCache) Back() *Element {
    return lc.tail
}

// Len - length of lru cache
func (lc *LRUCache) Len() int {
    return len(lc.cache)
}

// Capacity - capacity of lru cache
func (lc *LRUCache) Capacity() int {
    return lc.capacity
}

func (lc *LRUCache) refresh(e *Element) {
    if e.prev != nil {
        e.prev.next = e.next
        if e.next == nil {
            lc.tail = e.prev
        } else {
            e.next.prev = e.prev
        }
        e.prev = nil
        e.next = lc.head
        lc.head.prev = e
        lc.head = e
    }
}

func (lc *LRUCache) remove(e *Element) {
    if e.prev == nil {
        lc.head = e.next
    } else {
        e.prev.next = e.next
    }
    if e.next == nil {
        lc.tail = e.prev
    } else {
        e.next.prev = e.prev
    }
}