理解和实现 LRU 缓存置换算法

引言

在计算机科学中，缓存是一种用于提高数据访问速度的技术。然而，缓存空间是有限的，当缓存被填满时，就需要一种策略来决定哪些数据应该保留，哪些应该被淘汰。LRU（最近最少使用）算法是一种广泛使用的缓存淘汰策略，它基于一个简单的假设：如果数据最近被访问过，那么它在未来也更有可能被访问。

LRU算法简介

LRU算法的核心思想是：在缓存空间不足时，淘汰最长时间未被访问的数据项。这种策略适用于多种场景，包括Web缓存、数据库查询缓存、操作系统的页面置换等。

LRU算法的工作原理

LRU算法通常需要两种数据结构来实现：

哈希表：提供O(1)时间复杂度的数据访问和插入。
双向链表：维护数据项的使用顺序，最近使用的在头部，最久未使用的在尾部。

数据访问和插入的流程如下：

获取数据（Get）：从缓存中获取数据，如果数据存在（缓存命中），则将该数据移到链表头部；如果数据不存在（缓存未命中），返回 -1。
放入数据（Put）：将数据放入缓存，如果数据已经存在，则更新数据值并将该节点移到链表头部；如果数据不存在，则在链表头部插入新的节点，如果缓存已满，还需要移除链表尾部的节点。

LRU算法的实现

class LRUCache {
    /**
        整体思路：定义双向循环链表和Map，其中Map的key存储key，value存储链表节点.
        为什么定义双向循环链表，因为这样定义就不需要定义额外的头尾节点
    */

    static class Node{

        Node prev, next;
        int key, val;

        public Node(int key, int val){
            this.key = key;
            this.val = val;
        }
    }

    private Node dummy = new Node(-1,-1);
    
    Map<Integer, Node> mp = new HashMap<>();
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy.prev = dummy;
        dummy.next = dummy;
    }
    
    public int get(int key) {
    	// 判断是否在缓存
        Node node = mp.get(key);
        // 不在，直接返回-1
        if(node == null) return -1;
        // 在，就把当前节点移动到前面
        moveToHead(node);
        // 返回节点值
        return node.val;
    }
    
    public void put(int key, int value) {
    	// 判断是否在缓存
        Node node = mp.get(key);
        // 在，就把当前节点移动到前面
        if(node != null){
        	// 更新node.val
            node.val = value;
            moveToHead(node);
        }else{
        	// 不在，就加入
            node = new Node(key, value);
            mp.put(key, node);
            // 将新节点加入到头部
            insert(node);
            // 如果当前容量大于LRU容量，就移出
            if(mp.size() > capacity){
            	// 找到尾节点
                node = dummy.prev;
                // 删除尾节点
                del(node);
                // 从缓存移出对应的key
                mp.remove(node.key);
            }
        }
    }
	
	// 移动当前节点到头节点
    public void moveToHead(Node node){
        del(node);
        insert(node);
    }

	// 插入头部
    public void insert(Node node){
        node.prev = dummy;
        node.next = dummy.next;
        dummy.next.prev = node;
        dummy.next = node;
    }

	// 删除节点
    public void del(Node node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}
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

LRU算法的优势与局限

LRU算法的优势在于其简单性和效率。它能够快速地识别并淘汰最久未使用的数据项。然而，LRU也有局限性，它可能不适用于所有类型的访问模式，特别是那些具有周期性或随机性访问模式的场景。另外，在某些情况下，LRU 缓存可能会频繁地移除和加载数据，导致缓存抖动。这种现象在缓存大小接近于工作集大小时尤为明显。

结论

LRU算法是一种高效且广泛使用的缓存淘汰策略，适用于多种需要缓存的场景。通过理解其工作原理和实现方式，我们可以更好地利用缓存来提高系统性能。随着技术的发展，对LRU算法的优化和变种也在不断涌现，为不同的应用场景提供了更多的选择。