实现一个简便的 LRUCache 和 LFUCache

本文主要是介绍了 LruCache 和 LFUCache，以及对应的简单实现，阅读时长大约 8 分钟

文章分为2个部分：

1、LRUCache

概述

简易实现

2、LFUCache

概述

简易实现：

1、LRUCache

概述

在 Android 或者 java 开发中， LRUCache 的使用很广泛，Android 中的在 android.util.LruCache 这个类，使用什么的就不展开了，进入里面看可以看到借助了 LinkedHashMap 来实现了 LruCache，类的内容并不多，通过注释可以很快理解，这里不做详细展开。

在 Linux 内核中，页框回收算法( page frame reclaiming algorithm, 简称 PFRA) 采取从用户态进程和内核告诉缓存“窃取”页框的办法补充伙伴系统的空闲块列表，PFRA必须处理多种属于用户态进程、次盘高速缓存和内存高速缓存的页，它的执行有三种基本情形：

内存紧缺回收
睡眠回收
周期回收

实际上，在用完所有空闲内存之前，就必须执行 PFRA，否则内核很可能陷入一种内存请求的僵局中，严重会导致系统崩溃，而 PFRA 的目标之一就是保存最少的空闲页框池以便内核可以安全地从“内存紧缺”的情形中恢复过来。对于 PFRA 来说，PFRA 选取的页框肯定不是空闲的（think think ～～），尽管很容易确定回收内存的候选页，但是选择合适的目标页也是需要重点关注的问题。这个时候就引出了 LRU 算法： LRU 算法的主要思想就是用一个计数器来存放RAM中每一页的页年龄，即上一次访问该页到现在已经过的时间，这个计数器可使PFRA只回收任何进程的最旧页，但是一些处理器并不支持这样的功能，因此，Linux 使用每页表项中的访问标志位，即（最近最少使用）LRU 链表。

属于进程用户态地址空间或页高速缓存的所有页被分成两组：活动链表与非活动链表。它们被统称为 LRU 链表。前面一个链表用于存放最近被访问过的页，后面的则存放有一段时间没有被访问过的页，显然，页必须从非活动链表中窃取。页的活动链表和非活动链表是 PFRA 的核心数据结构，这两个双向链表（敲黑板，双向链表～～）的头分别存放在每个 zone 描述符的 active_list 和 inactive_list 字段，看名字就可以看出来了，而该描述符的 nr_activie 和 nr_inactive 字段表示存放在两个链表中的页数。最后，有一个字段，叫 lru_lock ，这是一个自旋锁 （自旋锁可以看看jvm的），主要是保护两个链表免受并发访问。那么，如果页属于LRU链表，则设置页描述符中的 PG_lru 标志，此外，如果页属于活动链表，则设置 PG_active 标志，如果属于非活动链表，则清PG_active 标志。页描述符的 lru 字段存放指向 LRU 链表中下一个元素和前一个元素的指针。

因此，PFRA 要做的还有就是在 LRU 链表之间移动页，如下：

如上，当内核必须把一个页标记为访问过时，就调用 mark_page_accessed() 函数，PFRA扫描一页调用一次page_referenced() 函数，而 refill_inactivie_zone() 函数由 shrink_zone() 调用，而shrink_zone()函数对页高速缓存和用户态地址空间进行页回收。

可见，LRUCache 在 Android 以及操作系统中都有着很广泛的用途。

简易实现

上面做了一个简单的概述，那么，要实现一个 LRUCache，包含 get 和 set 方法，并且要求这两个方法的时间复杂度都是 O(1)，可以怎么做呢？

实现的方式有很多种，下面的代码主要是使用了双向链表：

首先，脑海里先浮现一副结构图：

图中包含了头节点 head 和尾节点 tail，中间是有限数量的节点，对于这些节点可以做 get 和 set 操作，接着，根据这幅结构图，先思考几种常规操作以及边界条件：

a、get 和 set 操作需要怎么做？

b、get 和 set 有没有共同的操作？

c、如果超出了容量要怎么操作？

好了，接下来就是具体的实现：

首先定义一个节点的头文件，如下：

Node.h

#ifndef NODE_H#define NODE_H// 定义一个节点 Nodestruct Node {public:    int key;    int val;    Node *pre;    Node *next;    Node(int key, int val) : key(key), val(val), pre(nullptr), next(nullptr) {    }};#endif

接着定义一个 LruCache 的头文件，如下：

LruCache.h

#ifndef LRUCACHE_H#define LRUCACHE_H#include #include "Node.h"class LruCache {private:    int capacity; // 定义容量protected:    std::unordered_map map; // 用于存储 put 传入 的 key 和 对应生成的 Node 节点    Node *head, *tail;public:    LruCache(int capacity);    int get(int key);    void put(int key, int val);    void appendHead(Node *node);    void removeTail();    void deleteNode(Node *node);};#endif

最后实现LruCache头文件里面的逻辑，相应注释写在代码里面，如下：

LruCache.cpp

#include "LruCache.h"// 初始化构造方法LruCache::LruCache(int capacity) {    this->capacity = capacity;    // 初始化容量    head = new Node(-1, -1);      // 初始化头节点    tail = new Node(-1, -1);      // 初始化尾节点    head->next = tail;            // 头节点的 next 指向尾节点    tail->pre = head;             // 尾节点的 next 指向头节点}int LruCache::get(int key) {    if (map.find(key) == map.end())   // 如果找不到对应的key则返回 -1        return -1;    Node *temp = map.find(key)->second;    deleteNode(temp);                 // 删除访问到的节点的位置，因为要重新将它插入到头节点后面    appendHead(temp);                 // 访问的节点插入到头节点后面    return temp->val;}void LruCache::put(int key, int val) {    if (map.find(key) != map.end()) {  // 如果已经有对应节点，更新key的值，并将节点插入到头节点后面        Node *temp = map.find(key)->second;        temp->val = val;        map[key] = temp;        deleteNode(temp);        appendHead(temp);        return;    }    Node *temp = new Node(key, val);    if (map.size() == capacity) {     // 超出 capacity 删除尾节点        map.erase(map.find(tail->pre->key));        removeTail();    }    map.insert(std::make_pair(key, temp));    appendHead(temp);}void LruCache::appendHead(Node *node) {  // 将指定节点插入到头节点后面    node->next = head->next;    head->next->pre = node;    head->next = node;    node->pre = head;}void LruCache::removeTail() {      // 删除尾部节点    tail->pre->pre->next = tail;    tail->pre = tail->pre->pre;}void LruCache::deleteNode(Node *node) {    // 删除指定节点    node->next->pre = node->pre;    node->pre->next = node->next;}

最后来运行下下面代码的效果：

int main() {    LruCache *lruCache = new LruCache(2);    lruCache->put(1, 1);    lruCache->put(2, 2);    cout << lruCache->get(2) << endl;    lruCache->put(3, 3);    lruCache->put(3, 2);    cout << lruCache->get(3) << endl;    cout << lruCache->get(1) << endl;    return 0;}/** * 结果： * 2 * 2 * -1 * */

上面并没有添加哨兵节点，如果需要也可以增加。

总体来说，LruCache 很简单，思路和实现都不难，主要是需要考虑到每次 get 和 put 操作的时候都需要将对应节点插入到头节点后面即可。上面使用 C++ 实现了一遍，没有涉及到什么语法糖，用 java 或者 kotlin 都是可以很快写出来的。简单的整体设计好了，后面各种花样变化就可以慢慢添加。

贴一个java的实现：

public class LRUCache {    private int capacity;    private Map map = new HashMap<>();    private Node head, tail;    public LRUCache(int capacity) {        this.capacity = capacity;        head = new Node(-1, -1);        tail = new Node(-1, -1);        head.next = tail;        tail.pre = head;    }    public int get(int key) {        if (!map.containsKey(key))            return -1;        Node temp = map.get(key);        temp.next.pre = temp.pre;        temp.pre.next = temp.next;        appendHead(temp);        return temp.val;    }    public void put(int key, int value) {        if (map.containsKey(key)) {            Node temp = map.get(key);            temp.val = value;            map.put(key, temp);            temp.next.pre = temp.pre;            temp.pre.next = temp.next;            appendHead(temp);            return;        }        Node newNode = new Node(key, value);        if (map.size() == capacity) {            map.remove(tail.pre.key);            removeTail();        }        map.put(key, newNode);        appendHead(newNode);    }    private void removeTail() {        tail.pre.pre.next = tail;        tail.pre = tail.pre.pre;    }    private void appendHead(Node node) {        head.next.pre = node;        node.next = head.next;        head.next = node;        node.pre = head;    }    class Node {        int key;        int val;        Node pre;        Node next;        Node(int key, int val) {            this.key = key;            this.val = val;            pre = null;            next = null;        }    }}

2、LFUCache

概述

相对 LRUCache，LruCache 是基于访问时间，而LFU(Least Frequently Used) 是基于访问频率，即超过容量之后最先淘汰使用次数最少的，当然，LFU是一种称为最不常用的缓存的缓存逐出算法，不过，对于两者来说，LRU 以及 LFU都属于堆栈型替换算法（堆栈型替换算法的特点：随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降），可以看看这篇论文，内容挺多的：https://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-358.pdf

简易实现：

那么，如何实现一个简易的LFUCache呢，由于LFUCache是基于次数的，所以需要考虑用次数来作为key，首先，同样需要在脑海里有一幅图：

当然，依然需要考虑这几个问题：

a、get 和 set 操作需要怎么做？

b、get 和 set 有没有共同的操作？

c、如果超出了容量要怎么操作？

最后就是代码了，注释写在代码里面了，同样，实现LFUCache有很多种方法，这里提供了一种

public class LFUCache {    private static final int DEFAULT_CAPACITY = 16; // 默认容量    private Map nodeMap = new HashMap<>();    private Map> freq_list_map = new HashMap<>();    private int mCapacity;    private int minFreq; // 最少访问次数    public static void main(String[] args) {        LFUCache lfuCache = new LFUCache(0);        lfuCache.put(0, 0);        lfuCache.get(0);       // do get or set action    }    // 创建内部类 Node    class Node {        int key;        int value;        int freq;        Node(int key, int value, int freq) {            this.key = key;            this.value = value;            this.freq = freq;        }    }    // 赋值默认容量    public LFUCache(){        this.mCapacity = DEFAULT_CAPACITY;    }        // 外部传递容量    public LFUCache(int capacity) {        this.mCapacity = capacity;    }    public int get(int key) {         // 边界条件        if (!nodeMap.containsKey(key) || mCapacity <= 0)            return -1;        Node result = nodeMap.get(key);        int fre = result.freq; // 获取访问次数        freq_list_map.get(fre).remove(result); // 删除掉访问节点，因为后面还要再加上        if (freq_list_map.get(fre).isEmpty()) {  // 如果以 frep为key的链表已经空了，则可以删掉了            freq_list_map.remove(fre); // 做删除操作            if (fre == minFreq) { // 更新最小的 freq，即访问次数                minFreq++;            }        }        // 如果不包含以 fre + 1 开头的链表，新建一个，并存储进去        if (!freq_list_map.containsKey(fre + 1)) {            freq_list_map.put(fre + 1, new LinkedList());        }        freq_list_map.get(fre + 1).add(result);        result.freq += 1;        return result.value;    }    public void put(int key, int value) {        if (mCapacity <= 0)            return;        if (nodeMap.containsKey(key)) {            nodeMap.get(key).value = value;            get(key);            return;        }        // 到达容量上限制，删除最少次数的表头元素        if (nodeMap.size() == mCapacity) {            Node n = freq_list_map.get(minFreq).pollFirst();            if (freq_list_map.get(minFreq).isEmpty()) {                freq_list_map.remove(minFreq);            }            nodeMap.remove(n.key);        }                // 插入新元素，第一次插入，次数是 1        minFreq= 1;        if (!freq_list_map.containsKey(minFreq)) {            freq_list_map.put(minFreq, new LinkedList<>());        }        Node nn = new Node(key, value, 1);        freq_list_map.get(minFreq).add(nn);        nodeMap.put(key, nn);    }}

上面就是LFUCache的简易实现，可以稍微思考下，为什么Android里面一些缓存都是LRUCache而不是LFUCache呢，很简单，因为我们时常用的数据都是最新的，比如从网络或者数据库拉取的数据，对于次数并没有什么要求，当然，这两者孰优孰劣，实际要看具体场景，比如堆栈型替换算法，两者的命中率可能不同场景各有优势。

好了，本文到此告一段落，希望对各位有一点点帮助，文章如有不对，欢迎批评指正，Thanks ~~

1、LRUCache

概述

简易实现

2、LFUCache

概述

简易实现：

更多相关文章

随机推荐