今天主要给大家分享下基于C语言实现的LRU缓存淘汰算法。
缓存，是一种提高数据读取性能的技术，不论是在硬件，还是软件设计中都会被广泛的应用。
在软件设计中，缓存的大小总是有限的。当缓存被使用完时，就需要对数据进行清理。在清理数据时，经常会使用到缓存淘汰策略来决定清理哪些不需要的数据。
常见的策略有下面三种：
先进先出策略FIFO
最少使用策略LFU
最近最少使用策略LRU
一般采用链表实现LRU，基本的思路如下
首先需要在缓存中维护一个双向链表，链表中的数据按照访问的时间从新到旧排列。当有一个数据被访问时，我们从链表头开始顺序遍历。
如果该数据在此之前已经被放入到了缓存中
我们需要将该数据的节点从原位置删除，然后重新将其放入到链表的表头。
如果该数据在这之前没有被放入缓存中
如果此时缓存没有满，则将此数据放入到链表的表头。
如果此时缓存已满，则需要先将链表尾部的数据删除，之后将该数据放入链表的表头。
上述方法在我们需要从缓存中查找数据时，都需要遍历一遍数据。因此，这种做法的时间复杂度为O(n)。
使用哈希表保证缓存的访问速度
为了提高上述方法的时间复杂度，我们除了需要将数据维护在双向链表中，还需要将数据维护在哈希表中。哈希表的数据访问的时间复杂度为O(1)
LRU缓存内部数据结构
- LRU缓存包含了一个双向链表和一个哈希表
/* 定义LRU缓存 */ typedef struct LRUCacheS{ sem_t cache_lock; int cacheCapacity; /*缓存的容量*/ int lruListSize; /*缓存的双向链表节点个数*/ cacheEntryS **hashMap; /*缓存的哈希表*/ cacheEntryS *lruListHead; /*缓存的双向链表表头*/ cacheEntryS *lruListTail; /*缓存的双向链表表尾*/ }LRUCacheS;
缓存中的数据单元
- 缓存中的数据单元，既是一个双向链表的节点，也是哈希表中的一个节点。
typedef struct cacheEntryS{ char key[KEY_SIZE]; /* 数据的key */ char data[VALUE_SIZE]; /* 数据的data */ sem_t entry_lock; struct cacheEntryS *hashListPrev; /* 缓存哈希表指针， 指向哈希链表的前一个元素 */ struct cacheEntryS *hashListNext; /* 缓存哈希表指针， 指向哈希链表的后一个元素 */ struct cacheEntryS *lruListPrev; /* 缓存双向链表指针， 指向链表的前一个元素 */ struct cacheEntryS *lruListNext; /* 缓存双向链表指针， 指向链表后一个元素 */ }cacheEntryS;
测试
int main(int argc, char **argv){ void *LruCache; //创建缓存器 if (0 == LRUCacheCreate(3, &LruCache)) printf("缓存器创建成功，容量为3\n"); //向缓存器中添加数据 if (0 != LRUCacheSet(LruCache, "key1", "value1")) printf("put (key1, value1) failed!\n"); if (0 != LRUCacheSet(LruCache, "key2", "value2")) printf("put (key2, value2) failed!\n"); if (0 != LRUCacheSet(LruCache, "key3", "value3")) printf("put (key3, value3) failed!\n"); if (0 != LRUCacheSet(LruCache, "key4", "value4")) printf("put (key4, value4) failed!\n"); if (0 != LRUCacheSet(LruCache, "key5", "value5")) printf("put (key5, value5) failed!\n"); //按照顺序输出缓存器当前的内容 LRUCachePrint(LruCache); //获取缓存器内容 if (NULL == LRUCacheGet(LruCache, "key1")){ printf("key1 所对应的数据未被缓存\n"); } else{ char data[VALUE_SIZE]; strncpy(data, LRUCacheGet(LruCache, "key1"), VALUE_SIZE); printf("key1所对应的数据为:%s", data); } char value4[VALUE_SIZE]; strncpy(value4, LRUCacheGet(LruCache, "key4"), VALUE_SIZE); printf("key4所对应的数据:%s", value4); LRUCachePrint(LruCache); //销毁缓存器 if (0 != LRUCacheDestory(LruCache)) printf("destory error"); }
- 结果
