关于LRU，可以参考LRU LFU FIFO
LRU全称是Least Recently Used，即最近最久未使用的意思。如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。而用什么数据结构来实现LRU算法呢？
可能大多数人都会想到：用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。这种实现思路很简单，但是有什么缺陷呢？需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。
那么有没有更好的实现办法呢？
那就是利用链表移动访问时间的数据顺序和hashmap查询是否是新数据项。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。
关于链表，参考Golang源码 container 系列二 list链表
以下内容，参考protobuf、LRU、sigleflight
//lru.go
1// Package lru implements an LRU cache.
2//【lru包用于实现LRU cache】
3package lru
4
5import "container/list"
6
7// Cache is an LRU cache. It is not safe for concurrent access.
8//【Cache结构用于实现LRU cache算法；并发访问不安全】
9type Cache struct {
10 // MaxEntries is the maximum number of cache entries before
11 // an item is evicted. Zero means no limit.
12 //【最大入口数，也就是缓存中最多存几条数据，超过了就触发数据淘汰；0表示没有限制】
13 MaxEntries int
14
15 // OnEvicted optionally specificies a callback function to be
16 // executed when an entry is purged from the cache.
17 //【销毁前回调】
18 OnEvicted func(key Key, value interface{})
19
20 //【链表】
21 ll *list.List
22 //【key为任意类型，值为指向链表一个结点的指针】
23 cache map[interface{}]*list.Element
24}
25
26// A Key may be any value that is comparable.
27// See http://golang.org/ref/spec#Comparison_operators
28//【任意可比较类型】
29type Key interface{}
30
31//【访问入口结构，包装键值】
32type entry struct {
33 key Key
34 value interface{}
35}
36
37// New creates a new Cache.
38// If maxEntries is zero, the cache has no limit and it's assumed
39// that eviction is done by the caller.
40//【初始化一个Cache类型实例】
41func New(maxEntries int) *Cache {
42 return &Cache{
43 MaxEntries: maxEntries,
44 ll: list.New(),
45 cache: make(map[interface{}]*list.Element),
46 }
47}
48
49// Add adds a value to the cache.
50//【往缓存中增加一个值】
51func (c *Cache) Add(key Key, value interface{}) {
52 //【如果Cache还没有初始化，先初始化，创建cache和l1】
53 if c.cache == nil {
54 c.cache = make(map[interface{}]*list.Element)
55 c.ll = list.New()
56 }
57 //【如果key已经存在，则将记录前移到头部，然后设置value】
58 if ee, ok := c.cache[key]; ok {
59 c.ll.MoveToFront(ee)
60 ee.Value.(*entry).value = value
61 return
62 }
63 //【key不存在时，创建一条记录，插入链表头部，ele是这个Element的指针】
64 //【这里的Element是一个*entry类型，ele是*list.Element类型】
65 ele := c.ll.PushFront(&entry{key, value})
66 //cache这个map设置key为Key类型的key，value为*list.Element类型的ele
67 c.cache[key] = ele
68 //【链表长度超过最大入口值，触发清理操作】
69 if c.MaxEntries != 0 && c.ll.Len() > c.MaxEntries {
70 c.RemoveOldest()
71 }
72}
73
74// Get looks up a key's value from the cache.
75//【根据key查找value】
76func (c *Cache) Get(key Key) (value interface{}, ok bool) {
77 if c.cache == nil {
78 return
79 }
80 //【如果存在】
81 if ele, hit := c.cache[key]; hit {
82 //【将这个Element移动到链表头部】
83 c.ll.MoveToFront(ele)
84 //【返回entry的值】
85 return ele.Value.(*entry).value, true
86 }
87 return
88}
89
90// Remove removes the provided key from the cache.
91//【如果key存在，调用removeElement删除链表and缓存中的元素】
92func (c *Cache) Remove(key Key) {
93 if c.cache == nil {
94 return
95 }
96 if ele, hit := c.cache[key]; hit {
97 c.removeElement(ele)
98 }
99}
100
101// RemoveOldest removes the oldest item from the cache.
102//【删除最旧的元素】
103func (c *Cache) RemoveOldest() {
104 if c.cache == nil {
105 return
106 }
107 //【ele为*list.Element类型，指向链表的尾结点】
108 ele := c.ll.Back()
109 if ele != nil {
110 c.removeElement(ele)
111 }
112}
113
114func (c *Cache) removeElement(e *list.Element) {
115 //【链表中删除一个element】
116 c.ll.Remove(e)
117 //【e.Value本质是*entry类型，entry结构体就包含了key和value2个属性】
118 //【Value本身是interface{}类型，通过类型断言转成*entry类型】
119 kv := e.Value.(*entry)
120 //【删除cache这个map中key为kv.key这个元素；也就是链表中删了之后缓存中也得删】
121 delete(c.cache, kv.key)
122 if c.OnEvicted != nil {
123 c.OnEvicted(kv.key, kv.value)
124 }
125}
126
127// Len returns the number of items in the cache.
128//【返回缓存中的item数，通过链表的Len()方法获取】
129func (c *Cache) Len() int {
130 if c.cache == nil {
131 return 0
132 }
133 return c.ll.Len()
134}
135
136// Clear purges all stored items from the cache.
137//【删除缓存中所有条目，如果有回调函数OnEvicted()，则先调用所有回调函数，然后置空】
138func (c *Cache) Clear() {
139 if c.OnEvicted != nil {
140 for _, e := range c.cache {
141 kv := e.Value.(*entry)
142 c.OnEvicted(kv.key, kv.value)
143 }
144 }
145 c.ll = nil
146 c.cache = nil
147}
具体用法，可以参考lru_test.go
有疑问加站长微信联系（非本文作者）
