文章翻新 250913

  • 补充 Java 相关数据结构 LinkedList、LinkedHashMap、PriorityQueue 信息
  • 补充 OPT、LFU 算法题与解析

文章最初发表于 240903，原标题：手写 LRU 缓存以理解 Java 中的 LinkedHashMap，原封面。

在操作系统的学习过程中，我们会在不同的内容中（页面置换算法、高速缓冲器替换算法）接触到各种缓存置换算法：

算法 名称 说明
OPT 最佳置换算法 此算法在已知未来所有访问记录的前提下，每次都替换未来不再被访问/最远被访问的现存数据。该算法是理论上的最优算法。
FIFO 先进先出置换算法 每次替换最先进入缓存的数据，该算法认为最先进入的数据在将来被访问到的可能性最小。FIFO 算法存在 Belady 现象。
LRU 最近最少使用置换算法 每次替换最久未被访问的数据，该算法认为最近一段时间没有被访问到的数据在将来被访问的可能性最小，这种策略在实际中应用较广。
LFU 最少使用置换算法 每次替换访问次数最小的数据，该算法的思想是最近一段时间被访问次数最小的数据在将来被访问的可能性最小。
RAND 随机算法 从现存数据中随机选择一个元素进行替换，该算法不需要维护历史访问记录的任何信息，实现上简单高效，但命中率通常一般。
Belady 现象

Belady 现象是计算机系统中采用先进先出（FIFO）页面置换算法时出现的异常现象，表现为当分配给进程的物理页面数增加时，缺页率不降反升。贝拉迪通过实验发现，当操作系统未满足进程全部页面需求时，FIFO 算法可能因过早置换仍将被频繁访问的页面，引发更多缺页中断。这一发现打破了 「增加内存必然降低缺页率」的传统认知。

缓存替换算法用于管理有限的缓存空间，决定哪些数据需要被移除以腾出空间。现在编程题也喜欢考察对于这些算法的实现能力。

本文结合真实题目，讲解用 Java 语言实现 OPT、LRU、LFU 算法，并了解相关的 Java 数据结构。至于 FIFO、RAND 很简单，读者可自行实现。

本文题目难度标识：🟩简单，🟨中等，🟥困难。

Java 中相关的数据结构

LinkedList 双向链表

从 JDK1.7 开始，LinkedList 由双向循环链表改为双向链表。

LinkedList 是一个基于双向链表实现的集合类。

image.png

image.png

一些操作的时间复杂度：

API 操作 时间复杂度 源码做法
add(e)
addFirst(e)
addLast(e)		 头尾插入 O(1)O(1) 双向链表常规做法
add(index,e) 指定位置插入 O(n)O(n) 选择靠近的一端向中间遍历
remove()
removeFirst()
removeLast()		 头尾删除 O(1)O(1) 双向链表常规做法
remove(E e) 指定元素删除（删除首次出现元素） O(n)O(n) 从头到尾遍历链表
remove(index) 指定位置删除 选择靠近的一端向中间遍历
getFirst()
getLast()		 获取头尾元素 O(1)O(1) 双向链表常规做法
get(int index) 获取链表指定位置的元素 O(n)O(n) 选择靠近的一端向中间遍历
clear() 移除此链表中的所有元素 从头到尾遍历链表
contains(e) 查询指定元素是否存于链表
循环使用 remove(int index) 的时间复杂度。

Q：在一个 LinkedList 类型的变量进行 for 循环遍历时，每轮迭代执行一次 remove(index) 操作，请问该循环时间复杂度是多少？

A：O(n2)O(n^2)，因为一次 remove(int index) 就需要 O(n)O(n)。

LinkedHashMap 含双向链表的哈希集合

image.png

LinkedHashMap 是 Java 提供的一个集合类，它继承自 HashMap，并在 HashMap 基础上维护一条双向链表。

image.png

LinkedHashMap 特性：

  • 支持遍历时会按照插入顺序有序进行迭代。（与 HashMap 的最大区别）
  • 支持按照元素访问顺序排序，适用于封装 LRU 缓存工具。
  • 因为内部使用双向链表维护各个节点，所以遍历时的效率和元素个数成正比，相较于和容量成正比的 HashMap 来说，迭代效率会高很多。由于双向链表的存在，其插入性能可能会比 HashMap 略低。

基本特性 LinkedHashMap 迭代顺序和插入顺序一致

它的用法和 HashMap 一致。特点在于 LinkedHashMap 的从头到尾迭代顺序是和插入顺序一致的，而 HashMap 中是随机的。

可在构造函数中开启访问顺序 accessOrder

LinkedHashMap 定义了排序模式 boolean accessOrder = false。当 accessOrder 为 true 时，被访问的元素将重新拿出来放到链表尾部。

设置方式：

1
2
// 初始容量、负载因子、访问顺序
LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);

重写 removeEldestEntry 方法

removeEldestEntry 将返回一个 boolean 值，告知 LinkedHashMap 是否需要移除链表首元素。我们需要在继承 LinkedHashMap 的子类中重写该方法：

1
2
3
4
5
6
7
8
9
10
11
public class MyMap<K, V> extends LinkedHashMap<K, V> {

    public MyMap(int capacity) {
        super(capacity, 0.75f, true);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return /* 编写判断逻辑 */;
    }
}

PriorityQueue 优先队列（二项堆）

优先队列基于二项堆，用法详见：站内文章Java 集合的使用。

最佳置换算法 OPT

缓存替换的最优算法（MIN/OPT，Optimal）在 1966 年由 Laszlo A.Belady 提出，此算法在已知未来所有访问记录的前提下，每次都替换未来不再被访问/最远被访问的现存数据。该算法是理论上的最优算法，因为需要已知未来所有访问记录，并不具备可实现性，通常用于衡量其它缓存替换算法的优劣。

🟨 P4404 [JSOI2010] 缓存交换 - 洛谷

在计算机中，CPU 只能和高速缓存 Cache 直接交换数据。当所需的内存单元不在 Cache 中时，则需要从主存里把数据调入 Cache。此时，如果 Cache 容量已满，则必须先从中删除一个。

在现代计算机中，往往采用 LRU(最近最少使用) 的算法来进行 Cache 调度——可是，从上一个例子就能看出，这并不是最优的算法。 对于一个固定容量的空 Cache 和连续的若干主存访问请求，聪聪想知道如何在每次 Cache 缺失时换出正确的主存单元，以达到最少的 Cache 缺失次数。

思路：采用 OPT，即淘汰在之后的访问中，出现最晚（甚至不出现）的元素。

我的解法：

  • 使用到的数据结构有哈希表和优先队列。
  • 哈希表用于快速判断缓存中是否存在指定的 key。
  • 优先队列可快速得出待删元素。
  • 更新键值时，从优先队列中找出相应元素并删除的 remove(obj) 操作可能有一定的时间复杂度。
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
import java.util.Scanner;
import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;
import java.util.PriorityQueue;

public class Main{
    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int[] dataIds = new int[N];
        for(int i=0;i<N;i++){
            dataIds[i]=in.nextInt();
        }

        int ans = f(N,M,dataIds);
        System.out.println(ans);
    }

    public static int f(int n,int capacity,int[] dataIds){
        int[] next = new int[n]; // 表示当前 id 下一次出现的位置
        Arrays.fill(next,Integer.MAX_VALUE);
        Map<Integer,Integer> map = new HashMap<>(); // id->lastIdx
        for(int i=0;i<n;i++){
            if(map.containsKey(dataIds[i])){
                int lastIdx = map.get(dataIds[i]);
                next[lastIdx] = i;
            }
            map.put(dataIds[i],i);
        }
        PriorityQueue<Node> q = new PriorityQueue<>((n1,n2)->{
            return n2.next-n1.next;
        });
        Map<Integer,Node> keyMap = new HashMap<>(); // 为了更快判断缓存中是否存在对应的键
        int miss = 0;
        for(int i=0;i<n;i++){
            if(keyMap.containsKey(dataIds[i])){
                Node node = keyMap.get(dataIds[i]);
                q.remove(node);
                node.next = next[i];
                q.offer(node);
                continue;
            }
            if(q.size()==capacity){
                Node oldNode = q.poll();
                keyMap.remove(oldNode.id);
            }
            Node newNode = new Node(dataIds[i],next[i]);
            q.offer(newNode);
            keyMap.put(dataIds[i],newNode);
            miss++;
        }
        return miss;
    }
}

class Node{
    Integer id;
    int next;
    Node(Integer id,int next){
        this.id= id;
        this.next = next;
    }
}

最近最少使用 LRU

最近最少使用（Least Recently Used，LRU），是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

题目：🟨 146. LRU 缓存 - 力扣（LeetCode）

请你设计并实现一个满足 LRU（最近最少使用）缓存 约束的数据结构。
实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value)
    • 如果关键字 key 已经存在，则变更其数据值 value
    • 如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1)O(1) 的平均时间复杂度运行。

首先介绍直接使用 Java API 的写法。Java 中 LinkedHashMap 的特性使其天然地成为轻松实现 LRU 缓存的数据结构。具体实现思路如下：

  • 继承 LinkedHashMap；
  • 构造方法中指定 accessOrder 为 true ，这样在访问元素时就会把该元素移动到链表尾部，链表首元素就是最近最少被访问的元素；
  • 重写 removeEldestEntry 方法，该方法会返回一个 boolean 值，告知 LinkedHashMap 是否需要移除链表首元素（缓存容量有限）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class LRUCache extends LinkedHashMap<Integer,Integer>{
    int capacity;
    public LRUCache(int capacity) {
		super(capacity,0.75f,true);
		this.capacity = capacity;
    }

	// 由于题目对get返回值要求，这里我们需要进行一些调整，不然我们都可以干脆不写。
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    
    /* 题目中 put 方法直接交给 LinkedHashMap */

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest){
        return size() > capacity;
    }
}

如果面试手撕环节这道题目这样写，估计面试官就会叫你在家等通知了。LinkedHashMap 无外乎就是哈希表 HashMap + 双向链表 LinkedList。把它拆开来，就会有以下实现：

  • HashMap + LinkedList。HashMap 用于快速定位双向链表中的结点；LinkedList 用于区分缓存 key 的访问顺序。
  • 双向链表必须自己手动建立并维护各种结点操作
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
class LRUCache {
    public List<Node> list = new LinkedList<>();
    public Map<Integer,Node> map = new HashMap<>();
    public int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }
        Node node = map.get(key);
        list.remove(node);
        list.addLast(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)){
            Node node = map.get(key);
            list.remove(node);
            node.value = value;
            list.addLast(node);
            return;
        }
        
        if(map.size()==capacity){
            Node oldNode = list.removeFirst();
            map.remove(oldNode.key);
        }
        Node newNode = new Node(key,value);
        list.addLast(newNode);
        map.put(key,newNode);
    }
}

class Node{
    int key;
    int value;
    Node pre,next;
    public Node(){};
    public Node(int key,int value){
        this.key = key;
        this.value = value;
    }
}

但是，上面的实现方法中使用了 LinkedList 的 remove(obj) 操作，这个操作的时间复杂度为 O(n)O(n)，不符合题目的时间复杂度要求。因此我们需要自己手写双向链表改进这块的时间复杂度。在接下来的实现中：

  • 使用循环双向链表，简化代码编写
  • 利用 HashMap 直接定位链表中待删除的 node，优化 remove(obj) 的时间复杂度
  • 只会编写必要的链表操作。
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
class LRUCache {
    public Node head = new Node();
    public Map<Integer,Node> map = new HashMap<>();
    public int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next=head;
        head.pre = head;
    }
    
    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }
        Node node = map.get(key);
        remove(node);
        addLast(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)){
            Node node = remove(map.get(key));
            node.value = value;
            addLast(node);
            return;
        }
        
        
        if(map.size()==capacity){
            Node oldNode = removeFirst();
            map.remove(oldNode.key);
        }
        Node newNode = new Node(key,value);
        addLast(newNode);
        map.put(key,newNode);
    }
    
    // 时间复杂度缩短至 O(1)
    public Node remove(Node node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
        return node;
    }
    
    public Node removeFirst(){
        return remove(head.next);
    }
    
    public void addLast(Node node){
        node.pre = head.pre;
        node.next = head;
        head.pre.next = node;
        head.pre = node;
    }
    
}

class Node{
    int key;
    int value;
    Node pre,next;
    public Node(){};
    public Node(int key,int value){
        this.key = key;
        this.value = value;
    }
}

最少使用置换算法 LFU

最近最不常用算法（LFU，Least Frequently Used）每次替换访问次数最小的数据，该算法的思想是最近一段时间被访问次数最小的数据在将来被访问的可能性最小。

🟥 460. LFU 缓存 - 力扣（LeetCode）

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。

实现 LFUCache 类：

  • LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
  • int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。
  • void put(int key, int value) 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最久未使用 的键。

为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1（由于 put 操作）。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

函数 get 和 put 必须以 O(1)O(1) 的平均时间复杂度运行。

同 LRU 中说明的顺序一样，我们还是先从 API 用法开始介绍，再慢慢改造为手工实现。

实现要点：

  • 双 HashMap，一个保存 key 对应的频数（频数用于索引链表以及快速判空），一个保存不同频数下保存的链表结构。
  • 链表结构选用 LinkedHashMap，使用它的一些特性：
    • 链表特性：在平局情况时快速获取最久未使用的结点（表头结点）；插入键时自动插入链表末端。
    • 哈希表特性：删除元素时能达到 O(1) 时间复杂度
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
class LFUCache {
    public Map<Integer,Map<Integer,Integer>> freq2map = new HashMap<>();
    public Map<Integer,Integer> key2freq = new HashMap<>();

    public int capacity;
    public int minfreq = 0;
    public LFUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        return move(key,null);
    }
    
    public void put(int key, int value) {
        if(move(key,value)!=-1){
            return;
        }
        if(key2freq.size()==capacity){
            Map<Integer,Integer> map = freq2map.get(minfreq);
            Integer k = map.keySet().iterator().next();
            map.remove(k);
            key2freq.remove(k);   
        }
        key2freq.put(key,1);
        freq2map.computeIfAbsent(1,k->new LinkedHashMap<>()).put(key,value);
        minfreq = 1;
    }
    
    public Integer move(Integer key, Integer value){
        Integer freq = key2freq.getOrDefault(key,null);
        if(freq==null){
            return -1;
        }
        
        // Integer value = freq2map.get(freq).remove(key);
        Map<Integer,Integer> map = freq2map.get(freq);
        if(value==null){
            value = map.get(key);
        }
        map.remove(key);
        if(map.size()==0 && minfreq==freq){
            minfreq++;
        }
    
        
        Integer newFreq= freq+1;
        key2freq.put(key,newFreq);
        freq2map.computeIfAbsent(newFreq,k->new LinkedHashMap<>()).put(key,value);
        return value;
    }
}

接下来，我们开始用 LinkedList 替换 LinkedHashMap。变化点：

  • 我们创建了 Node 结点，把频数内化到 Node 中。
  • 把频数哈希表变为 key2Node，要获取频数可以先得到 Node，在通过 node.freq 获取。
  • 使用 LinkedList 进行链表操作，自行模拟链表插入、删除操作维护链表顺序。
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
class LFUCache {
    
    public Map<Integer,LinkedList<Node>> freq2list = new HashMap<>();
    public Map<Integer,Node> key2node = new HashMap<>();

    public int capacity;
    public int minfreq = 0;
    public LFUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        return move(key,null);
    }
    
    public void put(int key, int value) {
        if(move(key,value)!=-1){
            return;
        }
        if(key2node.size()==capacity){
            List<Node> list = freq2list.get(minfreq);
            Node oldNode = list.removeFirst();
            key2node.remove(oldNode.key);   
        }
        Node newNode = new Node(key,value,1);
        key2node.put(key,newNode);
        freq2list.computeIfAbsent(1,k->new LinkedList<>()).add(newNode);
        minfreq = 1;
    }
    
    public Integer move(Integer key, Integer value){
        Node node = key2node.getOrDefault(key,null);
        if(node==null){
            return -1;
        }
        
        LinkedList<Node> list = freq2list.get(node.freq);
        if(value==null){
            value = node.value;
        }
        list.remove(node); // 不为 O(1)
        if(list.size()==0 && minfreq==node.freq){
            minfreq++;
        }
    
        node.freq++;
        node.value = value;
        freq2list.computeIfAbsent(node.freq,k->new LinkedList<>()).add(node);
        return value;
    }
}

class Node{
    int key;
    int value;
    int freq;
    public Node(){};
    public Node(int key,int value,int freq){
        this.key = key;
        this.value = value;
        this.freq = freq;
    }
}

在上面的实现中，还是存在 LinkedList 的 remove(obj) 的时间复杂度过高的问题。我们需要字节写双向链表。要点：

  • 自写循环双向链表，降低代码实现难度
  • 利用 key2Node 哈希表能在 O(1)O(1) 时间内定位待删结点，降低时间复杂度。
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
class LFUCache {
    
    public Map<Integer,MyLinkedList> freq2list = new HashMap<>();
    public Map<Integer,Node> key2node = new HashMap<>();

    public int capacity;
    public int minfreq = 0;
    public LFUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        return move(key,null);
    }
    
    public void put(int key, int value) {
        if(move(key,value)!=-1){
            return;
        }
        if(key2node.size()==capacity){
            MyLinkedList list = freq2list.get(minfreq);
            Node oldNode = list.removeFirst();
            key2node.remove(oldNode.key);   
        }
        Node newNode = new Node(key,value,1);
        key2node.put(key,newNode);
        freq2list.computeIfAbsent(1,k->new MyLinkedList()).add(newNode);
        minfreq = 1;
    }
    
    public Integer move(Integer key, Integer value){
        Node node = key2node.getOrDefault(key,null);
        if(node==null){
            return -1;
        }
        
        MyLinkedList list = freq2list.get(node.freq);
        if(value==null){
            value = node.value;
        }
        list.remove(node);
        if(list.size==0 && minfreq==node.freq){
            minfreq++;
        }
    
        node.freq++;
        node.value = value;
        freq2list.computeIfAbsent(node.freq,k->new MyLinkedList()).add(node);
        return value;
    }
}

class Node{
    int key;
    int value;
    int freq;
    Node pre;
    Node next;
    public Node(){};
    public Node(Node pre,Node next){
        this.pre = pre;
        this.next = next;
    }
    public Node(int key,int value,int freq){
        this.key = key;
        this.value = value;
        this.freq = freq;
    }
}

class MyLinkedList{
    Node dummy;
    int size=0;
    public MyLinkedList(){
        this.dummy = new Node();
        this.dummy.next = this.dummy;
        this.dummy.pre = this.dummy;
    }
    
    public void add(Node node){
        Node lastNode = dummy.pre;
        lastNode.next = node;
        dummy.pre = node;
        node.pre = lastNode;
        node.next = dummy;
        this.size++;
    }
    
    public Node remove(Node node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
        this.size--;
        return node;
    }
    
    public Node removeFirst(){
        return remove(this.dummy.next);
    }
   
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

本文参考