需求概述

实现一个满足LRU缓存的数据结构，即有一个容器，可以存放key-value型的数据，有以下功能：

  • 根据缓存最大容量构造该缓存数据结构

  • 能够根据key获取相应的value，若缓存未命中则返回相应异常标志

  • 可以放入一个kv数据，若已存在则变更value，若不存在，则淘汰最久未使用的kv对

  • 还能够获得当前容器已存放的kv数目

  • 可以删除指定kv对，可以清空缓存

问题分析

使用golang实现该数据结构，即定义一个结构体，实现如下LRU接口

为了通用起见，key,value不限定类型，即interface{}类型

1
2
type Key interface{}
type Value interface{}

设计一个结构体，实现如下接口方法

1
2
3
4
5
6
7
type LRU interface {
    Get(key Key) (value Value, ok bool)
    Put(key Key, value Value)
    Remove(key Key)
    Len() int
    Clear()
}

首先尽可能高效的存储kv对，故考虑使用哈希表存储，即golang中的map

为了实现淘汰机制，我们需要频繁地对元素顺序进行调整，故考虑使用链表数据结构，即golang中的list.List

定义结构体即构造函数如下，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type Cache struct {
    maxCapacity int
    linkedList  *list.List
    table       map[Key]*list.Element
}

func NewCache(maxCapacity int) *Cache {
    return &Cache{
        maxCapacity: maxCapacity,
        linkedList:  list.New(),
        table:       make(map[Key]*list.Element),
    }
}

...

当Get/Put某个kv时，若已存在指定key则将该链表节点移动到头部，若新增元素，则在头部放入新链表节点

当Put新元素时，淘汰最末尾的节点kv

当删除某个kv时需要根据key定位到目标链表节点，故hash表类型为map[Key]*list.Element

测试代码

使用测试驱动开发（TDD）的思想，可以先编写测试代码如下，

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
86
87
88
89
90
91
92
93
94
95
96
97
package lru

import (
	"github.com/stretchr/testify/assert"
	"testing"
)

func TestNewCache(t *testing.T) {
	cache := NewCache(5)
	assert.NotNil(t, cache)
}

func TestCache_Put(t *testing.T) {
	cache := NewCache(5)
	cache.Put("k1", "v1")
	assert.Equal(t, 1, cache.Len())
	cache.Remove("k1")
	assert.Equal(t, 0, cache.Len())
}

func TestCache_Remove(t *testing.T) {
	cache := NewCache(5)
	assert.Equal(t, 0, cache.Len())

	cache.Remove("k1")
	assert.Equal(t, 0, cache.Len())

	cache.Put("k1", "v1")
	assert.Equal(t, 1, cache.Len())

	cache.Remove("k1")
	assert.Equal(t, 0, cache.Len())
}

func TestCache_Get(t *testing.T) {
	cache := NewCache(1)
	var val Value
	var ok bool
	// 正常情况
	{
		cache.Put("k1", "v1")
		val, ok = cache.Get("k1")
		assert.True(t, ok)
		assert.Equal(t, "v1", val)
		assert.Equal(t, 1, cache.Len())
		cache.Clear()
	}

	// 异常情况
	{
		// 找不到k2
		{
			_, ok = cache.Get("k2")
			assert.False(t, ok)
		}

		// k1被k2置换找不到k1但能找到k2
		{
			cache.Put("k1", "v1")
			cache.Put("k2", "v2")
			_, ok = cache.Get("k1")
			assert.False(t, ok)

			val, ok = cache.Get("k2")
			assert.True(t, ok)
			assert.Equal(t, "v2", val)
			cache.Clear()
		}

	}
}

func TestCache_Len(t *testing.T) {
	cache := NewCache(1)
	assert.Equal(t, 0, cache.Len())

	cache.Put("k1", "v1")
	assert.Equal(t, 1, cache.Len())

	cache.Put("k2", "v2")
	assert.Equal(t, 1, cache.Len())
}

func TestCache_Clear(t *testing.T) {
	cache := NewCache(1)
	assert.Equal(t, 0, cache.Len())

	cache.Put("k1", "v1")
	assert.Equal(t, 1, cache.Len())

	cache.Put("k2", "v2")
	assert.Equal(t, 1, cache.Len())

	cache.Clear()
	assert.Equal(t, 0, cache.Len())
}

实现代码

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
package lru

import "container/list"

type Key interface{}
type Value interface{}

type LRU interface {
	Get(key Key) (value Value, ok bool)
	Put(key Key, value Value)
	Remove(key Key)
	Len() int
	Clear()
}

type kv struct {
	key   Key
	value Value
}
type Cache struct {
	maxCapacity int
	linkedList  *list.List
	table       map[Key]*list.Element
}

func NewCache(maxCapacity int) *Cache {
	return &Cache{
		maxCapacity: maxCapacity,
		linkedList:  list.New(),
		table:       make(map[Key]*list.Element),
	}
}

// Get / 获取缓存内容
func (c *Cache) Get(key Key) (value Value, ok bool) {
	if v, ok := c.table[key]; ok {
		c.linkedList.MoveToFront(v)
		return v.Value.(*kv).value, true
	}
	return nil, false
}

// Put / 放入一个kv
func (c *Cache) Put(key Key, value Value) {
	if v, ok := c.table[key]; ok {
		c.linkedList.MoveToFront(v)
		v.Value.(*kv).value = value
	} else {
		c.table[key] = c.linkedList.PushFront(&kv{
			key:   key,
			value: value,
		})
		if c.maxCapacity < c.linkedList.Len() {
			// 淘汰最久没用的
			e := c.linkedList.Back()
			if e != nil {
				c.linkedList.Remove(e)
				kv := e.Value.(*kv)
				delete(c.table, kv.key)
			}
		}
	}
}

// Remove / 移除一个指定的key的kv
func (c *Cache) Remove(key Key) {
	if v, ok := c.table[key]; ok {
		c.linkedList.Remove(v)
		kv := v.Value.(*kv)
		delete(c.table, kv.key)
	}
}

// Len / 获取当前已缓存的数量
func (c *Cache) Len() int {
	return c.linkedList.Len()
}

// Clear / 清空缓存
func (c *Cache) Clear() {
	c.linkedList = list.New()
	c.table = make(map[Key]*list.Element)
}