LRU算法是一种页面置换算法。常见的页面置换算法包括：random、FIFO、LRU、LFU。

采用随机random的置换算法效率并不好，没有利用好页面置换调度序列的信息，更加没有考虑程序的局部性原理。

FIFO实现简单，但没有利用好程序的局部性原理，会出现Belady现象。Belady现象指系统分配的页面数增加了，可是缺页率依然在增加。可以配合程序的局部性原理来理解这一点。我们考虑一个球体，随着它的体积的正大，表面积与体积的比反而变小。FIFO就像一个体积不断变大的球体，但根据程序的局部性原理，下次进程需要的页面将会在一个更大的球体表明中寻找。

LRU算法（Least Rencently Used，最不近使用），是最能利用程序的局部性原理的算法。在有限的Cache中，当Cache到达临界时，淘汰掉最不常使用的页面。直观上，最近使用和最不近使用的页面分表排在队列的尾部和首部。注意，最近和最常是有差别的，前者是和当前时间戳对比，后者是关于使用过的频率。LRU算法可能会把最频繁使用的页面淘汰。

类似LRU算法，LFU算法为每个进入Cache中的页面添加计数器，根据页面使用的统计频率来淘汰页面。在有限的Cache中，当Cache到达临界区（使用上限），把使用频率最低的先淘汰掉。LFU的一个缺点是，它可能会把最近使用过的页面也淘汰出去（只要它频率低）

LRU关注的是最近：和当前时间戳比较
LFU关注的是最常：一个关于页面使用过的统计次数

这两种算法不能说那种算法优秀，只能视使用场景而定。通常情况下，我们会使用LRU算法策略做备忘录。

下面给出LRU算法的Go语言实现。

原理剖析

在LRU算法中，直观理解，页面是有序的，排序依据是最不近或最近。除了有序，序列元素键位置的变更需要灵活。因此考虑使用双向链表。

另外就是快速定位页面的位置，不用多说，我们会考虑使用map这种基于散列的数据结构，保证添加删除时间复杂度为O(1)。

因此：本实现使用双向链表+基于散列的map

实现

实现双链表

结点的定义

1
2
3
4
5
6
type Node struct {
    key   string
    value string
    next  *Node
    prev  *Node
}

双链表定义和封装

1
2
3
4
5
6
7
8
9
10
11
12
type List struct {
    root Node
    len  int
}

func NewList() *List {
    l := new(List)
    l.root.next = &l.root
    l.root.prev = &l.root
    l.len = 0
    return l
}

双链表的操作方法。只实现需要使用的接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func (l *List) Len() int {
    return l.len
}

func (l *List) Front() *Node {
    if l.len == 0 {
        return nil
    }
    return l.root.next
}

func (l *List) insert(e, at *Node) *Node {
    n := at.next
    at.next = e
    e.prev = at
    e.next = n
    n.prev = e
    l.len++
    return e
}

func (l *List) remove(e *Node) *Node {
    e.prev.next = e.next
    e.next.prev = e.prev
    e.next = nil
    e.prev = nil
    l.len--
    return e
}

func (l *List) moveToBack(e *Node) {
    if l.root.prev == e {
        return
    }
    l.insert(l.remove(e), l.root.prev)
}

func (l *List) appendToBack(e *Node) {
    l.insert(e, l.root.prev)
}

实现LRU算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
type LRUCache struct {
    data map[string]*Node
    root *List
    size int
}

func NewLRUCache(size int) *LRUCache {
    cache := new(LRUCache)
    cache.size = size
    cache.root = NewList()
    cache.data = make(map[string]*Node, size)
    return cache
}

func (cache *LRUCache) Put(key, value string) {
    node, ok := cache.data[key]
    if ok {
        node.value = value
        cache.root.moveToBack(node)
        return
    }
    if cache.size == len(cache.data) {
        temp := cache.root.Front()
        cache.root.remove(temp)
        delete(cache.data, temp.key)
    }
    node = &Node{
        key:   key,
        value: value,
    }
    cache.root.appendToBack(node)
    cache.data[key] = node
}

func (cache *LRUCache) Get(key string) string {
    node, ok := cache.data[key]
    if ok {
        cache.root.moveToBack(node)
        return node.value
    }
    return ""
}

编写简单的测试，详细的测试可以使用在线工具

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func main() {
    cache := NewLRUCache(2)
    cache.Put("1", "1")
    cache.Put("2", "2")
    fmt.Println(cache.Get("1"))

    cache.Put("3", "3")
    fmt.Println(cache.Get("2"))
    fmt.Println(cache.data)

    cache.Put("4", "4")
    fmt.Println(cache.data)

    fmt.Println(cache.Get("1"))
    fmt.Println(cache.Get("3"))
    fmt.Println(cache.Get("4"))
}

另外一种实现

由于go内置了双链表container/list，可以直接使用它及其方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package main

import (
    "container/list"
    "fmt"
)

type LRUCache struct {
    Size  int
    list  *list.List
    cache map[string]*list.Element
}

type Entry struct {
    Key   string
    Value interface{}
}

func NewLRUCache(size int) *LRUCache {
    return &LRUCache{
        Size:  size,
        list:  list.New(),
        cache: make(map[string]*list.Element),
    }
}

func (c *LRUCache) Add(key string, value interface{}) {
    if c.cache == nil {
        c.cache = make(map[string]*list.Element)
        c.list = list.New()
    }
    // 获取到缓存后把它已到双链表最前，表示最热数据
    if e, ok := c.cache[key]; ok {
        c.list.MoveToFront(e)
        e.Value.(*Entry).Value = value
        return
    }
    entry := &Entry{Key: key, Value: value}
    e := c.list.PushFront(entry)
    c.cache[key] = e
    // 缓存有限，把最不热的数据移走
    if c.Size != 0 && c.list.Len() > c.Size {
        e := c.list.Back()
        if e != nil {
            c.list.Remove(e)
            delete(c.cache, e.Value.(*Entry).Key)
        }
    }
}

func (c *LRUCache) Get(key string) interface{} {
    if c.cache == nil {
        return nil
    }
    if e, ok := c.cache[key]; ok {
        c.list.MoveToFront(e)
        return e.Value.(*Entry).Value
    }
    return nil
}

func (c *LRUCache) Remove(key string) {
    if c.cache == nil {
        return
    }
    if e, ok := c.cache[key]; ok {
        c.list.Remove(e)
        delete(c.cache, e.Value.(*Entry).Key)
    }
}

func (c *LRUCache) Len() int {
    return c.list.Len()
}

func main() {
    cache := NewLRUCache(2)
    cache.Add("a", 1)
    cache.Add("b", 2)
    cache.Add("c", 3)

    fmt.Println(cache.Get("a"))
    fmt.Println(cache.Get("b"))
    fmt.Println(cache.Get("c"))
}

双链表借助container/list代码更简洁。

结语

如果你把上述的实现读下来了，你会发现，第一种实现不就是Java的LinkedHashMap吗？是的。在Java中直接使用该容器就可以实现LRU算法。