【数据结构】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;
}

在上面的代码中，定义了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;
}

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