LRU和LFU简介与代码演练

简介

LRU（Least Recently Used）和LFU（Least Frequently Used）是两种常见的缓存替换算法。

LRU是基于最近使用时间的缓存替换算法。它的基本思想是，当缓存空间不足时，优先淘汰最长时间未被访问的数据。LRU算法维护一个访问顺序链表（或双向链表），每次访问一个数据时，将其移动到链表的头部。当需要淘汰数据时，选择链表尾部的数据进行删除。

LFU则是基于访问频率的缓存替换算法。它的核心思想是，当缓存空间不足时，优先淘汰访问频率最低的数据。LFU算法维护一个频率计数器，用于记录每个数据被访问的次数。每次访问一个数据时，将对应数据的访问次数加1。当需要淘汰数据时，选择访问次数最低的数据进行删除。

LRU和LFU都是为了在有限的缓存空间中提供尽可能高的缓存命中率。LRU更注重保留最近被访问的数据，而LFU更注重保留访问频率较高的数据。

在实际应用中，可以根据具体的场景选择合适的缓存替换算法。LRU算法适用于访问模式具有时间局部性的场景，而LFU算法适用于访问模式具有频率局部性的场景。有些系统还会结合两种算法，根据实际情况动态选择使用哪种算法。

当我们看这个代码的时候，首先需要理解两个缓存算法的概念：LRU（最近最少使用）和LFU（最不经常使用）。

实现逻辑

• LRU缓存算法逻辑：

LRU缓存算法基本思想是保留最近被访问过的数据项，当容量超过预设阈值时，将最久未被访问的数据项从缓存中移除。

在代码中，我们使用LinkedHashMap作为LRU缓存的数据结构。LinkedHashMap是一个有序的HashMap，通过重写removeEldestEntry方法来控制是否移除最老的数据项。具体逻辑如下：

在构造函数中，我们初始化一个LinkedHashMap作为缓存，并重写了removeEldestEntry方法，使其在缓存大小超过capacity时返回true，表示需要移除最老的数据项。

get方法用于从缓存中获取数据。如果数据项存在于缓存中，则将其移动到链表的尾部（表示最近访问过），然后返回数据项的值；否则，返回null。

put方法用于向缓存中插入数据。如果数据项已存在，则更新数据值，并将其移动到链表尾部。如果数据项不存在，我们检查缓存是否已满，如果满了，则移除链表头部的数据项（最久未被访问的数据项），然后插入新数据项到链表尾部。

• LFU缓存算法逻辑：

LFU缓存算法基本思想是保留访问频率最高的数据项，当容量超过预设阈值时，将访问频率最低的数据项从缓存中移除。

在代码中，我们使用一个自定义的LFUCache类来实现LFU缓存。具体逻辑如下：

在构造函数中，我们初始化一个HashMap作为缓存，并设定缓存容量。

get方法用于从缓存中获取数据。如果数据项存在于缓存中，则将其访问频率增加，并通过updateNode方法将其在链表中按照访问频率调整位置，然后返回数据项的值；否则，返回null。

put方法用于向缓存中插入数据。如果数据项已存在，则更新数据值，并将其访问频率增加，并通过updateNode方法将其在链表中按照访问频率调整位置。如果数据项不存在，我们检查缓存是否已满，如果满了，则移除链表头部的数据项（访问频率最低的数据项），然后插入新数据项到链表尾部，并设定访问频率为1。

updateNode 这段代码是用于在LFU缓存算法中更新节点位置的逻辑。它会在以下情况下执行：

1. 当要更新的节点的下一个节点不为空，并且当前节点的频率大于或等于下一个节点的频率时，会进入循环while (curr.next != null && curr.frequency >= curr.next.frequency)。这意味着当前节点的频率与下一个节点的频率相同或更高。
2. 如果在循环内，发现当前节点curr不等于要更新的节点node，则表示需要将节点node移动到当前节点curr的位置。

在LFU缓存算法中，当访问频率增加时，我们需要将节点移动到适当的位置，以保持链表中节点按照访问频率从低到高的顺序排列。这段代码就是负责处理这个移动的逻辑。

例如，假设链表中有以下节点（按照频率从低到高的顺序）：A -> B -> C -> D。

• 当访问节点B时，B的频率增加，变为了2。此时，循环将curr从B移动到C。
• 如果访问节点C，C的频率增加，变为了3。由于C的频率大于D（频率为2），所以循环将curr从C移动到D的位置，链表变为A -> B -> D -> C。

在LFUCache类中，updateNode方法会在get和put操作中调用，用于调整节点的位置。通过这个逻辑，我们可以确保链表中节点按照频率从低到高的顺序排列。

package com.javayh.mv.common.util;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.Map;

/**
 * <p>
 *
 * </p>
 *
 * @author hai ji
 * @version 1.0.0
 * @since 2023-07-05
 */
class LRUCache<K, V> {
    private int capacity;
    private LinkedHashMap<K, V> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > capacity;
            }
        };
    }

    public V get(K key) {
        return cache.getOrDefault(key, null);
    }

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

class LFUCache<K, V> {
    private int capacity;
    private Map<K, Node<K, V>> cache;
    private Node<K, V> head;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>(capacity);
    }

    public V get(K key) {
        Node<K, V> node = cache.get(key);
        if (node != null) {
            node.frequency++;
            updateNode(node);
            return node.value;
        }
        return null;
    }

    public void put(K key, V value) {
        if (capacity == 0) {
            return;
        }

        Node<K, V> node = cache.get(key);
        if (node != null) {
            node.value = value;
            node.frequency++;
            updateNode(node);
        } else {
            if (cache.size() >= capacity) {
                K evictKey = head.keys.iterator().next();
                head.keys.remove(evictKey);
                cache.remove(evictKey);
            }

            Node<K, V> newNode = new Node<>(key, value);
            newNode.frequency = 1;
            cache.put(key, newNode);
            if (head == null || head.frequency > 1) {
                Node<K, V> newHead = new Node<>(null, null);
                newHead.next = head;
                if (head != null) {
                    head.prev = newHead;
                }
                head = newHead;
            }
            head.keys.add(key);
        }
    }

    /*
     * 这段代码是用于在LFU缓存算法中更新节点位置的逻辑。它会在以下情况下执行：
     *
     * 当要更新的节点的下一个节点不为空，并且当前节点的频率大于或等于下一个节点的频率时，会进入循环while (curr.next != null && curr.frequency >= curr.next.frequency)。这意味着当前节点的频率与下一个节点的频率相同或更高。
     *
     * 如果在循环内，发现当前节点curr不等于要更新的节点node，则表示需要将节点node移动到当前节点curr的位置。
     *
     * 在LFU缓存算法中，当访问频率增加时，我们需要将节点移动到适当的位置，以保持链表中节点按照访问频率从低到高的顺序排列。这段代码就是负责处理这个移动的逻辑。
     *
     * 例如，假设链表中有以下节点（按照频率从低到高的顺序）：A -> B -> C -> D。
     *
     * 当访问节点B时，B的频率增加，变为了2。此时，循环将curr从B移动到C。
     *
     * 如果访问节点C，C的频率增加，变为了3。由于C的频率大于D（频率为2），所以循环将curr从C移动到D的位置，链表变为A -> B -> D -> C。
     *
     * 在LFUCache类中，updateNode方法会在get和put操作中调用，用于调整节点的位置。通过这个逻辑，我们可以确保链表中节点按照频率从低到高的顺序排列。
     */
    private void updateNode(Node<K, V> node) {
        Node<K, V> curr = node;
        while (curr.next != null && curr.frequency >= curr.next.frequency) {
            curr = curr.next;
        }

        if (curr != node) {
            curr.prev.next = node;
            node.prev = curr.prev;

            if (node.next != null) {
                node.next.prev = curr;
            }
            curr.next = node.next;
            node.next = curr;
            curr.prev = node;
        }

        LinkedHashSet<K> keys = node.keys;
        if (!keys.isEmpty()) {
            K key = keys.iterator().next();
            keys.remove(key);
            keys.add(key);
        }
    }

    private static class Node<K, V> {
        private K key;
        private V value;
        private int frequency;
        //节点的prev指向频率较低的节点，next指向频率较高的节点。当访问某个数据项时，我们通过更新节点的频率和调整节点在链表中的位置来实现LFU缓存算法的逻辑。
        private Node<K, V> prev;
        private Node<K, V> next;
        private LinkedHashSet<K> keys;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.frequency = 0;
            this.prev = null;
            this.next = null;
            this.keys = new LinkedHashSet<>();
        }
    }
}

public class Test {
    public static void main(String[] args) {
        // LRU Cache example  长时间为访问
        LRUCache<Integer, String> lruCache = new LRUCache<>(3);
        lruCache.put(1, "One");
        lruCache.put(2, "Two");
        lruCache.put(3, "Three");
        System.out.println(lruCache.get(2)); // Output: Two
        lruCache.put(4, "Four");
        System.out.println(lruCache.get(1)); // Output: null (evicted)
        System.out.println(lruCache.get(4)); // Output: Four

        // LFU Cache example 访问频次最低的
        LFUCache<Integer, String> lfuCache = new LFUCache<>(3);
        lfuCache.put(1, "One");
        lfuCache.put(2, "Two");
        lfuCache.put(3, "Three");
        System.out.println(lfuCache.get(2)); // Output: Two
        System.out.println(lfuCache.get(2)); // Output: Two
        lfuCache.put(4, "Four");
        System.out.println(lfuCache.get(2)); // Output: Two
        System.out.println(lfuCache.get(1)); // Output: null (evicted)
        System.out.println(lfuCache.get(4)); // Output: Four
    }
}

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
172
173
174
175
176
177
178
179
180