使用链表实现LRU cache

发表于 分类于

LRU（Least Recently Used，最近最少使用）算法是一种淘汰策略，简单来讲实现的是如下工作：将一些元素放在一个容量固定的容器中进行存取，由于容器的容量有限，该容器就要保证那些最近才被用到的元素始终在容器内，而将已经很久没有用的元素剔除，实现容器内元素的动态维护。这种算法是一种缓存维护策略，因为缓存空间有限，让缓存中存储的都是最近才被用到的元素可以实现系统缓存的高效运作。

结构与设计

需求

实现一个类LRUCache。

1.实现类的构造方法，使得该类的使用者可以通过设置初始化容量来创建一个指定容量的LRUCache。
2.实现该类对象的外部操作接口 —— get()成员函数。该函数的作用是查找一个指定的关键字是否在LRUCache对象中，如果在，返回该关键字的值，否则返回-1。即输入参数为一个int值key，返回一个int，代表LRUCache中关键字key对应的值。
3.实现该类对象的外部操作接口 —— put()成员函数。该函数的作用是将一个指定的键值对放入LRUCache对象中，该函数不需要向外返回任何值。即输入参数为一个int值key和一个int值value（代表一个键值对key-value），如果LRUCache中已存在该关键字key，则用参数列表中的value值更新LRUCache中key关键字对应的value，如果缓存中不存在该关键字key，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过缓存的初始容量 capacity ，则应该从缓存中删除最久未使用的关键字。

设计

根据以上要求，我们可以确定：

  1. LRUCache本身需要用一个具体的存储容器来实现，该容器内部存储的元素形式是键值对的形式，并且该容器查找元素是通过输入键，返回键所对应的值来实现的，因此可以确定，LRUCache容器本身可以使用哈希表这种数据结构来实现。并且根据键与值的参数类型可以确定，该哈希表的键和值都是int类型。

  2. LRUCache的int get(int key)接口完成的操作是哈希表本身就可以完成的操作。同时，该接口定义了缓存中元素被使用的含义，即最近一次通过get接口被查询到的键值对元素是缓存中最近一次被使用到的元素。

  3. LRUCache的void put(int key, int value)接口完成的操作隐含了动态维护LRUCache中元素的需求。动态维护的方法就是LRU算法，即将LRUCache中的元素（int键值对）按照使用的时间顺序排列。同时需要特别注意的是，该接口操作也定义了缓存中元素另一种被使用的含义，即最近一次通过put接口被放入缓存中的元素是缓存中最近一次被使用到的元素。
    可以通过双向链表来实现LRU算法，细节如下：

  4. 双向链表的节点存储内容是用来实现LRUCache容器的哈希表元素（int类型键值对）

  5. 双向链表存在界限，即最大节点数就是LRUCache的容量。

  6. 每次通过int get(int key)接口查询到LRUCache中的一个元素，就将该元素在双向链表中移动到头部。

  7. 操作LRUCache的void put(int key, int value)接口可能会使得双向链表的节点数增加（当缓存中没有该key值，且缓存容量未满时），每次put操作（无论是存在key，只是更新value，还是不存在key，插入新的key-value对）都会将该put操作的key-value元素在双向链表中移动到头部

  8. 通过上述操作，双向链表的尾节点一定是LRUCache中最久没有被使用过的元素，则当双向链表超出限定长度后，删除超长的尾节点
    要实现以上的双向链表操作，需要自己定义双向链表节点和相应的节点移动操作，在C++中可以通过自定义一个结构体或类来实现，其成员属性如下：

算法实现

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
import java.util.HashMap;
import java.util.Map;

public class LRUCache<K, V> {

    // 静态内部类，双向链表中的节点类，key理解为页面号，val理解为页面内容
    static class Entry<K, V> {
        public Entry<K, V> prev;
        public Entry<K, V> next;
        public K key;
        public V val;
        public Entry() {}
        public Entry(K key, V val) { this.key = key; this.val = val; }
    }

    private Entry<K, V> head, tail; // 虚拟头节点和虚拟尾节点
    private final int capacity;     // 缓存容量
    private int size;               // 缓存占用量
    Map<K, Entry<K, V>> cache;      // 哈希表，记录双向列表节点的地址值

    public LRUCache(int capacity) {
        this.capacity = capacity;
        initCache();
    }

    // 初始化LRU缓存
    private void initCache() {
        head = new Entry<>();
        tail = new Entry<>();
        head.next = tail;
        tail.prev = head;
        size = 0;
        cache = new HashMap<>(this.capacity);
    }

    private V get(K key) {
        Entry<K, V> entry = cache.get(key);
        if(entry != null) {
            moveToTail(entry);
            return entry.val;
        } else {
            return null;
        }
    }

    private void put(K key, V val) {
        Entry<K, V> entry = cache.get(key);
        if(entry != null) {
            // 缓存命中
            entry.val = val;
            moveToTail(entry);
        } else {
            // 缓存未命中
            if(size == capacity) {
                // 缓存已满，删除链表头部节点
                Entry<K, V> h = head.next;
                deleteEntry(h);
                cache.remove(h.key);
                size--;
            }
            // 添加新页面到链表尾部
            Entry<K, V> newEntry = new Entry<>(key, val);
            addToTail(newEntry);
            cache.put(key, newEntry);
            size++;
        }
    }

    private void moveToTail(Entry<K, V> entry) {
        deleteEntry(entry);
        addToTail(entry);
    }

    private void addToTail(Entry<K, V> entry) {
        if(entry != null) {
            entry.next = tail;
            entry.prev = tail.prev;
            tail.prev.next = entry;
            tail.prev = entry;
        }
    }

    private void deleteEntry(Entry<K, V> entry) {
        if(entry != null) {
            entry.prev.next = entry.next;
            entry.next.prev = entry.prev;
        }
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(2);
        cache.put(1,"可口可乐");
        cache.put(2,"雪碧");
        System.out.println("页面1的内容：" + cache.get(1));
        cache.put(3,"果粒橙"); // 此时缓存已满，且页面2最久未被使用（因为cache.get(1)访问了页面1），页面2被置换成页面3
        System.out.println("页面2的内容：" + cache.get(2)); // 页面2已被换出，访问不到
    }

}