LRU算法
LRU算法就是Least Recently Used，最近最少使用算法。 是一种内存管理算法，当内存占用到达一定阈值时，就移除掉最近最少使用的数据。LRU算法的实现，基于双向链表。
LRU算法设计原则是：长期不被使用的数据，在未来被使用的概率也不大。
看图说话
假设现在有一个链表,存有4个数据，最大容量也为4，如下图：
1、当程序需要获取数据2时，把数据2的前后引用都移除，插入到链表最右端；把数据1的后引用改为数据3，把数据3的前引用改为数据1。
2、此时，程序如果插入一条新数据5，那么链表数据情况如下：
3、又因为链表最大容量为4，所以应该移除最前端的数据1,最终的数据顺序如下图：
以上，就是LRU算法的基本思路，无外乎以上几种情况交替出现。
Kotlin代码的简单实现
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
|
class Data constructor(val key:String,var value:String) {
var pre : Data? = null
var next : Data? = null
}
class LRUCache constructor(val max: Int = 4) {
private var head: Data? = null
private var end: Data? = null
private val map = HashMap<String, Data>()
fun get(key: String): String? {
val data = map[key] ?: return null
moveToLast(data)
return data.value
}
fun put(data: Data) {
if (map.contains(data.key)) { //存在
val old = map[data.key]
old!!.value = data.value
moveToLast(old)
} else { //不存在
if (map.size >= max) {
remove(head!!)
map.remove(head!!.key)
}
add(data)
map[data.key] = data
}
}
fun delete(key: String) {
val data = map[key]
if (null != data) {
remove(data)
map.remove(key)
}
}
private fun moveToLast(data: Data) {
if (end == data) {
return
}
remove(data)
add(data)
}
private fun remove(data: Data) {
when (data) {
end -> {
end = end!!.pre
}
head -> {
head = head!!.next
}
else -> { //中间情况，如文中所说的获取数据2的情况
data.pre!!.next = data.next
data.next!!.pre = data.pre
}
}
}
private fun add(data: Data) {
if (null == head) head = data
if (null != end) {
end!!.next = data
data.pre = end
data.next = null
}
end = data
}
fun print(){
var data:Data? = head
while(null != data){
println(data.value)
data = data.next
}
}
}
|
在Java中的实现是LinkedHashMap，线程不安全,继承自HashMap。
Android中缓存类LruCache，也是基于LinkedHashMap实现。
附件
lru.kt
延伸
Android缓存机制-LRU cache原理与用法
LruCache原理和用法与LinkedHashMap
LRU算法四种实现方式介绍