Go 语言实现一个 LRU 缓存 ( 上 ) - 简单教程，简单编程

昨天，我对某个朋友说，我天生，就是对电脑啦写代码啦很该兴趣，但是，我对持续研究一门技术没啥大兴趣，基本就是想到什么写什么和学习什么。

所以，会造成一个很严重的后果，我的 Todo 列表里有很多还没研究完成的东西。最近因为工作需要，所以需要研究比特币，莱特币等。结果有一大堆计划了

今天我们就使用 Go 语言来实现一个 LRU ，也就是「最近最少使用」

在我的工作中，我经常发现自己必须实现一种将数据保存在内存中的方法，以便我以后可以使用它们。有时这是出于缓存目的，有时候是为了跟踪我之前发送过的其他服务，这样我就可以做一个比较或者其它事情，不管为什么，总之原因很多。

直到有一天，我注意到我一遍又一遍地写同一个版本的版本，当我们这样做时，也许是时候尝试创建一个更通用的解决方案了

让我们从简单的开始，好吗？

我们想要的是实现「最近最少使用」的列表（ LRU ）

对，不是复杂的，只是一个最简单的，不用大惊小怪

Naïve LRU

我们从一个简单而非常 Naïve 的实现开始吧。先定义一个如下结构

type LRU struct {
    cap int                           // 缓存的最大元素个数
    idx map[interface{}]*list.Element // 链表的索引
    l   *list.List                    // 实际存储数据的链表
}

对，就这么简单，简单三个属性 元素个数 、链表索引 和链表。我们使用了一个双向链表 l 来保存数据和一个 map 作为索引。

为了使用 list.List，我们需要引入 container/list 抱

import (
    "container/list"
)

然后，我们需要为 LRU 定义一个初始化器 New ，这是当前 Go 语言最时髦的做法，不是吗？

func New(cap int) *LRU {
    l := &LRU{
        cap: cap,
        l:   list.New(),
        idx: make(map[interface{}]*list.Element, cap+1),
    }
    return l
}

New 方法接收一个参数，就是缓存元素的个数，然后对 LRU 类型的各个属性进行初始化，并返回一个 LRU 实例。

这样，这个 LRU 的使用者就可以使用 l := lru.New(1000) 初始化一个可以缓存 1000 个元素的列表

虽然不定义一个 New 方法而是直接实例化一个 LRU 也是可以的，但，这不是我们所期待的使用方法

var l LRU
l.Add("hello", "world")

像上面这种方式，l 和 idx 属性并没有正确的被初始化。

如果真要实现这种不用事先指定缓存元素个数的机制 ( 经常有这种需求 ) ，那么我们可以定义一个懒初始化方法

func (l *LRU) lazyInit() {
    if l.l == nil {
        l.l = list.New()
        l.idx = make(map[interface{}]*list.Element, l.cap+1)
    }
}

方法很简单，就是判断 l.l 是否为 nil ，如果是则说明未初始化，否则已初始化。然后在未初始化的时候做一些初始化工作。

接下来，就是实现添加元素的方法 Add(k,v) ，其中第一个参数是键 k ，另一个参数是要保存的值 v ，方法定义如下

func (l *LRU) Add(k, v interface{}) {
    l.lazyInit()

    // 判断是否已经缓存键
    if le, ok := l.idx[k]; ok {
        // 更新缓存项并移动都链表的头部
        le.Value.(*entry).val = v
        l.l.MoveToFront(le)
        return
    }
    l.idx[k] = l.l.PushFront(&entry{key: k, val: v})

    if l.cap > 0 && l.l.Len() > l.cap {
        l.removeOldest()
    }
    return
}

方法看起来有点长，但是很简单的，一看就懂

使用 lazyInit() 判定是否已经初始化，没有则进行初始化工作
使用 le, ok := l.idx[k] 判定是否已经缓存了指定的键，如果存在则更新其值并移动到链表的头部
如果没有缓存，则将数据追加到链表的顶部，且根据 cap 和链表长度决定删除最旧的那些缓存

对了，我们的链表存储的东西，并不是缓存的实际值，而是另一个被称为键值对的类型，这个类型有两个属性 key 和 val

type entry struct {
    key, val interface{}
}