LRU(Least recently used，最近最少使用)算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

常见的LRU实现策略是:

  1. 新数据插入到链表头部；
  2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
  3. 当链表满的时候，将链表尾部的数据丢弃。

但是如上实现存在一个问题：命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部，时间复杂度是$O(N)$。
未解决遍历带来的消耗，再此设计的是一种哈希表维护的双向链表结构，以减少寻找数据块时的时间消耗。

如上图所示，每个数据块拥有2个角度的身份，一个身份是缓存双向链表的成员，一个身份是哈希表成员。

LRU结构体设计

1
/*定义LRU缓存的缓存单元*/
2
typedef struct cacheEntryS{
3
    char key;     /* 数据块的key */
4
    char data;    /* 数据块的data */
5
    struct cacheEntryS *hashListPrev;  /* 缓存哈希表指针，指向哈希链表的前一个元素 */
6
    struct cacheEntryS *hashListNext;  /* 缓存哈希表指针，指向哈希链表的后一个元素 */
7
    struct cacheEntryS *lruListPrev;   /* 缓存双向链表指针，指向链表的前一个元素 */
8
    struct cacheEntryS *lruListNext;   /* 缓存双向链表指针，指向链表的后一个元素 */
9
}cacheEntryS;
10
/* 定义LRU缓存*/ 
11
typedef struct LRUCacheS{
12
    int cacheCapacity;        /*缓存的容量*/
13
    cacheEntryS **hashMap;    /*缓存的哈希表*/
14
    cacheEntryS *lruListHead; /*缓存双向链表表头*/
15
    cacheEntryS *lruListTail; /*缓存双向链表表尾*/
16
    int lruListSize;          /*缓存双向链表节点个数*/
17
}LRUCacheS;

双休链表相关接口实现

1
/*从双向链表中删除指定节点*/
2
static void removeFromList(LRUCacheS *cache, cacheEntryS *entry)
3
{
4
    /*链表为空*/
5
    if (cache->lruListSize==0)
6
        return ;
7
    if (entry==cache->lruListHead && entry==cache->lruListTail) {
8
    /*链表中仅剩当前一个节点*/
9
        cache->lruListHead = cache->lruListTail = NULL;
10
    } else if (entry == cache->lruListHead) {
11
    /*欲删除节点位于表头*/
12
        cache->lruListHead = entry->lruListNext;
13
        cache->lruListHead->lruListPrev = NULL;
14
    } else if (entry == cache->lruListTail) {
15
    /*欲删除节点位于表尾*/
16
        cache->lruListTail = entry->lruListPrev;
17
        cache->lruListTail->lruListNext = NULL;
18
    } else {
19
    /*其他非表头表尾情况，直接摘抄节点*/
20
        entry->lruListPrev->lruListNext = entry->lruListNext;
21
        entry->lruListNext->lruListPrev = entry->lruListPrev;
22
    }
23
    /*删除成功，链表节点数减1*/
24
    cache->lruListSize--;
25
}
26
27
/* 将节点插入到链表表头 */ 
28
static cacheEntryS * insertToListHead(LRUCacheS *cache, cacheEntryS *entry) 
29
{
30
    cacheEntryS *removedEntry = NULL;
31
    if (++cache->lruListSize > cache->cacheCapacity) {
32
    /* 如果缓存满了，即链表当前节点数已等于缓存容量，那么需要先删除链表表尾节点，即淘汰最久没有被访问到的缓存数据单元*/
33
        removedEntry = cache->lruListTail;
34
        removeFromList(cache, cache->lruListTail);   
35
    }
36
    if (cache->lruListHead==NULL&&cache->lruListTail==NULL) {
37
    /*如果当前链表为空链表*/
38
            cache->lruListHead = cache->lruListTail = entry;
39
    } else {
40
    /*当前链表非空，插入表头*/
41
            entry->lruListNext = cache->lruListHead;
42
            entry->lruListPrev = NULL;
43
            cache->lruListHead->lruListPrev = entry;
44
            cache->lruListHead = entry;
45
    }
46
    return removedEntry;
47
}
48
49
/*辅助性接口，用于保证最近访问的节点总是位于链表表头*/
50
static void updateLRUList(LRUCacheS *cache, cacheEntryS *entry) 
51
{
52
    /*将节点从链表中摘抄*/
53
    removeFromList(cache, entry);
54
    /*将节点插入链表表头*/
55
    insertToListHead(cache, entry);
56
}

哈希表相关接口实现

1
/*哈希函数*/
2
static int hashKey(LRUCacheS *cache, char key)
3
{
4
    return (int)key%cache->cacheCapacity;
5
}
6
/*从哈希表获取缓存单元*/
7
static cacheEntryS *getValueFromHashMap(LRUCacheS *cache, int key) {
8
    /*1.使用函数函数定位数据存放在哪个槽*/
9
    cacheEntryS *entry = cache->hashMap[hashKey(cache,key)];
10
    /*2.遍历查询槽内链表，找到准确的数据项*/
11
    while (entry) {
12
        if (entry->key == key)
13
            break;
14
        entry = entry->hashListNext;
15
    }
16
    return entry;
17
}
18
/*向哈希表插入缓存单元*/
19
static void insertentryToHashMap(LRUCacheS *cache, cacheEntryS *entry) 
20
{
21
     /*1.使用函数函数定位数据存放在哪个槽*/
22
    cacheEntryS *n = cache->hashMap[hashKey(cache, entry->key)];
23
    if (n!=NULL) {
24
    /*2.如果槽内已有其他数据项，将槽内数据项与当前欲加入数据项链成链表，当前欲加入数据项为表头*/
25
       entry->hashListNext = n;
26
       n->hashListPrev = entry;
27
    }
28
    /*3.将数据项放入加入哈希槽内*/
29
    cache->hashMap[hashKey(cache,entry->key)] = entry;
30
}
31
/*从哈希表删除缓存单元*/
32
static void removeEntryFromHashMap(LRUCacheS *cache, cacheEntryS *entry) 
33
{
34
    /*无需做任何删除操作的情况*/
35
    if (NULL==entry || NULL==cache || NULL==cache->hashMap) return ;
36
    /*1.使用函数函数定位数据存放在哪个槽*/
37
    cacheEntryS *n = cache->hashMap[hashKey(cache,entry->key)];
38
    /*2.遍历槽内链表，找到欲删除节点，将节点从哈希表摘除*/
39
    while (n) {
40
        if (n->key==entry->key) {/*找到欲删除节点，将节点从哈希表摘抄*/
41
            if (n->hashListPrev) {
42
                n->hashListPrev->hashListNext = n->hashListNext;
43
            } else {
44
                cache->hashMap[hashKey(cache, entry->key)] = n->hashListNext;
45
            }
46
            if (n->hashListNext)
47
                n->hashListNext->hashListPrev = n->hashListPrev;
48
            return ;
49
        }
50
        n = n->hashListNext;
51
    }
52
}
53
`

LRU相关接口实现

1
/*将数据放入LRU缓存中*/
2
int LRUCacheSet(void *lruCache, char key, char data)
3
{
4
    LRUCacheS *cache = (LRUCacheS *)lruCache;
5
    /*从哈希表查找数据是否已经在缓存中*/
6
    cacheEntryS *entry = getValueFromHashMap(cache, key);
7
    if (entry!=NULL) {/*数据已经在缓存中*/
8
    /*更新数据，将该数据项更新至链表表头*/
9
        entry->data = data;
10
        updateLRUList(cache, entry);
11
    } else {
12
    /*数据没在缓存中*/
13
       /*新建缓存单元*/
14
       entry = newCacheEntry(key, data);
15
       /*将新建缓存单元插入链表表头*/
16
       cacheEntryS *removedEntry = insertToListHead(cache, entry);
17
       if (NULL != removedEntry) {
18
       /*将新建缓存单元插入链表表头过程中，发生缓存满了的情况，需要淘汰最久没有被访问到的缓存数据单元*/
19
           removeEntryFromHashMap(cache, removedEntry);     
20
           freeCacheEntry(removedEntry);
21
       }
22
       /*将新建缓存单元插入哈希表*/
23
       insertentryToHashMap(cache, entry);
24
    }    
25
    return 0;
26
}
27
/*从缓存中获取数据*/
28
char LRUCacheGet(void *lruCache, char key)
29
{
30
    LRUCacheS *cache = (LRUCacheS *)lruCache;
31
    /*从哈希表查找数据是否已经在缓存中*/
32
    cacheEntryS *entry = getValueFromHashMap(cache,key);
33
    if (NULL != entry) {
34
        /*缓存中存在该数据，更新至链表表头*/
35
        updateLRUList(cache, entry);
36
        /*返回数据*/
37
        return entry->data;
38
    } else {
39
        /*缓存中不存在相关数据*/
40
        return '\0';
41
    }
42
}