经典的 LRU 算法，你真的了解吗？

发表于 | 分类于

人生有涯，学海无涯。

《Java 极客技术》公众号已经有很多优质的原创文章了，但是纵观公号的历史文章总感觉少了点啥，那就是算法相关的内容。算法可以说是编程人员不可避免的一个难题，而且算法也是一个非常难的课题，很多人一提到数据结构与算法都会瑟瑟发抖。学算法是一个持久战，后续我们会慢慢增加算法相关的文章，尽量的为大家提供一些帮助，今天让我们来看一个经典的算法 LRU(最近最少使用)算法。

LRU 简介

Least Recently Used的缩写，即最近最少使用，可以用来作为路由或者淘汰算法。很多开源的框架或者一些第三方的项目都会采用到这个算法，比如 Redis 的 key 的缓存失效，比如一些路由功能。

算法的思想是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。正是由于这个特性，所以我们可以将使用不到的数据淘汰，或者如果是路由，我们就可以将数据路由到这台机器，实现负载。

这里我们以淘汰数据为例，提供两种实现方式。

算法实现

基于链表的 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
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
90
91
92
93
94
95
96
97
98
99
100
101
package com.silence.arts.leetcode;

import java.util.LinkedList;

/**
 * <br>
 * <b>Function：</b><br>
 * <b>Author：</b>@author ziyou<br>
 * <b>Date：</b>2019-07-30 23:27<br>
 * <b>Desc：</b>无<br>
 */
public class LruCacheDemo {

    /**
     * 定义链表的大小
     */
    private int capacity;
    /**
     * 初始化链表
     */
    private LinkedList<User> cacheList = new LinkedList<>();

    public LruCacheDemo(int capacity) {
        this.capacity = capacity;
    }


    /**
     * 根据名称获取数据，如果名称相同则返回用户实体，并且将该用户移动到链表头部
     *
     * @param username 名称
     * @return 用户
     */
    public User get(String username) {
        User u = null;
        for (User user : cacheList) {
            if (user.getUsername().equals(username)) {
                cacheList.remove(user);
                cacheList.add(0, user);
                u = user;
            }
        }
        return u;
    }

    public void put(User user) {
        //判断链表长度是否达到最大
        if (cacheList.size() == capacity) {
            cacheList.remove(capacity - 1);
        }
        cacheList.add(0, user);
    }


    public static void main(String[] args) {
        LruCacheDemo cacheDemo = new LruCacheDemo(5);
        User user1 = new User("a1", 1);
        cacheDemo.put(user1);
        User user2 = new User("a2", 2);
        cacheDemo.put(user2);
        System.out.println(cacheDemo.get("a1"));
        User user3 = new User("a3", 3);
        cacheDemo.put(user3);
        User user4 = new User("a4", 4);
        cacheDemo.put(user4);
        System.out.println(cacheDemo.get("a4"));
        System.out.println(cacheDemo.get("a2"));
        User user5 = new User("a5", 5);
        cacheDemo.put(user5);
        User user6 = new User("a6", 6);
        cacheDemo.put(user6);
        System.out.println(cacheDemo.get("a1"));
    }


    static class User {
        public User(String username, int age) {
            this.username = username;
            this.age = age;
        }

        private String username;
        private int age;

        public String getUsername() {
            return username;
        }

        public void setUsername(String username) {
            this.username = username;
        }

        public int getAge() {
            return age;
        }

        public void setAge(int age) {
            this.age = age;
        }
    }
}

基于 HashMap 和 Linkedlist 的 LRU 实现

这种实现方式其他跟上面的实现方式类似，区别的地方是在这种方式采用的是 JDK 封装好的，给大家参考如下

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
package com.silence.arts.leetcode;

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * <br>
 * <b>Function：</b><br>
 * <b>Author：</b>@author ziyou<br>
 * <b>Date：</b>2019-07-30 23:35<br>
 * <b>Desc：</b>无<br>
 */
public class LRULinkedMap<K, V> {
    /**
     * 最大缓存大小
     */
    private int cacheSize;
    private LinkedHashMap<K, V> cacheMap;

    public LRULinkedMap(int cacheSize) {
        this.cacheSize = cacheSize;
        cacheMap = new LinkedHashMap(16, 0.75F, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                if (cacheSize + 1 == cacheMap.size()) {
                    return true;
                } else {
                    return false;
                }
            }
        };
    }

    public void put(K key, V value) {
        cacheMap.put(key, value);
    }

    public V get(K key) {
        return cacheMap.get(key);
    }

}

总结

今天给大家介绍了一下 LRU 算法的两种实现，还有很多变种的实现方式大家可以自行的搜索学习。

我们只要记住 LRU 的核心思想：新增和最近被访问的数据需要移到到链表前，淘汰的是链表最后的一个数据。

在算法的道路上还有很多路要走，大家一起加油。

Java Geek Tech wechat
欢迎订阅 Java 极客技术，这里分享关于 Java 的一切。