C语言实现LRU缓存：哈希表与链表结合应用

C语言实现LRU缓存的核心在于结合哈希表与双向链表。1. 哈希表用于快速查找，时间复杂度为O(1)；2. 双向链表维护访问顺序，最近使用项置于头部，最久未用项置于尾部；3. 缓存项结构包含key、value及前后指针；4. 初始化时分配内存并初始化哈希表和互斥锁；5. 获取缓存时命中则移动至链表头部；6. 设置缓存时若存在则更新并移动，否则新建节点插入头部并可能淘汰尾部节点；7. 使用链地址法处理哈希冲突，头插法插入节点；8. 通过添加pthread互斥锁解决线程安全问题，在操作缓存前加锁，操作后解锁；9. 哈希函数选择需考虑均匀性、高效性和简单性，如MurmurHash、FNV-1a或DJB2等，以提升性能。

C语言实现LRU缓存，核心在于结合哈希表快速查找和双向链表维护访问顺序。哈希表用于O(1)时间复杂度查找缓存项，双向链表则用于记录缓存项的使用情况，最近使用的放在链表头部，最久未使用的放在尾部。

解决方案

1. 数据结构定义：

   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;

2. 初始化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;
   }

3. 哈希函数（简单示例）：

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

4. 获取缓存项：

   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; // 未找到
   }

5. 设置缓存项：

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

6. 释放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）来保护对缓存数据结构的访问。

1. 添加互斥锁： 在LRUCache结构体中添加一个互斥锁成员。

   typedef struct LRUCache {
       size_t capacity;
       size_t size;
       CacheNode *head;
       CacheNode *tail;
       CacheNode **table;
       pthread_mutex_t mutex; // 互斥锁
   } LRUCache;

2. 初始化互斥锁： 在lruCacheCreate函数中初始化互斥锁。

   LRUCache* lruCacheCreate(size_t capacity) {
       // ... 其他初始化代码 ...
       pthread_mutex_init(&cache->mutex, NULL); // 初始化互斥锁
       return cache;
   }

3. 加锁和解锁： 在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是字符串，可以使用专门为字符串设计的哈希函数。