缓存算法 --- LRU算法
Redis的性能优越，应用普遍，可以存储的键值个数大到上亿条记录，依然保持较高的效率。作为一个内存数据库，Redis内部采用了字典（哈希表）的数据结构实现了键值对的存储。但是长期将Redis作为缓存使用，难免会遇到内存空间存储瓶颈，当Redis内存超出物理内存限制时，内存数据就会与磁盘产生频繁交换，使Redis性能急剧下降。此时如何淘汰无用数据释放空间?
LRU（Least recently used;最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是 “如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”。
注意LFU和LRU算法的不同之处，LRU的淘汰规则是基于访问时间，而LFU是基于访问次数的。
- 新增数据插入到哈希链表头部；
- 每当缓存命中（即缓存数据被再次访问到），则将数据重新移到链表头部；
- 当哈希链表存储满的时候，将链表尾部的数据丢弃；
- 最开始时，内存空间富余，数据A、B、C依次存储
- 当加入D时，内存空间不够了，因此根据LRU算法，内存空间中A待的时间最为久远，选择A，将其淘汰，此时B处于顶部
- 当再次访问B时，内存空间中的B又处于活跃状态，而C则变成了内存空间中，近段时间最久未使用的
- 当再次向内存空间加入E时，这时内存空间又不足了，选择在内存空间中待的最久的C将其淘汰出内存，这时的内存空间存放的对象就是E->B->D
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
|
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
| type Node struct {
Key int
Value int
pre *Node
next *Node
}
type LRUCache struct {
limit int
HashMap map[int]*Node
head *Node
end *Node
}
func Constructor(capacity int) LRUCache{
lruCache := LRUCache{limit:capacity}
lruCache.HashMap = make(map[int]*Node, capacity)
return lruCache
}
func (l *LRUCache) Get(key int) int {
if v,ok:= l.HashMap[key];ok {
l.refreshNode(v)
return v.Value
}else {
return -1
}
}
func (l *LRUCache) Put(key int, value int) {
if v,ok := l.HashMap[key];!ok{
if len(l.HashMap) >= l.limit{
oldKey := l.removeNode(l.head)
delete(l.HashMap, oldKey)
}
node := Node{Key:key, Value:value}
l.addNode(&node)
l.HashMap[key] = &node
}else {
v.Value = value
l.refreshNode(v)
}
}
func (l *LRUCache) refreshNode(node *Node){
if node == l.end {
return
}
l.removeNode(node)
l.addNode(node)
}
func (l *LRUCache) removeNode(node *Node) int{
if node == l.end {
l.end = l.end.pre
}else if node == l.head {
l.head = l.head.next
}else {
node.pre.next = node.next
node.next.pre = node.pre
}
return node.Key
}
func (l *LRUCache) addNode(node *Node){
if l.end != nil {
l.end.next = node
node.pre = l.end
node.next = nil
}
l.end = node
if l.head == nil {
l.head = node
}
}
|
