每日一题——LRU缓存机制的C语言实现详解

参考

建议先参考下面的视频

1. 数据结构设计

双向链表节点

typedef struct DulNode {int key;           // 缓存项的键int value;         // 缓存项的值struct DulNode* pre;  // 前驱节点指针struct DulNode* next; // 后继节点指针
} DulNode;

• 作用：维护缓存项的使用顺序，最近访问的节点靠近链表头部，未使用的节点靠近尾部。

哈希表节点

typedef struct HashTableNode {DulNode* node;          // 指向双向链表中的节点struct HashTableNode* next; // 处理哈希冲突的链表指针
} HashTableNode;

• 作用：通过哈希表快速定位缓存项，键为key，值为对应的双向链表节点。

哈希表

typedef struct HashTable {int capacity;         // 哈希表容量（桶数量）hash_cal_f hash_func; // 哈希函数指针HashTableNode** bucket; // 桶数组（存储链表头节点）
} HashTable;

• 作用：以O(1)时间复杂度查找键是否存在，结合双向链表实现LRU策略。

LRU缓存结构

typedef struct {int cur_node;       // 当前缓存中的节点数HashTable* hash_table; // 哈希表DulNode* head;      // 双向链表头节点（哨兵）DulNode* tail;      // 双向链表尾节点（哨兵）
} Solution;

• 作用：整合哈希表和双向链表，封装LRU缓存的核心操作。

---

2. 初始化哈希表和双向链表

哈希函数

int hash_cal(int capacity, int val) {return val % capacity; // 简单取模哈希
}

• 设计意图：将键值映射到哈希表的桶索引，均匀分布以减少冲突。

初始化哈希表

void InitHashTable(Solution* lruCache, int capacity) {HashTable* hash_table = malloc(sizeof(HashTable));hash_table->capacity = capacity;hash_table->hash_func = hash_cal;hash_table->bucket = calloc(capacity, sizeof(HashTableNode*));lruCache->hash_table = hash_table;
}

• 关键点：动态分配桶数组并初始化为NULL，避免野指针问题。

初始化双向链表

void InitDoubleList(Solution* lruCache) {// 创建头尾哨兵节点并连接成环lruCache->head = (DulNode*)malloc(sizeof(DulNode));lruCache->tail = (DulNode*)malloc(sizeof(DulNode));lruCache->head->pre = lruCache->tail;lruCache->head->next = lruCache->tail;lruCache->tail->pre = lruCache->head;lruCache->tail->next = lruCache->head;
}

• 设计优势：哨兵节点简化链表操作，无需处理头尾边界条件。

创建LRU缓存

Solution* SolutionCreate(int capacity) {Solution* lruCache = malloc(sizeof(Solution));lruCache->cur_node = 0;InitHashTable(lruCache, capacity);InitDoubleList(lruCache);return lruCache;
}

• 流程：分配内存后，初始化哈希表和双向链表。

---

3. 更新双向链表

void DulLinkLinkUpdateNode(DulNode* head, DulNode* node) {if (node->pre == head) return; // 已在头部无需处理// 摘除节点node->pre->next = node->next;node->next->pre = node->pre;// 插入到头部node->pre = head;node->next = head->next;head->next->pre = node;head->next = node;
}

• 作用：将节点移动到链表头部，表示最近被访问。

---

4. 实现Get操作

int SolutionGet(Solution* obj, int key) {if (obj->cur_node == 0) return -1;int h_index = obj->hash_table->hash_func(obj->hash_table->capacity, key);HashTableNode* hash_node = obj->hash_table->bucket[h_index];// 遍历哈希冲突链表while (hash_node && hash_node->node->key != key) hash_node = hash_node->next;if (hash_node) {DulLinkLinkUpdateNode(obj->head, hash_node->node); // 更新链表return hash_node->node->value;}return -1;
}

• 时间复杂度：O(1)（哈希表平均情况）。

---

5. 实现Put操作

更新节点值

void LRUCacheUpdateNode(Solution* obj, int key, int value) {// 查找并更新值，随后移动节点到头部int h_index = obj->hash_table->hash_func(obj->hash_table->capacity, key);HashTableNode* hash_node = obj->hash_table->bucket[h_index];while (hash_node && hash_node->node->key != key) hash_node = hash_node->next;if (hash_node) {hash_node->node->value = value;DulLinkLinkUpdateNode(obj->head, hash_node->node);}
}

删除最久未使用节点

void LRUCacheDelLastNode(Solution* obj) {DulNode* del_node = obj->tail->pre; // 尾节点的前驱为LRU节点// 从哈希表中删除int h_index = obj->hash_table->hash_func(obj->hash_table->capacity, del_node->key);HashTableNode *pre = NULL, *cur = obj->hash_table->bucket[h_index];while (cur && cur->node->key != del_node->key) {pre = cur;cur = cur->next;}if (cur) {if (pre) pre->next = cur->next;else obj->hash_table->bucket[h_index] = cur->next;free(cur);}// 从链表中删除del_node->pre->next = del_node->next;del_node->next->pre = del_node->pre;free(del_node);obj->cur_node--;
}

插入或更新节点

void SolutionPut(Solution* obj, int key, int value) {if (obj->cur_node >= obj->hash_table->capacity)LRUCacheDelLastNode(obj); // 缓存满时删除LRU节点if (SolutionGet(obj, key) != -1) { // Key存在则更新LRUCacheUpdateNode(obj, key, value);return;}// 创建新节点并插入链表头部DulNode* new_dul_node = malloc(sizeof(DulNode));new_dul_node->key = key;new_dul_node->value = value;new_dul_node->pre = obj->head;new_dul_node->next = obj->head->next;obj->head->next->pre = new_dul_node;obj->head->next = new_dul_node;// 插入哈希表HashTableNode* new_hash_node = malloc(sizeof(HashTableNode));new_hash_node->node = new_dul_node;int h_index = obj->hash_table->hash_func(obj->hash_table->capacity, key);new_hash_node->next = obj->hash_table->bucket[h_index];obj->hash_table->bucket[h_index] = new_hash_node; // 头插法obj->cur_node++;
}

---

6. 释放缓存

释放双向链表

void DulLinkLinkFree(DulNode* head) {DulNode* cur = head->next;while (cur != head) {DulNode* tmp = cur;cur = cur->next;free(tmp);}free(head->pre); // 释放尾节点free(head);
}

释放哈希表

void HashTableNodeFree(Solution* obj) {for (int i = 0; i < obj->hash_table->capacity; i++) {HashTableNode* cur = obj->hash_table->bucket[i];while (cur) {HashTableNode* tmp = cur;cur = cur->next;free(tmp);}}free(obj->hash_table->bucket);
}

释放LRU缓存

void SolutionFree(Solution* obj) {DulLinkLinkFree(obj->head);HashTableNodeFree(obj);free(obj->hash_table);free(obj);
}

---

7. 完整代码及测试

测试用例

int main() {Solution* cache = SolutionCreate(2);SolutionPut(cache, 1, 1);SolutionPut(cache, 2, 2);printf("Get(1) -> %d\n", SolutionGet(cache, 1)); // 1SolutionPut(cache, 3, 3); // 淘汰2printf("Get(2) -> %d\n", SolutionGet(cache, 2)); // -1SolutionFree(cache);return 0;
}

输出结果

Get(1) -> 1
Get(2) -> -1

---

总结

• 核心机制：通过双向链表维护访问顺序，哈希表实现快速查找。
• 时间复杂度：Get和Put操作均摊时间复杂度为O(1)。
• 优化点：哈希表采用链地址法处理冲突，双向链表使用哨兵节点简化操作。
• 适用场景：高频访问的缓存系统，需快速淘汰最久未使用数据。
  反正以我的能力远远不能解决问题。还是只能勉强把代码看懂。这题还是很难得，感觉没有一天时间，完全搞不定。放弃了，放弃了。