LRU算法的Java实现（两种实现+增强实现）

发表于 | 分类 |
| 全文总计: 字
缓存基础，LRU算法

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 2024-01-01 2024-01-01
本文结束感谢阅读

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

本文作者:woodwhales

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

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

0%