【数据结构】LRU缓存

LRU缓存

LRU（Least Recently Used，最近最少使用）缓存是一种缓存淘汰策略，用于管理缓存中数据的存储和淘汰。LRU缓存会优先淘汰最近最少使用的数据，以便为新数据腾出空间。它通常用于提高应用程序的性能，通过缓存常用的数据来减少对磁盘或数据库的访问次数。

LRU缓存的基本原理

• 缓存：LRU缓存通过一个数据结构（通常是字典或散列表）来存储缓存中的数据。数据可以通过键值对的形式存储和访问。
• 淘汰策略：LRU缓存使用一个有序的数据结构（通常是双向链表）来跟踪数据的使用顺序。数据的插入、访问和删除操作都会更新链表中的数据顺序，以便保持最近最少使用的数据在链表的尾部。
• 插入操作：当向缓存中插入新数据时，如果缓存已满，则会根据LRU策略删除最近最少使用的数据，然后插入新数据。
• 访问操作：当访问缓存中的数据时，该数据会被移动到链表的头部，以表示它是最近被使用的数据。
• 删除操作：当缓存已满且需要插入新数据时，会删除链表尾部的最近最少使用的数据。

LRU缓存的优点

• 提高性能：LRU缓存通过缓存常用的数据，减少了对慢速存储设备（如磁盘或数据库）的访问次数，从而提高了应用程序的性能。
• 自适应淘汰：LRU策略根据数据的访问频率和顺序自动调整缓存中的数据，从而保持缓存中的数据始终是最近最常用的数据。

LRU缓存的缺点

• 内存开销：LRU缓存需要额外的内存来维护数据的有序链表。
• 复杂性：实现LRU缓存需要维护数据的顺序，并处理数据的插入、访问和删除操作。

C语言中的LRU缓存示例

下面是一个使用C语言实现的LRU缓存示例，展示了基本的插入、访问和删除操作。

首先，定义LRU缓存的数据结构和相关操作：

#include <stdio.h>
#include <stdlib.h>

// 定义缓存的最大大小
#define MAX_SIZE 3

// 双向链表节点
typedef struct Node {
    int key;
    int value;
    struct Node *prev;
    struct Node *next;
} Node;

// LRU缓存结构
typedef struct {
    Node *head;
    Node *tail;
    int size;
    Node *hashTable[MAX_SIZE];  // 哈希表，用于快速查找节点
} LRUCache;

// 初始化LRU缓存
LRUCache *initLRUCache() {
    LRUCache *cache = (LRUCache *)malloc(sizeof(LRUCache));
    cache->head = NULL;
    cache->tail = NULL;
    cache->size = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        cache->hashTable[i] = NULL;
    }
    return cache;
}

// 释放LRU缓存
void freeLRUCache(LRUCache *cache) {
    Node *current = cache->head;
    while (current != NULL) {
        Node *next = current->next;
        free(current);
        current = next;
    }
    free(cache);
}

// 将节点移动到链表的头部
void moveToHead(LRUCache *cache, Node *node) {
    if (cache->head == node) {
        // 节点已经在头部
        return;
    }
    // 将节点从当前位置移除
    if (node->prev != NULL) {
        node->prev->next = node->next;
    } else {
        cache->head = node->next;
    }
    if (node->next != NULL) {
        node->next->prev = node->prev;
    } else {
        cache->tail = node->prev;
    }
    // 将节点插入到头部
    node->prev = NULL;
    node->next = cache->head;
    if (cache->head != NULL) {
        cache->head->prev = node;
    }
    cache->head = node;
    if (cache->tail == NULL) {
        cache->tail = node;
    }
}

// 插入键值对到缓存中
void put(LRUCache *cache, int key, int value) {
    int hashIndex = key % MAX_SIZE;
    Node *node = cache->hashTable[hashIndex];
    while (node != NULL) {
        if (node->key == key) {
            // 键已存在，更新值并移动到头部
            node->value = value;
            moveToHead(cache, node);
            return;
        }
        node = node->next;
    }
    // 键不存在，创建新节点
    node = (Node *)malloc(sizeof(Node));
    node->key = key;
    node->value = value;
    node->prev = NULL;
    node->next = NULL;
    // 将新节点插入到头部
    moveToHead(cache, node);
    cache->hashTable[hashIndex] = node;
    cache->size++;
    // 如果缓存已满，删除最近最少使用的节点
    if (cache->size > MAX_SIZE) {
        Node *tailNode = cache->tail;
        // 从哈希表中移除
        int tailHashIndex = tailNode->key % MAX_SIZE;
        cache->hashTable[tailHashIndex] = NULL;
        // 从链表中移除
        cache->tail = tailNode->prev;
        if (cache->tail != NULL) {
            cache->tail->next = NULL;
        } else {
            cache->head = NULL;
        }
        free(tailNode);
        cache->size--;
    }
}

// 从缓存中获取值
int get(LRUCache *cache, int key) {
    int hashIndex = key % MAX_SIZE;
    Node *node = cache->hashTable[hashIndex];
    while (node != NULL) {
        if (node->key == key) {
            // 键存在，移动到头部并返回值
            moveToHead(cache, node);
            return node->value;
        }
        node = node->next;
    }
    // 键不存在
    return -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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

在上面的代码中，定义了LRU缓存的数据结构 LRUCache，包含一个双向链表（用于跟踪数据的使用顺序）和哈希表（用于快速查找节点）。同时，定义了插入和访问操作。

• 插入操作：当插入新键值对时，如果键已经存在，则更新值并将节点移动到链表的头部。如果键不存在，则创建新节点并插入到头部。如果缓存已满，则删除链表尾部的节点。
• 访问操作：当访问缓存中的键时，如果键存在，则将节点移动到链表的头部并返回值；否则返回 -1。

接下来，示例代码展示了如何使用LRU缓存：

int main() {
    // 初始化LRU缓存
    LRUCache *cache = initLRUCache();

    // 插入键值对
    put(cache, 1, 100);
    put(cache, 2, 200);
    put(cache, 3, 300);
    
    // 获取值
    printf("获取键1的值：%d\n", get(cache, 1));  // 输出100
    printf("获取键2的值：%d\n", get(cache, 2));  // 输出200
    printf("获取键3的值：%d\n", get(cache, 3));  // 输出300

    // 插入新键值对，会淘汰最久未使用的键2
    put(cache, 4, 400);

    // 获取值
    printf("获取键1的值：%d\n", get(cache, 1));  // 输出100
    printf("获取键2的值：%d\n", get(cache, 2));  // 输出-1（键2被淘汰）
    printf("获取键3的值：%d\n", get(cache, 3));  // 输出300
    printf("获取键4的值：%d\n", get(cache, 4));  // 输出400

    // 释放LRU缓存
    freeLRUCache(cache);

    return 0;
}
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

在上面的代码中，我们首先初始化一个LRU缓存，然后插入键值对 (1, 100)、(2, 200) 和 (3, 300)。接着，通过调用 get() 函数获取这些键的值。在插入新键值对 (4, 400) 后，最久未使用的键 (2, 200) 被淘汰。因此，再次获取键 2 的值时，将返回 -1。

总结

LRU缓存是一种基于双向链表和哈希表的数据结构，用于管理缓存中的数据并自动淘汰最近最少使用的数据。它通过高效的插入、访问和删除操作，提高了应用程序的性能。LRU缓存非常适合用于对数据访问频率较高且具有较强时效性的数据集。