LRU算法的Java实现(两种实现+增强实现)

LRU 算法

LRU 全称是 Least Recently Used,即最近最久未使用的意思。

LRU算法的设计原则是:如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小。也就是说,当限定的空间已存满数据时,应当把最久没有被访问到的数据淘汰。

LRU 接口设计

有了上面的设计原则,就可以得出设计一个带有 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
public interface LruCache<K, V> {

/**
* 插入数据
* 当容器满的时候,将最久访问的数据从容器中移除,
* 并将新加入的数据放入容器中
* @param key
* @param value
*/
void put(K key, V value);

/**
* 获取数据
* @param key
* @return
*/
V get(K key);

/**
* 将指定元素从容器中移除
* @param key
*/
void remove(K key);

/**
* 清空缓存
*/
void clear();

/**
* 缓存当前已存有效数据的容量大小
* @return
*/
int size();

/**
* 当前缓存容器的最大可缓存容量
* @return
*/
int limit();
}

说明:在实现 LRU 算法容器过程中,对参数校验笔者使用到了 guava 工具包:https://mvnrepository.com/artifact/com.google.guava/guava

1
2
3
4
5
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>29.0-jre</version>
</dependency>

实现1:利用 LinkedHashMap 实现

在 Java 中,LinkedHashMap 天然实现了 LRU 算法,因此我们可以设计一个 Cache 对象,内部自己维护一个 LinkedHashMap 容器,重写掉 removeEldestEntry() 方法即可。

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
import com.google.common.base.Preconditions;

import java.util.LinkedHashMap;
import java.util.Map;

/**
* @projectName: guava
* @author: woodwhales
* @date: 20.7.4 21:02
* @description: 使用LinkedHashMap实现带LRU的缓存
* 本类不是一个线程安全的
*/
public class LinkedHashMapLruCache<K, V> implements LruCache<K, V> {

private final int limit;

private final InternalLruLinkedHashMapCache<K, V> cache;

@Override
public void put(K key, V value) {
this.cache.put(key, value);
}

@Override
public V get(K key) {
return this.cache.get(key);
}

@Override
public void remove(K key) {
this.cache.remove(key);
}

@Override
public void clear() {
this.cache.clear();
}

@Override
public int size() {
return this.cache.size();
}

@Override
public int limit() {
return this.limit;
}

@Override
public String toString() {
return this.cache.toString();
}

private static class InternalLruLinkedHashMapCache<K, V> extends LinkedHashMap<K, V> {
private int limit;

public InternalLruLinkedHashMapCache(int limit) {
super(limit, 0.75f, true);
this.limit = limit;
}

@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return this.size() > this.limit;
}
}

public LinkedHashMapLruCache(int limit) {
Preconditions.checkArgument(limit > 0, "this limit must big than zero.");
this.limit = limit;
this.cache = new InternalLruLinkedHashMapCache<>(limit);
}

}

为什么 LinkedHashMapLruCache 不直接继承 LinkedHashMap,而是在内部维护一个静态内部类呢?因为保证接口实现的“纯洁性”,LinkedHashMapLruCache 的使用者随便继承使用或直接使用,也只能使用上述定义的缓存接口中的方法,而不会使用到 LinkedHashMap 的方法。

上述这种实现很简单,完全依靠 LinkedHashMap 来维护缓存数据,重点在于内部类 InternalLruLinkedHashMapCache 一定要重写 removeEldestEntry() 方法,当达到容器容量满时,触发 LinkedHashMap 对最久访问数据的移除。

单元测试:

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
import org.woodwhales.guava.lru.LruCache;
import org.woodwhales.guava.lru.LinkedHashMapLruCache;

/**
* @projectName: guava
* @author: woodwhales
* @date: 20.7.4 21:43
* @description: 使用LinkedHashMap实现带LRU的缓存测试
*/
public class LinkedHashMapLruCacheExample {

public static void main(String[] args) {
LruCache<String, Integer> cache = new LinkedHashMapLruCache<>(3);

cache.put("1", 1);
cache.put("2", 2);
cache.put("3", 3);

System.out.println(cache);

cache.put("4", 4);

System.out.println(cache);

// 由于使用了一次 2,因此原本 2 是最老的,现在是 3 是最老的
System.out.println(cache.get("2"));

System.out.println(cache);
}
}

日志输出:

1
2
3
4
{1=1, 2=2, 3=3}
{2=2, 3=3, 4=4}
2
{3=3, 4=4, 2=2}

日志输出结果符合预期。

实现2:利用 LinkedList + HashMap 实现

上面一种实现完全利用 Java 自带的 LinkedHashMap 容器实现,如果不允许使用 LinkedHashMap,则需要自己实现 LinkedHashMap 类似的功能:LinkedList + HashMap

使用 LinkedList 维护着缓存中元素的 key,保证key的顺序就可以真正的数据存放在 HashMap 中。

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
import com.google.common.base.Preconditions;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.stream.Collectors;

/**
* @projectName: guava
* @author: woodwhales
* @date: 20.7.4 21:59
* @description: 使用LinkedList+HashMap实现带LRU的缓存
*/
public class LinkedListLruCache<K, V> implements LruCache<K, V> {

private final int limit;

private final LinkedList<K> keys;

private final HashMap<K, V> cache;

public LinkedListLruCache(int limit) {
Preconditions.checkArgument(limit > 0, "the limit big than zero.");
this.limit = limit;
this.keys = new LinkedList<K> ();
this.cache = new HashMap<>(limit);
}

@Override
public void put(K key, V value) {
Preconditions.checkNotNull(key, "this key must nut null");
Preconditions.checkNotNull(value, "this value must nut null");
if(cache.size() >= limit) {
K firstKey = keys.getFirst();
keys.remove(firstKey);
cache.remove(firstKey);
}

keys.addLast(key);
cache.put(key, value);
}

@Override
public V get(K key) {

boolean exist = keys.remove(key);
if(!exist) {
return null;
}

keys.addLast(key);
return cache.get(key);
}

@Override
public void remove(K key) {
boolean exist = keys.remove(key);
if(exist) {
cache.remove(key);
}
}

@Override
public void clear() {
keys.clear();
cache.clear();
}

@Override
public int size() {
return keys.size();
}

@Override
public int limit() {
return this.limit;
}

@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("{");
builder.append(keys.stream().map(key -> key + "=" + cache.get(key)).collect(Collectors.joining(",")));
builder.append("}");
return builder.toString();
}
}

单元测试:

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
import org.woodwhales.guava.lru.LinkedListLruCache;
import org.woodwhales.guava.lru.LruCache;

/**
* @projectName: guava
* @author: woodwhales
* @date: 20.7.4 21:43
* @description: 使用LinkedList+HashMap实现带LRU的缓存测试
*/
public class LinkedListLruCacheExample {

public static void main(String[] args) {
LruCache<String, Integer> cache = new LinkedListLruCache<>(3);

cache.put("1", 1);
cache.put("2", 2);
cache.put("3", 3);

System.out.println(cache);

cache.put("4", 4);

System.out.println(cache);

// 由于使用了一次 2,因此原本 2 是最老的,现在是 3 是最老的
System.out.println(cache.get("2"));

System.out.println(cache);
}
}

日志输出:

1
2
3
4
{1=1,2=2,3=3}
{2=2,3=3,4=4}
2
{3=3,4=4,2=2}

实现3:软引用缓存(增强版缓存)

上述两种实现的容器,缓存中的对象都是强引用,可能会存在一种极端情况:当开发者在内存中使用了大量的缓存,而这些缓存中的内容一旦“满员”,那么这个缓存容器就会维护着大量的强引用对象,这些对象会一直得不到垃圾回收。从而导致堆内存溢出(OOM)。

Java 中的引用有四种:强引用、软引用、弱引用、幻影(虚)引用。

软引用会在内存快要 OOM 的时候被 GC 回收。因此我们可以利用这个特性,对缓存中的数据做软引用,而不是使用强引用。

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
import com.google.common.base.Preconditions;

import java.lang.ref.SoftReference;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Objects;

/**
* @projectName: guava
* @author: woodwhales
* @date: 20.7.5 00:45
* @description: 使用软引用对缓存进行增强
*/
public class LinkedHashMapSoftReferencesLruCache<K, V> implements LruCache<K, V> {

private final int limit;

private final InternalLruLinkedHashMapCache<K, V> cache;

private class InternalLruLinkedHashMapCache<K, V> extends LinkedHashMap<K, SoftReference<V>> {
private int limit;

public InternalLruLinkedHashMapCache(int limit) {
super(limit, 0.75f, true);
this.limit = limit;
}

@Override
protected boolean removeEldestEntry(Map.Entry<K, SoftReference<V>> eldest) {
return this.size() > this.limit;
}
}

public LinkedHashMapSoftReferencesLruCache(int limit) {
Preconditions.checkArgument(limit > 0, "this limit must big than zero.");
this.limit = limit;
this.cache = new InternalLruLinkedHashMapCache<>(limit);
}

@Override
public void put(K key, V value) {
this.cache.put(key, new SoftReference<>(value));
}

@Override
public V get(K key) {
SoftReference<V> softReference = this.cache.get(key);
if(Objects.isNull(softReference)) {
return null;
}
return softReference.get();
}

@Override
public void remove(K key) {
this.cache.remove(key);
}

@Override
public void clear() {
this.cache.clear();
}

@Override
public int size() {
return this.cache.size();
}

@Override
public int limit() {
return this.limit;
}
}

上述实现是在实现1的基础上做了一点点变动,即 LinkedHashMap 中存储的数据对象是 SoftReference

单元测试:

测试时,注意设置JVM参数:-Xms128m -Xmx128m -XX:+PrintGCDetails

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
import org.woodwhales.guava.lru.LinkedHashMapLruCache;
import org.woodwhales.guava.lru.LinkedHashMapSoftReferencesLruCache;
import org.woodwhales.guava.lru.LruCache;

import java.util.concurrent.TimeUnit;

/**
* @projectName: guava
* @author: woodwhales
* @date: 20.7.5 00:58
* @description: 使用软引用对缓存进行增强测试
* 测试时,注意设置JVM参数:-Xms128m -Xmx128m -XX:+PrintGCDetails
*/
public class LinkedHashMapSoftReferencesLruCacheTest {

public static void main(String[] args) throws Exception {
testSoftReferencesCache();
//testStrongReferenceCache();
}

/**
* 当使用了带软引用的缓存的时候,相比强引用缓存,在不频繁写入缓存情况下,很难出现OOM
* @throws Exception
*/
private static void testSoftReferencesCache() throws Exception {
LruCache<String, byte[]> cache = new LinkedHashMapSoftReferencesLruCache(100);

for (int i = 1; i <= 100; i++) {
cache.put(String.valueOf(i), new byte[1024 * 1024 * 2]);
System.out.println("i = " + i + " was cached");
TimeUnit.MILLISECONDS.sleep(500);
}
}

/**
* 设置了最大堆内存是 128M
* 每次创建对象并缓存,则增加 2M 内存,因此在大约缓存第60次的时候,就会出现OOM
* @throws Exception
*/
private static void testStrongReferenceCache() throws Exception {
LruCache<String, byte[]> cache = new LinkedHashMapLruCache<>(100);

for (int i = 1; i <= 100; i++) {
cache.put(String.valueOf(i), new byte[1024 * 1024 * 2]);
System.out.println("i = " + i + " was cached");
TimeUnit.MILLISECONDS.sleep(500);
}
}
}

上述单元测试中,由于设置了堆内存最大上限,因此在使用强引用的缓存时,堆内存会被缓存不断地占满,最终导致堆内存全部被占满,即每 500 毫秒创建 2MB 的内存在堆中,堆的最大容量是 128 MB,因此当循环到达 60 次左右的会出现 OOM。而软引用缓存中,当堆内存不够的时候,创建新的对象到堆的频率不够快,GC 来得及回收掉部分软引用对象,那么循环会一直进行下去,不会出现 OOM。

updated updated 2020-07-05 2020-07-05
本文结束感谢阅读

本文标题:LRU算法的Java实现(两种实现+增强实现)

本文作者:木鲸鱼

微信公号:木鲸鱼 | woodwhales

原始链接:https://woodwhales.cn/2020/07/05/070/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%