本文共 3565 字，大约阅读时间需要 11 分钟。

注：本文使用golang语言表述。

LRU（least recently used）是一个缓存剔除策略算法，在缓存容量不足的时候，将最不常用的一个或多个缓存相剔除，腾出空间以便后续缓存使用。

实现一个LRU cache

LRU cache可以使用两个数据结构来表示。

• 一个hashtable，用来存储需要存储的缓存项，这样，get/set操作可以在O(1)时间复杂度下完成。
• 一个doubly list用来记录缓存项的最近使用情况，例如，如果最近使用过的项，则该项在doubly list的队首，最不常用的项在队尾。正是经常使用队首队尾，所以才使用doubly list数据结构。

首先对需要缓存的对象进行抽象，用一个interface来表示。

type Cacheable interface {        Key() string        Size() int}

对缓存项定义

type LRUCacheItem struct {        cacheable Cacheable        listElement *list.Element}

缓存项LRUCacheItem里记录了需要缓存对对象以及其对应的链表元素的指针，这个指针用来快速操作缓存链表，后面会详细表述。

对整体缓存定义

type LRUCache struct {        capcity int        items map[string]*LRUCacheItem        list *list.List}

缓存LRUCache包含三个字段：capcity表示当前缓存剩余容量。items是一个hashtable，用来记录LRUCacheItem，list用来给LRUCacheItem排队。

数据结构都定义好了，下面生成一个cache。

func New(capcity int) *LRUCache {        return &LRUCache{                capcity: capcity,                items: make(map[string]*LRUCacheItem),                list: list.New(),        }}

定义get操作:

func (c *LRUCache) get(key string) Cacheable {        item, exists := c.items[key]        if !exists {                return nil        }        c.promote(item) // 因为刚刚用到，所以将该item提到队首        return item.cacheable}// 将item提到队首func (c *LRUCache) promote(item *LRUCacheItem) {        c.list.MoveToFront(item.listElement)}

定义set操作：

func (c *LRUCache) set(cacheable Cacheable) bool {        if c.capcity < cacheable.Size() {                c.prune() // 空间不足，剔除不常用队缓存项        }        if c.capcity < cacheable.Size() {                return false        }        if item, exists := c.items[cacheable.Key()]; exists {                c.promote(item)                return true        }        key := cacheable.Key()        item := &LRUCacheItem{                cacheable: cacheable,                listElement: c.list.PushFront(key),        }        c.items[key] = item        c.capcity -= cacheable.Size()        return true}// 剔除不常用队缓存项。从队尾开始剔除。func (c *LRUCache) prune() {        for i := 0; i < 50; i++ {                tail := c.list.Back()                if tail == nil {                        return                }                key := c.list.Remove(tail)                item := c.items[key.(string)]                delete(c.items, key.(string))                c.capcity += item.cacheable.Size()        }}

到这里，LRUCache算是实现完了。接下来体验一下。

type p struct {key string}type a struct {key string}func (p) Size() int {        return 10}func (p p) Key() string {        return p.key}func (a) Size() int {        return 5}func (a a) Key() string {        return a.key}func init() {        rand.Seed(time.Now().UnixNano())}const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"func randstring(l int) string {        r := make([]rune, l)        for i := range r {                r[i] = rune(letters[rand.Intn(len(letters))])        }        return string(r)}func main() {        p1 := p{key: randstring(6)}        lc := New(30)        fmt.Println(lc.get(p1.Key()))        lc.set(p1)        fmt.Println(lc.get(p1.Key()))        p2 := p{key: randstring(6)}        lc.set(p2)        fmt.Println(lc.get(p2.Key()))        p3 := p{key: randstring(6)}        lc.set(p3)        fmt.Println(lc.get(p3.Key()))        fmt.Println(lc.items)        fmt.Println(lc.list.Front().Value)        lc.get(p1.Key())        fmt.Println(lc.list.Front().Value)        a4 := a{key: randstring(4)}        fmt.Println(lc.get(a4.Key()))        lc.set(a4)        fmt.Println(lc.items, lc.list.Len())}

这里查看

实际的使用其实还需要添加并发控制。可以粗略地在get/set函数里添加mutux。当然最好是为 LRUCache 里的 hashtable 和 list分别添加 read-write mutex。

referce to: