MMKV中的简单LRU缓存(LRUCache)

MMKV中的简单LRU缓存(LRUCache)

LRU（Least recently used）是一种缓存更新策略，即当缓存数目达到最大容量、或者某个条件时，移除掉最近最少使用的元素。微信前不久开源了一个客户端Key-Value存储库MMKV https://github.com/Tencent/MMKV ，其中实现了这样一个十分精简的LRU缓存（LRUCache类）。

LRUCache实现原理介绍

  • 使用链表记录所有元素（key和value）。

  • 使用哈希表记录key和链表的位置，用于快速判断元素是否已经包含。

  • 加入新元素，在链表的头部添加。

  • 访问一个元素，则移动到链表的头部。

  • 若数量超过最大容量，则删除链表的结尾。

下面是代码及注释。

MMKV的实现

代码就贴这里，相信看一遍就很容易明白

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// 链表
#import <list>
// 无序map
#import <unordered_map>
// key和value类型
template <typename Key_t, typename Value_t>
class LRUCache {
    // 最大元素个数
    size_t m_capacity;
    // 链表存储pair
    std::list<std::pair<Key_t, Value_t>> m_list;
    // 记录key和指向链表的iterator（迭代器，类似指针）
    std::unordered_map<Key_t, typename decltype(m_list)::iterator> m_map;
public:
    LRUCache(size_t capacity) : m_capacity(capacity) {}
    // 当前占用的大小
    size_t size() const { return m_map.size(); }
    // 空间最大
    size_t capacity() const { return m_capacity; }
    // 是否包含某个key
    bool contains(const Key_t &key) const { return m_map.find(key) != m_map.end(); }
    // 清空
    void clear() {
        m_list.clear();
        m_map.clear();
    }
    // 添加
    void insert(const Key_t &key, const Value_t &value) {
        // 是否已经添加过key
        auto itr = m_map.find(key);
        if (itr != m_map.end()) {
            // 添加过
            // 则把这个元素移动到链表的最开始(iter->second移动到begin)
            m_list.splice(m_list.begin(), m_list, itr->second);
            // 覆盖key的新value
            itr->second->second = value;
        } else {
            // 是否满了
            if (m_map.size() == m_capacity) {
                // 满了（超过了设定的最大空间）
                // 移除掉链表的最后一项
                // 跟进最后一个key移除掉map中的项
                m_map.erase(m_list.back().first);
                // 移除掉链表的最后一项
                m_list.pop_back();
            }
            // 没有满
            // 链表最开始添加
            m_list.push_front(std::make_pair(key, value));
            // 加入map
            m_map.insert(std::make_pair(key, m_list.begin()));
        }
    }
    // 获取
    Value_t *get(const Key_t &key) {
        // 查找
        auto itr = m_map.find(key);
        if (itr != m_map.end()) {
            // 找到了
            // 移动找到的项目到链表最开始(iter->second存储了指向当前项目在链表中的迭代器)
            m_list.splice(m_list.begin(), m_list, itr->second);
            return &itr->second->second;
        }
        return nullptr;
    }
    // 遍历每一项
    void forEach(std::function<void(Key_t&,Value_t&)> callback){
        for(auto & item : m_list){
            callback(item.first,item.second);
        }
    }
};

增加打印方法

上面增加了一个打印所有元素的辅助方法forEach

1
2
3
4
5
void forEach(std::function<void(Key_t&,Value_t&)> callback){
    for(auto & item : m_list){
        callback(item.first,item.second);
    }
}

传入一个lambda表达式就可以打印了。

测试例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LRUCache<string, int> cache(5);
cache.insert("a",1);
cache.insert("b",2);
cache.insert("c",3);
cache.insert("d",4);
cache.insert("e",5);
cache.forEach([](string& key,int& value){
    NSLog(@"%s - %d",key.c_str(),value);
});
NSLog(@">> after insert 6");
cache.insert("f",6);
cache.forEach([](string& key,int& value){
    NSLog(@"%s - %d",key.c_str(),value);
});
NSLog(@">> after get d");
cache.get("d");
cache.forEach([](string& key,int& value){
    NSLog(@"%s - %d",key.c_str(),value);
});

输出如下：

其他缓存策略

https://en.wikipedia.org/wiki/Cache_replacement_policies

参考

https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)
LeetCode 中就有个类似的题目 https://leetcode.com/problems/lru-cache/description/ 可以练习一下。