LRU缓存算法

文章目录

1、什么是缓存

这里说的缓存是一种广义的概念,在计算机存储层次结构中,低一层的存储器都可以看做是高一层的缓存。比如Cache是内存的缓存,内存是硬盘的缓存,硬盘是网络的缓存等等。

缓存可以有效地解决存储器性能与容量的这对矛盾,但绝非看上去那么简单。如果缓存算法设计不当,非但不能提高访问速度,反而会使系统变得更慢。

从本质上来说,缓存之所以有效是因为程序和数据的局部性(locality)。程序会按固定的顺序执行,数据会存放在连续的内存空间并反复读写。这些特点使得我们可以缓存那些经常用到的数据,从而提高读写速度。

缓存的大小是固定的,它应该只保存最常被访问的那些数据。然而未来不可预知,我们只能从过去的访问序列做预测,于是就有了各种各样的缓存替换策略。本文介绍一种简单的缓存策略,称为最近最少使用(LRU,Least Recently Used)算法。

2、LRU的实现

我们以内存访问为例解释缓存的工作原理。假设缓存的大小固定,初始状态为空。每发生一次读内存操作,首先查找待读取的数据是否存在于缓存中,若是,则缓存命中,返回数据;若否,则缓存未命中,从内存中读取数据,并把该数据添加到缓存中。向缓存添加数据时,如果缓存已满,则需要删除访问时间最早的那条数据,这种更新缓存的方法就叫做LRU。

实现LRU时,我们需要关注它的读性能和写性能,理想的LRU应该可以在O(1)的时间内读取一条数据或更新一条数据,也就是说读写的时间复杂度都是O(1)。

此时很容易想到使用HashMap,根据数据的键访问数据可以达到O(1)的速度。但是更新缓存的速度却无法达到O(1),因为需要确定哪一条数据的访问时间最早,这需要遍历所有缓存才能找到。

因此,我们需要一种既按访问时间排序,又能在常数时间内随机访问的数据结构。

这可以通过HashMap+双向链表实现。HashMap保证通过key访问数据的时间为O(1),双向链表则按照访问时间的顺序依次穿过每个数据。之所以选择双向链表而不是单链表,是为了可以从中间任意结点修改链表结构,而不必从头结点开始遍历。

如下图所示,黑色部分为HashMap的结构,红色箭头则是双向链表的正向连接(逆向连接未画出)。可以清晰地看到,数据的访问顺序是1->3->5->6->10。我们只需要在每次访问过后改变链表的连接顺序即可。
LRU缓存算法

3、代码

leetcode 146. LRU 缓存机制

leetcode 146. LRU 缓存机制
设计和实现一个 LRU (最近最少使用) 缓存机制 ,实现 LRUCache 类:

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
    int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
  • void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

提示:

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示:

1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 104
最多调用 3 * 104 次 get 和 put

代码:

/* 题目要求O(1)完成查询和插入,需要使用hash链表,而C语言优秀库uthash底层本身就是用双向链表实现的hash
 * 至于题目中说的当达到容量时,先删除最久未使用的数据,这个最久未使用就在双向链表的表头,可以自己写一些add测试下
 * 综上分析,无需一个 表示使用次数的变量,而是利用uthash底层的数据结构就可以实现
 */
typedef struct {
    int key;
    int val;
    UT_hash_handle hh;
} LRUCache;

LRUCache *g_usr = NULL;
int g_size;

LRUCache* lRUCacheCreate(int capacity) {
    g_size = capacity;
    return g_usr;
}

int lRUCacheGet(LRUCache* obj, int key) {
    LRUCache *cur_usr = NULL;
    HASH_FIND_INT(g_usr, &key, cur_usr);
    if (cur_usr != NULL) { // get存在的key,则该key被使用了一次,因此需要先删后入,满足LRU
        HASH_DEL(g_usr, cur_usr);
        HASH_ADD_INT(g_usr, key, cur_usr);
        return cur_usr->val;
    }
    return -1;
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    LRUCache *cur_usr = NULL, *next_usr = NULL;
    HASH_FIND_INT(g_usr, &key, cur_usr);
    if (cur_usr != NULL) {
        HASH_DEL(g_usr, cur_usr);
        cur_usr->key = key;
        cur_usr->val = value;
        HASH_ADD_INT(g_usr, key, cur_usr);
    } else { // 新插入
        int cnt = HASH_COUNT(g_usr);
        if (cnt == g_size) {
            HASH_ITER(hh, g_usr, cur_usr, next_usr) {
                HASH_DEL(g_usr, cur_usr);
                free(cur_usr);
                break;
            }
        }
        LRUCache *new_usr = (LRUCache *)malloc(sizeof(LRUCache));
        new_usr->key = key;
        new_usr->val = value;
        HASH_ADD_INT(g_usr, key, new_usr);
    }
    return;
}

void lRUCacheFree(LRUCache* obj) {
    LRUCache *cur_usr = NULL, *next_usr = NULL;
    HASH_ITER(hh, g_usr, cur_usr, next_usr) {
        HASH_DEL(g_usr, cur_usr);
        free(cur_usr);
    }
}

/**
 * Your LRUCache struct will be instantiated and called as such:
 * LRUCache* obj = lRUCacheCreate(capacity);
 * int param_1 = lRUCacheGet(obj, key);
 * lRUCachePut(obj, key, value);
 * lRUCacheFree(obj);
*/
上一篇:【死磕 Java 基础】 — 自己动手实现一个 LRU


下一篇:leetcode#146. LRU 缓存机制