1 基本概念
LRU是一个老生常谈的问题，即最近最少使用，LRU是Least Recently Used的缩写，是一种操作系统中常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。
实现LRU基本的数据结构：Map+LinkedList
一般规则：
- 添加数据时，将新增数据节点放在头指针，尾结点部分大于最大长度时删除。
- 删除数据时，先按照Map的规则进行查找，再根据链表规则进行删除。
-
查找数据时，按照
Map进行查找，没有则返回空，有则返回该数据的值并移动到头节点。
2 代码实现
|
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 mainimport "fmt"var head *Nodevar end *Nodetype Node struct { Key string Value string pre *Node next *Node}func (n *Node) Init(key string, value string) { n.Key = key n.Value = value}type LRUCache struct { Capacity int //页面初始化大小 Size int //页面实际大小 Map map[string]*Node //具体的cache}func GetLRUCache(capacity int) *LRUCache { lruCache := LRUCache{Capacity: capacity} lruCache.Map = make(map[string]*Node, capacity) return &lruCache}func (l *LRUCache) get(key string) string { if v, ok := l.Map[key]; ok { l.refreshNode(v) return v.Value } else { return "null" }}func (l *LRUCache) put(key, value string) { if v, ok := l.Map[key]; !ok { if len(l.Map) >= l.Capacity { oldKey := l.removeNode(head) delete(l.Map, oldKey) } node := Node{Key: key, Value: value} l.addNode(&node) l.Map[key] = &node } else { v.Value = value l.refreshNode(v) }}func (l *LRUCache) refreshNode(node *Node) { if node == end { return } l.removeNode(node) l.addNode(node)}func (l *LRUCache) removeNode(node *Node) string { if node == end { end = end.pre } else if node == head { head = head.next } else { node.pre.next = node.next node.next.pre = node.pre } return node.Key}func (l *LRUCache) addNode(node *Node) { if end != nil { end.next = node node.pre = end node.next = nil } end = node if head == nil { head = node }} |
3 测试使用
|
1
2
3
4
5
6
7
8
9
10
11
12
|
func main() { lruCache := GetLRUCache(3) lruCache.put("001", "1") lruCache.put("002", "2") lruCache.put("003", "3") lruCache.put("004", "4") lruCache.put("005", "5") lruCache.get("002") fmt.Println(lruCache.get("001")) fmt.Println(lruCache.get("002")) fmt.Print(lruCache.Map)} |
到此这篇关于如何利用Go语言实现LRU Cache的文章就介绍到这了,更多相关Go实现LRU Cache内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://blog.csdn.net/Mr_YanMingXin/article/details/123022534
