c语言实现lru缓存的核心在于结合哈希表与双向链表。1. 哈希表用于快速查找，时间复杂度为o(1)；2. 双向链表维护访问顺序，最近使用项置于头部，最久未用项置于尾部；3. 缓存项结构包含key、value及前后指针；4. 初始化时分配内存并初始化哈希表和互斥锁；5. 获取缓存时命中则移动至链表头部；6. 设置缓存时若存在则更新并移动，否则新建节点插入头部并可能淘汰尾部节点；7. 使用链地址法处理哈希冲突，头插法插入节点；8. 通过添加pthread互斥锁解决线程安全问题，在操作缓存前加锁，操作后解锁；9. 哈希函数选择需考虑均匀性、高效性和简单性，如murmurhash、fnv-1a或djb2等，以提升性能。
C语言实现LRU缓存，核心在于结合哈希表快速查找和双向链表维护访问顺序。哈希表用于O(1)时间复杂度查找缓存项，双向链表则用于记录缓存项的使用情况，最近使用的放在链表头部，最久未使用的放在尾部。
解决方案
-
数据结构定义：
立即学习“C语言免费学习笔记（深入）”；
typedef struct CacheNode { char *key; void *value; struct CacheNode *prev; struct CacheNode *next; } CacheNode; typedef struct LRUCache { size_t capacity; size_t size; CacheNode *head; CacheNode *tail; // 哈希表，存储 key -> CacheNode* 的映射 CacheNode **table; } LRUCache; -
初始化LRU缓存：
LRUCache* lruCacheCreate(size_t capacity) { LRUCache* cache = (LRUCache*)malloc(sizeof(LRUCache)); cache->capacity = capacity; cache->size = 0; cache->head = NULL; cache->tail = NULL; cache->table = (CacheNode**)calloc(capacity, sizeof(CacheNode*)); // 哈希表初始化 return cache; } -
哈希函数（简单示例）：
unsigned long hash(const char *key) { unsigned long hash = 5381; int c; while ((c = *key++)) hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ return hash; } -
获取缓存项：
void* lruCacheGet(LRUCache* cache, const char *key) { unsigned long index = hash(key) % cache->capacity; CacheNode* node = cache->table[index]; // 查找哈希表中是否存在该key while (node != NULL) { if (strcmp(node->key, key) == 0) { // 命中缓存，将节点移动到链表头部 // 1. 从链表中移除 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; // 如果是尾节点，更新尾节点 } // 2. 将节点添加到链表头部 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; // 如果是第一个节点，同时更新尾节点 } return node->value; } node = node->next; // 哈希冲突，链表解决 } return NULL; // 未找到 } -
设置缓存项：
void lruCachePut(LRUCache* cache, const char *key, void *value) { unsigned long index = hash(key) % cache->capacity; CacheNode* existingNode = cache->table[index]; // 检查key是否已存在 while (existingNode != NULL) { if (strcmp(existingNode->key, key) == 0) { // Key已存在，更新value并移动到链表头部 existingNode->value = value; // 移动到头部 (同get操作) if (existingNode->prev != NULL) { existingNode->prev->next = existingNode->next; } else { cache->head = existingNode->next; } if (existingNode->next != NULL) { existingNode->next->prev = existingNode->prev; } else { cache->tail = existingNode->prev; } existingNode->prev = NULL; existingNode->next = cache->head; if (cache->head != NULL) { cache->head->prev = existingNode; } cache->head = existingNode; if (cache->tail == NULL) { cache->tail = existingNode; } return; } existingNode = existingNode->next; // 处理哈希冲突 } // Key不存在，创建新节点 CacheNode* newNode = (CacheNode*)malloc(sizeof(CacheNode)); newNode->key = strdup(key); // 复制key，避免外部修改 newNode->value = value; newNode->prev = NULL; newNode->next = cache->head; if (cache->head != NULL) { cache->head->prev = newNode; } cache->head = newNode; if (cache->tail == NULL) { cache->tail = newNode; } // 添加到哈希表 newNode->next = cache->table[index]; // 头插法解决哈希冲突 cache->table[index] = newNode; cache->size++; // 如果超出容量，移除链表尾部节点 if (cache->size > cache->capacity) { CacheNode* tailNode = cache->tail; if (tailNode != NULL) { // 1. 从链表中移除 cache->tail = tailNode->prev; if (cache->tail != NULL) { cache->tail->next = NULL; } else { cache->head = NULL; // 链表为空 } // 2. 从哈希表中移除（需要遍历哈希表对应链表） unsigned long tailIndex = hash(tailNode->key) % cache->capacity; CacheNode* current = cache->table[tailIndex]; CacheNode* prev = NULL; while (current != NULL) { if (current == tailNode) { if (prev == NULL) { cache->table[tailIndex] = current->next; // 移除头节点 } else { prev->next = current->next; } break; } prev = current; current = current->next; } free(tailNode->key); free(tailNode); cache->size--; } } } -
释放LRU缓存：
void lruCacheFree(LRUCache* cache) { CacheNode* current = cache->head; while (current != NULL) { CacheNode* next = current->next; free(current->key); free(current); current = next; } free(cache->table); free(cache); }
C语言LRU缓存实现中的哈希冲突如何处理？
在lruCachePut函数中，当计算出的哈希索引对应的位置已经存在节点时，采用链地址法解决冲突。新的节点会以头插法的方式插入到哈希表对应索引的链表中。在lruCacheGet函数中，如果发生哈希冲突，会遍历链表，直到找到匹配的key。
C语言实现LRU缓存的线程安全性问题
上述代码并非线程安全。在多线程环境下，对缓存的并发访问可能导致数据竞争和不一致。例如，多个线程同时尝试插入或删除节点，可能导致链表结构损坏或哈希表数据不一致。
为了实现线程安全，需要使用互斥锁（mutex）来保护对缓存数据结构的访问。
-
添加互斥锁： 在
LRUCache结构体中添加一个互斥锁成员。typedef struct LRUCache { size_t capacity; size_t size; CacheNode *head; CacheNode *tail; CacheNode **table; pthread_mutex_t mutex; // 互斥锁 } LRUCache; -
初始化互斥锁： 在
lruCacheCreate函数中初始化互斥锁。LRUCache* lruCacheCreate(size_t capacity) { // ... 其他初始化代码 ... pthread_mutex_init(&cache->mutex, NULL); // 初始化互斥锁 return cache; } -
加锁和解锁： 在
lruCacheGet、lruCachePut和lruCacheFree函数中，在访问或修改缓存数据结构之前加锁，操作完成后解锁。void* lruCacheGet(LRUCache* cache, const char *key) { pthread_mutex_lock(&cache->mutex); // 加锁 // ... 缓存访问代码 ... pthread_mutex_unlock(&cache->mutex); // 解锁 return result; } void lruCachePut(LRUCache* cache, const char *key, void *value) { pthread_mutex_lock(&cache->mutex); // 加锁 // ... 缓存修改代码 ... pthread_mutex_unlock(&cache->mutex); // 解锁 } void lruCacheFree(LRUCache* cache) { pthread_mutex_lock(&cache->mutex); // 加锁 // ... 缓存释放代码 ... pthread_mutex_unlock(&cache->mutex); // 解锁 pthread_mutex_destroy(&cache->mutex); // 销毁互斥锁 // ... 其他释放代码 ... }
如何选择合适的哈希函数以提高LRU缓存性能？
哈希函数的选择对LRU缓存的性能至关重要。一个好的哈希函数应该具有以下特点：
- 均匀性： 哈希函数应该将不同的key均匀地映射到哈希表的各个槽位，避免出现大量的哈希冲突。
- 高效性： 哈希函数的计算速度应该足够快，以减少缓存操作的延迟。
- 简单性： 哈希函数的实现应该简单易懂，方便维护和调试。
一些常用的哈希函数包括：
- MurmurHash： 一种非加密哈希函数，具有良好的均匀性和高效性。
- FNV-1a： 另一种非加密哈希函数，实现简单，性能也不错。
- DJB2： 一种经典的哈希函数，广泛应用于各种场景。
选择哈希函数时，需要根据具体的应用场景进行权衡。如果对性能要求非常高，可以考虑使用MurmurHash或FNV-1a。如果对实现简单性要求较高，可以使用DJB2。此外，还可以根据key的特点选择特定的哈希函数，例如，如果key是字符串，可以使用专门为字符串设计的哈希函数。
