什么是LRU Cache
LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。 什么是Cache？狭义的Cache指的是位于CPU和主存间的快速RAM， 通常它不像系统主存那样使用DRAM技术，而使用昂贵但较快速的SRAM技术。 广义上的Cache指的是位于速度相差较大的两种硬件之间， 用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache， 内存与硬盘之间也有Cache，乃至在硬盘与网络之间也有某种意义上的Cache── 称为Internet临时文件夹或网络内容缓存等。
Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时， 就需要挑选并舍弃原有的部分内容，从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉(还有一种是FIFO方式进行缓存替换)。其实，LRU译成最久未使用会更形象， 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。
数据结构
LRU一般是由双向链表结合一个hash结构实现， 双向链表用于存储数据结点，并且它是按照结点最近被使用的时间来存储的。 如果一个结点被访问了， 我们有理由相信它在接下来的一段时间被访问的概率要大于其它结点。于是， 我们把它放到双向链表的头部。当我们往双向链表里插入一个结点， 我们也有可能很快就会使用到它，同样把它插入到头部。 我们使用这种方式不断地调整着双向链表，链表尾部的结点自然也就是最近一段时间， 最久没有使用到的结点。那么，当我们的Cache满了， 需要替换掉的就是双向链表中最后的那个结点(不是尾结点，头尾结点不存储实际内容)。
对外暴露的接口
LRUCache对外暴露三个接口
Get(K key)
Put(K key, V value)
当我们初始化的时候只需要调用NewLRUCache(capacity)即可初始化我们的Cache的容量，需要塞数据的时候调用Put方法，需要获取数据的时候调用Get方法。
当我们通过键值来访问类型为T的数据时，调用Get函数。如果键值为key的数据不存在在Cache中就返回-1；如果已经在 Cache中，那就返回该数据，同时将存储该数据的结点移到双向链表头部。 如果我们查询的数据不在Cache中，我们就可以通过Put接口将数据插入双向链表中。 如果此时的Cache还没满，那么我们将新结点插入到链表头部， 同时用哈希表保存结点的键值及结点地址对。如果Cache已经满了， 我们就将链表中的最后一个结点(注意不是尾结点)的内容替换为新内容， 然后移动到头部，更新哈希表。
GO 代码
➜ lru cat lru.go
package lru
import "fmt"
type Node struct {
Key interface{}
Value interface{}
Prev *Node
Next *Node
}
type LRUCache struct {
Head, Tail *Node
Capacity int
Map map[interface{}]*Node
}
func NewLRUCache(capacity int) *LRUCache {
l := &LRUCache{}
l.Capacity = capacity
l.Head = &Node{}
l.Tail = &Node{}
l.Head.Next = l.Tail
l.Tail.Prev = l.Head
l.Head.Prev = nil
l.Tail.Next = nil
l.Map = make(map[interface{}]*Node)
return l
}
//分离节点
func (l *LRUCache) detach(n *Node) {
n.Prev.Next = n.Next
n.Next.Prev = n.Prev
}
//节点插入头部
func (l *LRUCache) attach(n *Node) {
n.Prev = l.Head
n.Next = l.Head.Next
l.Head.Next = n
n.Next.Prev = n
}
func (l *LRUCache) Put(k interface{}, v interface{}) {
oldV, ok := l.Map[k]
if ok {
l.detach(oldV)
oldV.Value = v
} else {
var n *Node
if len(l.Map) >= l.Capacity {
n = l.Tail.Prev
l.detach(n)
delete(l.Map, n.Key)
} else {
n = new(Node)
}
n.Key = k
n.Value = v
l.Map[k] = n
l.attach(n)
}
}
func (l *LRUCache) Get(k interface{}) interface{} {
v, ok := l.Map[k]
if ok {
l.detach(v)
l.attach(v)
return v.Value
}
return -1
}
func main() {
l := NewLRUCache(10)
l.Put("str", 1)
fmt.Println(l.Get("str"))
l.Put(1, 2)
fmt.Println(l.Get(1))
fmt.Println(l.Get("str").(int))
}
➜ lru cat lru_test.go
package lru
import (
"testing"
)
func testEq(a, b []int) bool {
if a == nil && b == nil {
return true
}
if a == nil || b == nil {
return false
}
if len(a) != len(b) {
return false
}
for i := range a {
if a[i] != b[i] {
return false
}
}
return true
}
func Test_Get(t *testing.T) {
l := NewLRUCache(2)
l.Put("sky", "SKY")
if l.Get("sky") != "SKY" {
t.Error("test get sky failed!!!")
} else {
t.Log("test get sky success")
}
l.Put("sky1", 2)
if l.Get("sky1") != 2 {
t.Error("test get sky1 failed!!!")
} else {
t.Log("test get sky1 success")
}
l.Put("sky2", []int{1, 2})
if testEq(l.Get("sky2").([]int), []int{1, 2}) {
t.Log("test get sky2 success")
} else {
t.Error("test get sky2 failed!!!")
}
if l.Get("sky") != -1 {
t.Error("test get sky failed!!!")
} else {
t.Log("test get sky success")
}
if l.Get("sky1") != 2 {
t.Error("test get sky1 failed!!!")
} else {
t.Log("test get sky1 success")
}
}
func BenchmarkAdd(b *testing.B) {
l := NewLRUCache(100)
for i := 0; i < b.N; i++ {
l.Put(i, i*i)
}
}
➜ lru go version
go version go1.5 linux/amd64
➜ lru go test -v lru.go lru_test.go
=== RUN Test_Get
--- PASS: Test_Get (0.00s)
lru_test.go:31: test get sky success
lru_test.go:37: test get sky1 success
lru_test.go:41: test get sky2 success
lru_test.go:48: test get sky success
lru_test.go:54: test get sky1 success
PASS
ok command-line-arguments 0.003s
➜ lru go test -test.bench=".*" lru_test.go lru.go
PASS
BenchmarkAdd-2 3000000 421 ns/op
ok command-line-arguments 1.695s