lru算法设计与实现

本文最后更新于：2022年5月10日 上午

摘要：主要介绍了LRU（Least Recently Used，最近最少使用）算法是什么、设计思路、基于Java语言的具体实现。

前言

LRU（Least Recently Used，最近最少使用），是一种缓存数据淘汰策略。由于缓存有容量上限，当缓存写满后，有新的数据要放入缓存，则需要按照一定的策略淘汰掉缓存中原有的数据，这个策略就叫做缓存淘汰策略。常见的缓存淘汰策略有：FIFO（First Input First Output）、LRU、LFU（Least Frequently Used）等。

LRU的思想认为，最近被访问过的数据，在将来被访问的几率最大。

LRU算法设计

LRU缓存要求

  1. 以正整数作为容量 capacity 初始化 LRU 缓存。
  2. 查找操作：如果关键字 key 存在于缓存中，则返回关键字的值，否则返回null 。
  3. 插入操作：如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
  4. 插入操作和查找操作的平均时间复杂度为O(1)。

LRU算法设计

  1. 由于LRU缓存有容量限制，在put操作的时候需要先查看缓存是否已满，因此在初始化缓存时需要指定capacity和size分别记录缓存的容量和已经存放元素个数。
  2. 为了保证查找操作的平均时间复杂度为O(1)，可以使用HashMap来存放。
  3. 如果仅使用HashMap，淘汰元素时，就没法保证O(1)的时间复杂度。考虑到双向链表的队首和队尾的插入和删除操作都是O(1)的，因此本文选择使用HashMap配合双向链表来实现LRU缓存结构。

LRU算法实现——Java语言

主要成员变量和方法

  1. 首先定义一个Cache接口，在该接口中定义主要的方法。
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
package com.shg.algorithm.lru;

/**
 * @author: shg
 * @create: 2022-05-09 5:53 下午
 */
public interface Cache<K, V> {

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

    /**
     * 向缓存中添加数据
     *
     * @param key
     * @param value
     */
    void put(K key, V value);

    /**
     * 返回缓存中存放元素个数
     *
     * @return
     */
    int size();

    /**
     * 缓存是否为空
     *
     * @return
     */
    boolean isEmpty();

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

}

  1. 定义一个基于LRU算法的Cache接口的实现类LRUCache，在该类中实现具体方法，以及主要的成员变量。
  • 由于LRUCache需要维护一个双端队列，因此定义一个Entry封装放入缓存中的数据，作为链表的节点
  • 定义head和tail分别作为链表的头节点和尾节点，head是哑节点，不保存任何数据，其key和value始终为null
  • 定义一个HashMap类型的cache，用于存放数据，其中key为数据的关键字，而value是链表的节点
  • capacity和size分别表示缓存的容量和放入数据的数量
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
package com.shg.algorithm.lru;

import java.util.HashMap;

/**
 * @author: shg
 * @create: 2022-05-09 5:57 下午
 */
public class LRUCache<K, V> implements Cache<K, V> {

    /**
     * 缓存容量
     */
    private int capacity;

    /**
     * 缓存中已经存放元素数量
     */
    private int size;

    /**
     * head，双向链表的头节点
     * tail，双向链表的尾节点
     */
    private Entry head, tail;

    /**
     * 用来存放关键字k和关键字所对应的节点entry
     */
    private HashMap<K, Entry> cache;

    /**
     * 需要指定缓存容量的构造方法
     * @param capacity
     */
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    @Override
    public V get(K key) {
        return null;
    }

    @Override
    public void put(K key, V value) {

    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public void clear() {

    }

    /**
     * 内部类，用于将放入缓存中的数据k、v封装城双向链表的节点
     *
     * @param <K>
     * @param <V>
     */
    class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> pre;
        Entry<K, V> next;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

}

具体方法实现详解

  1. 构造方法
  • 初始容量应为正整数，否则抛出非法的参数异常
  • 本类中的哈希表采用懒初始化，因此在构造方法中并没有初始化哈希表
1
2
3
4
5
6
7
8
9
10
/**
 * 需要指定缓存容量的构造方法
 * @param capacity
 */
public LRUCache(int capacity) {
    if (capacity <= 0) 
        throw new IllegalArgumentException("capacity不能小于1，capacity：" + capacity);
    this.capacity = capacity;
    this.size = 0;
}
  1. get(K): V 操作
  • 首先判断cache是否为null，如果cache为null，则缓存中没有数据，直接返回null
  • 如果cache不为null，则根据key从cache中对应的entry
  • 判断entry是否为null，如果为null，则关键字key对应的数据不存在，返回null
  • 如果entry不为null，则判断该节点是否在队尾，如果不在队尾，则将该节点移到队尾
    • 将entry节点的前驱节点的后继节点指向entry节点的后继节点
    • 将entry节点的后继节点的前驱节点指向entry节点的前驱节点
    • 将entry节点的前驱节点指向队尾
    • 将队尾的后继节点执行entry
    • 将entry节点的后继节点置空
    • 将tail指向entry，完成将entry移到队尾操纵
  • 最后返回数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
@Override
public V get(K key) {
    // 如果cache为null，则缓存中没有数据，直接返回null
    if (cache == null) return null;
    // 否则，从cache中获取数据
    Entry<K, V> entry = cache.get(key);

    // 判断entry是否为空，如果为空，则关键字key对应的数据不存在，返回null
    if (entry == null) return null;
    // 否则判断该节点是否在队尾，如果不在队尾，则将该节点移到队尾
    if (entry != tail) {
        entry.pre.next = entry.next;
        entry.next.pre = entry.pre;
        entry.pre = tail;
        tail.next = entry;
        entry.next = null;
        tail = entry;
    }
    // 返回entry中的value值
    return entry.value;
}
  1. put(K, V): void
  • 首先校验插入的数据是否为null，为null则直接抛出异常
  • 判断cache是否初始化，如果没有初始化，则进行初始化
  • 判断是否需要先进行淘汰：如果缓存已满且要插入的key不在缓存中，需要先进行淘汰
    • 淘汰数据：
    • 将队首元素移出队列：队首元素是head.next，而不是head，head是不保存数据的哑节点
    • 从cache中删除数据
    • 移出队首元素后，队列已存入的元素数量要减1
  • 插入数据：这里还要考虑到数据是否已经存在于缓存中
    • 如果不存在需要先根据key和value封装entry插入到队列队尾，并加入到cache中
    • 如果存在，则需要更新value，并将对应的entry移动到队尾
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
@Override
public void put(K key, V value) {
    // 校验数据，如果为null则抛出异常
    if (key == null || value == null)
        throw new IllegalArgumentException("key-value不能为null");
    // 判断cache是否初始化，如果没有初始化，则进行初始化
    if (cache == null)
        initialCache();
    // 判断是否需要先进行淘汰：如果缓存已满且要插入的key不在缓存中，需要先进行淘汰
    if (size == capacity && !cache.containsKey(key)) {
        // 淘汰数据
        // 1. 将队首元素移出队列：队首元素是head.next，而不是head，head是不保存数据的哑节点
        // 2. 从cache中删除数据
        head = head.next;
        if (head != null) {
            cache.remove(head.key);
            head.key = null;
            head.value = null;
            head.pre = null;
        }
        // 移出队首元素后，队列已存入的元素数量要减1
        size--;
    }
    // 插入数据：这里还要考虑到数据是否已经存在于缓存中
    // 如果不存在需要先根据key和value封装entry插入到队列中，并加入到cache中
    // 如果存在，则需要更新value，并将对应的entry移动到队尾
    for (Entry<K, V> entry = cache.get(key);; ) {
        if (entry == null) {
            // 封装entry，并加入到cache中
            entry = new Entry<>(key, value);
            cache.put(key, entry);
        } else {
            if (entry.pre == null) { // 新创建的entry，直接加入到队尾
                tail.next = entry;
                entry.pre = tail;
                // tail = entry; // 这一步由于不管是新加入entry还是更新entry都有，因此可以提取出来
                size++;
            } else { // 更新entry
                entry.value = value;
                if (entry != tail) { // 如果entry不在队尾，则移到队尾
                    entry.pre.next = entry.next;
                    entry.next.pre = entry.pre;
                    entry.pre = tail;
                    tail.next = entry;
                    entry.next = null;
                    // tail = entry; // 这一步由于不管是新加入entry还是更新entry都有，因此可以提取出来
                }
            }
            tail = entry;
            return;
        }
    }
}
/**
 * 初始化cache、head、tail
 */
private void initialCache() {
    // 初始化cache，直接指定cache大小，防止以后扩容影响性能
    cache = new HashMap<>(capacity);
    // 初始化队列，head作为哑节点，不保存数据
    head = new Entry(null, null);
    tail = head;
}
  1. clear(): void
1
2
3
4
5
6
7
8
9
10
@Override
public void clear() {
    // 清空cache
    cache.clear();
    // 清空队列
    head = null;
    tail = null;
    // 缓存中数据的数量置为0
    size = 0;
}
  1. size(): int
1
2
3
4
@Override
public int size() {
    return size;
}
  1. isEmpty(): boolean
1
2
3
4
@Override
public boolean isEmpty() {
    return size == 0;
}

完整代码

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
package com.shg.algorithm.lru;

import java.util.HashMap;

/**
 * @author: shg
 * @create: 2022-05-09 5:57 下午
 */
public class LRUCache<K, V> implements Cache<K, V> {

    /**
     * 缓存容量
     */
    private int capacity;

    /**
     * 缓存中已经存放元素数量
     */
    private int size;

    /**
     * head，双向链表的头节点
     * tail，双向链表的尾节点
     */
    private Entry head, tail;

    /**
     * 用来存放关键字k和关键字所对应的节点entry
     */
    private HashMap<K, Entry> cache;

    /**
     * 需要指定缓存容量的构造方法
     *
     * @param capacity
     */
    public LRUCache(int capacity) {
        if (capacity <= 0)
            throw new IllegalArgumentException("capacity不能小于1，capacity：" + capacity);
        this.capacity = capacity;
        this.size = 0;
    }

    @Override
    public V get(K key) {
        // 如果cache为null，则缓存中没有数据，直接返回null
        if (cache == null) return null;
        // 否则，从cache中获取数据
        Entry<K, V> entry = cache.get(key);

        // 判断entry是否为空，如果为空，则关键字key对应的数据不存在，返回null
        if (entry == null) return null;
        // 否则判断该节点是否在队尾，如果不在队尾，则将该节点移到队尾
        if (entry != tail) {
            entry.pre.next = entry.next;
            entry.next.pre = entry.pre;
            entry.pre = tail;
            tail.next = entry;
            entry.next = null;
            tail = entry;
        }
        // 返回entry中的value值
        return entry.value;
    }

    @Override
    public void put(K key, V value) {
        // 校验数据，如果为null则抛出异常
        if (key == null || value == null)
            throw new IllegalArgumentException("key-value不能为null");
        // 判断cache是否初始化，如果没有初始化，则进行初始化
        if (cache == null)
            initialCache();
        // 判断是否需要先进行淘汰：如果缓存已满且要插入的key不在缓存中，需要先进行淘汰
        if (size == capacity && !cache.containsKey(key)) {
            // 淘汰数据
            // 1. 将队首元素移出队列：队首元素是head.next，而不是head，head是不保存数据的哑节点
            // 2. 从cache中删除数据
            head = head.next;
            if (head != null) {
                cache.remove(head.key);
                head.key = null;
                head.value = null;
                head.pre = null;
            }
            // 移出队首元素后，队列已存入的元素数量要减1
            size--;
        }
        // 插入数据：这里还要考虑到数据是否已经存在于缓存中
        // 如果不存在需要先根据key和value封装entry插入到队列中，并加入到cache中
        // 如果存在，则需要更新value，并将对应的entry移动到队尾
        for (Entry<K, V> entry = cache.get(key);; ) {
            if (entry == null) {
                // 封装entry，并加入到cache中
                entry = new Entry<>(key, value);
                cache.put(key, entry);
            } else {
                if (entry.pre == null) { // 新创建的entry，直接加入到队尾
                    tail.next = entry;
                    entry.pre = tail;
                    // tail = entry; // 这一步由于不管是新加入entry还是更新entry都有，因此可以提取出来
                    size++;
                } else { // 更新entry
                    entry.value = value;
                    if (entry != tail) { // 如果entry不在队尾，则移到队尾
                        entry.pre.next = entry.next;
                        entry.next.pre = entry.pre;
                        entry.pre = tail;
                        tail.next = entry;
                        entry.next = null;
                        // tail = entry; // 这一步由于不管是新加入entry还是更新entry都有，因此可以提取出来
                    }
                }
                tail = entry;
                return;
            }
        }
    }

    /**
     * 初始化cache、head、tail
     */
    private void initialCache() {
        // 初始化cache，直接指定cache大小，防止以后扩容影响性能
        cache = new HashMap<>(capacity);
        // 初始化队列，head作为哑节点，不保存数据
        head = new Entry(null, null);
        tail = head;
    }

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

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        // 清空cache
        cache.clear();
        // 清空队列
        head = null;
        tail = null;
        // 缓存中数据的数量置为0
        size = 0;
    }

    /**
     * 内部类，用于将放入缓存中的数据k、v封装城双向链表的节点
     *
     * @param <K>
     * @param <V>
     */
    class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> pre;
        Entry<K, V> next;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

}

小结

主要特点

  1. 并没有使用JDK内置的双端队列，而是通过内部类Entry来维护一个双端队列
  2. 内部维护了一个不保存任何数据的哑节点即head，这便于插入和移出节点操作
算法
#Java #算法
lru算法设计与实现
https://shgang97.github.io/posts/lrucache-a352b759247b/
作者
shgang
发布于
2022年5月9日
更新于
2022年5月10日
许可协议