AHA'S BOOK

LRU 缓存：请你设计并实现一个满足 LRU（Least Recently Used）缓存约束的数据结构。

实现 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) 的平均时间复杂度运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入 
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
 输出 
[null, null, null, 1, null, -1, null, -1, 3, 4]

 解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

题目分析

最近最久使用页面置换算法（Least Recently Used, LRU）是操作系统中局部页面置换算法中性能较好的一种算法，当一个缺页中断发生时，它选择 最近最久未使用 的那个页面淘汰。

在题目中，如果 get 方法获取的关键字存在于缓存中，除了要返回关键字对应的值，同时 这条记录将会被刷新为最近（最新）被使用的一条记录 。同样地，如果 put 方法存储的关键字存在于缓存中，除了要修改关键字对应的值，同时 这条记录也将会被刷新为最近（最新）被使用的一条记录。

题目还要求使用 O(1) 的平均时间复杂度完成 get 和 put 方法，这可以使用「双向链表」和「哈希表」来共同设计这个 LRU 缓存数据结构。

双向链表 + 哈希表

使用「双向链表」和「哈希表」来共同设计这个 LRU 缓存数据结构：

  • 双向链表用于维护缓存中的记录，使得这些记录按照访问时间顺序排序，也就是「链表头为最近最久未使用」的一条记录，「链表尾为最新使用」的一条记录。
  • 哈希表用于存储「节点关键字和它在链表中的地址」。

这样，我们在进行 get 操作时，可以使用关键字查找哈希表中的 key，来获取它在双向链表中的地址：

  • 若查找失败，则返回 -1；
  • 若查找成功，则将对应的节点从链表头部（或中间、尾部）移动到链表的尾部。

在进行 put 操作时，可以使用关键字查找哈希表中的 key，来获取它在双向链表中的地址：

  • 若查找成功，则将对应的节点从链表头部（或中间、尾部）移动到链表的尾部；
  • 若查找失败，则需要新建一个节点并将其追加到链表尾部，在追加节点前，需要判断缓存大小是否小于容量大小：
    • 若小于，则直接新建一个节点并将其追加到链表尾部即可；
    • 若不小于，则需要删除链表头的节点，并将该节点从哈希表中删除；再新建一个节点并将其追加到链表尾部。

数据结构设计

双向链表：

1
2
3
4
5
6
7
// 定义双向链表的结构体
typedef struct doubleLinked {
    int page;  // 键，逻辑页面
    int frame;  // 值，物理页帧面
    struct doubleLinked *prev;  // 前一个节点指针
    struct doubleLinked *next;  // 后一个节点指针
} stDLinked;

哈希表：

1
2
3
4
5
6
// 定义哈希表的结构体
typedef struct {
    int key;  // 键，对应着双向链表的键
    struct doubleLinked *dlNode;  // 双向链表节点指针
    UT_hash_handle hh;  // 哈希表句柄
} stHash;

LRU 缓存：

1
2
3
4
5
6
7
8
// 定义 LRU 缓存的结构体
typedef struct {
    stDLinked *front;  // 链表头指针
    stDLinked *rear;  // 链表尾指针
    stHash *hashTbl;  // 哈希表指针
    int size;  // 当前缓存大小
    int capacity;  // 缓存容量
} LRUCache;

上述数据结构关系图：

LRU 缓存结构

接口实现

创建 LRU 缓存：

1
2
3
4
5
6
7
8
9
10
11
// 创建 LRU 缓存
LRUCache *lRUCacheCreate(int capacity) {
    LRUCache *lru = (LRUCache *)malloc(sizeof(LRUCache));
    lru->front = NULL;
    lru->rear = NULL;
    lru->hashTbl = NULL; // 哈希表指针初始化为空
    lru->size = 0;
    lru->capacity = capacity;

    return lru;
}

实现 get 方法和 put 方法：

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
void printDLinked(stDLinked *node) {
    printf("print DL: ");
    while (node) {
        printf("(%d, %d)->", node->page, node->frame);
        node = node->next;
    }
    printf("NULL\n");
}

// 将指定的节点移动到尾结点后
void dlNodeMoveToRear(LRUCache *obj, stDLinked *node) {
    if (!node) { return; }
    
    stDLinked *prevNode = node->prev;
    stDLinked *nextNode = node->next;

    // 指定的节点是链表首节点，但不是链表尾结点
    if (!prevNode && nextNode) {
        nextNode->prev = prevNode;
        obj->front = nextNode;
        obj->rear->next = node;
        node->prev = obj->rear;
        node->next = NULL;
        obj->rear = node;
    } else if (prevNode && nextNode) { // 指定的节点是链表中间节点
        nextNode->prev = prevNode;
        prevNode->next = nextNode;
        obj->rear->next = node;
        node->prev = obj->rear;
        node->next = NULL;
        obj->rear = node;
    }
    // 指定的节点是链表尾结点无需处理
}

// 创建 LRU 缓存
LRUCache *lRUCacheCreate(int capacity) {
    LRUCache *lru = (LRUCache *)malloc(sizeof(LRUCache));
    lru->front = NULL;
    lru->rear = NULL;
    lru->hashTbl = NULL; // 哈希表指针初始化为空
    lru->size = 0;
    lru->capacity = capacity;

    return lru;
}

// 获取指定的逻辑页面对应的物理页帧号，若存在，则一并将该页表项移动到链表尾部
int lRUCacheGet(LRUCache *obj, int key) {
    int res = -1;
    stHash *hashNode = NULL;
    HASH_FIND_INT(obj->hashTbl, &key, hashNode);

    if (hashNode) {
        res = hashNode->dlNode->frame;
        dlNodeMoveToRear(obj, hashNode->dlNode);
    }
    // printf("Get: (%d, %d) ", key, res);
    // printDLinked(obj->front);
    return res;
}

// 往链表中插入页表项，若逻辑页面存在，则修改对应的物理页帧号并将该页表项移动到链表尾部，
// 不存在，则直接将该页表项移动到链表尾部
void lRUCachePut(LRUCache *obj, int key, int value) {
    stHash *hashNode = NULL;
    HASH_FIND_INT(obj->hashTbl, &key, hashNode);
    if (hashNode) { // 一. 存在逻辑页面，则直接移动该页表项到链表尾部
        dlNodeMoveToRear(obj, hashNode->dlNode);
    } else { // 二. 不存在逻辑页面，则将该页表项移动到链表尾部
        // 0. 申请追加的链表节点
        stDLinked *addNode = (stDLinked *)malloc(sizeof(stDLinked));
        addNode->next = NULL;
        addNode->prev = NULL;

        // 1. 先检查链表长度是否大于等于最大容量，是则先删除链表头，再追加节点
        if (obj->size >= obj->capacity) {
            // 1.1 获取链表头节点，并与双向链表断开
            stDLinked *delNode = obj->front;
            obj->front = obj->front->next;
            if (obj->front) { obj->front->prev = NULL; }

            // 1.2 从哈希表中删除对应的哈希节点
            stHash *delHashNode = NULL;
            int delKey = delNode->page;
            HASH_FIND_INT(obj->hashTbl, &delKey, delHashNode);
            HASH_DEL(obj->hashTbl, delHashNode);
            free(delHashNode);

            // 1.3 释放链表节点空间
            delNode->next = NULL;
            free(delNode);
            // 1.4 链表长度减一
            obj->size--;
        }
        // 2. 追加节点：分为链表为空和非空两种情况
        if (obj->size == 0) {
            obj->front = addNode;
            obj->rear = obj->front;
        } else {
            obj->rear->next = addNode;
            addNode->prev = obj->rear;
            obj->rear = addNode;
        }
        // 3. 追加节点后，将其添加到哈希表中
        hashNode = (stHash *)malloc(sizeof(stHash));
        hashNode->key = key;
        hashNode->dlNode = addNode;
        HASH_ADD_INT(obj->hashTbl, key, hashNode);
        // 4. 追加节点后，链表长度加一
        obj->size++;
    }
    // 三. 最后，统一修改或添加逻辑页面对应的物理页面
    hashNode->dlNode->page = key;
    hashNode->dlNode->frame = value;
    // printf("Put: (%d, %d) ", key, value);
    // printDLinked(obj->front);
}

// 释放哈希表空间
void hashFree(stHash **obj) {
    stHash *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp) {
        HASH_DEL(*obj, curr);
        free(curr);
    }
}

// 释放 LRU 缓存空间
void lRUCacheFree(LRUCache *obj) {
    if (obj) {
        hashFree(&(obj->hashTbl));
        while (obj->front) {
            stDLinked *tmp = obj->front;
            obj->front = obj->front->next;
            tmp->next = NULL;
            free(tmp);
        }
        free(obj);
    }
}

/**
 * Your LRUCache struct will be instantiated and called as such:
 * LRUCache* obj = lRUCacheCreate(capacity);
 * int param_1 = lRUCacheGet(obj, key);
 
 * lRUCachePut(obj, key, value);
 
 * lRUCacheFree(obj);
*/

代码执行结果

针对上面的测试用例，给出了每步操作后的双向链表的内容，如下。

1
2
3
4
5
6
7
8
9
Put: (1, 1) print DL: (1, 1)->NULL
Put: (2, 2) print DL: (1, 1)->(2, 2)->NULL
Get: (1, 1) print DL: (2, 2)->(1, 1)->NULL
Put: (3, 3) print DL: (1, 1)->(3, 3)->NULL
Get: (2, -1) print DL: (1, 1)->(3, 3)->NULL
Put: (4, 4) print DL: (3, 3)->(4, 4)->NULL
Get: (1, -1) print DL: (3, 3)->(4, 4)->NULL
Get: (3, 3) print DL: (4, 4)->(3, 3)->NULL
Get: (4, 4) print DL: (3, 3)->(4, 4)->NULL
aha
2023-12-01
LeetCode 设计
Expand all Back to top Go to bottom Search in blogs
银河白
豆沙绿
杏仁黄
青草绿
秋叶褐