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語言免費學習筆記（深入）”；
-
初始化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是字符串，可以使用專門為字符串設計的哈希函數。
? 版權聲明
文章版權歸作者所有，未經允許請勿轉載。
THE END
