用哈希表和和双向链表的代码模板实现LRU

字数统计: 1.9k字 | 阅读时长: 9分

2022-11-26

摘要: 实现LRU

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 LRU：维护最近访问/插入的元素中，我们基于 C++ STL 以及 Python OrderedDict 实现了 LRU 的插入和查询。在文章 LFU：维护最频繁访问的元素中我们基于 C++ STL 实现了 LFU 的插入和查询。本文我们基于 CloseHashTable 和 DoubleCircleList 实现 LRU。

在文章 OrderedDict：维护插入顺序的有序字典中，我们已经基于 CloseHashTable 和 DoubleCircleList 实现了 OrderedDict 的增删改查，在实现 LRU 和 LFU 的时候也可以借鉴，其中 LRU 比较简单，只需要在 OrderedDict 基础上做少量修改。

LRU 的增删改查实现要点

146. LRU 缓存

LRU 的增删改查操作，以及实现要点，这里做个复习。

put(key, value)

1
2
3

step1: 更新哈希表中的 (key, value)
step2: 新建 list 节点，并插入到表头，如果此时链表满，删除 list 尾节点在哈希表中对应的 key，删除尾节点并将尾指针指向下一个尾节点。
step3: 将新建 list 节点的指针更新到哈希表对应的 key

get(key)

1 2	step1. 查哈希表，得到值 value 和对应的链表节点的指针 iter step2. 用 iter 和链表的删除和插入操作将对应的链表节点调度到表头

remove(key)

1
2
3

step1. 查哈希表找到 key 对应的节点，得到值 value 和对应的链表节点的指针 iter
step2. 删除 iter 对应的链表节点
step3. 删除哈希表节点

LRU 在 OrderedDict 基础上的变化

与带插入顺序的有序字典 OrderedDict 相比，有两点变化：

put 中如果达到 capacity 需要删除链表的尾部节点及其对应的哈希表节点。
get 时，如果有值，则需要将对应的链表节点调度到表头。

代码 (C++，模板)

其中对 put 的修改中需要修改哈希表中的值，用引用接收哈希表的 findx 的返回值对后续的修改比较方便 ValueType &v = mapping.findx(key);，需要将模板里的返回类型改一下。

其余部分继承 OrderedDict 即可。包括删除 remove(key)，以及 remove_bottom。

#include <iostream>

using namespace std;

typedef int DLType;
const DLType DLTypeNULL = -1;
const int MAX_LEN = 1e6;
struct DLNode
{
    DLType val;
    DLNode *next;
    DLNode *prev;
    DLNode(DLType x) : val(x), next(nullptr), prev(nullptr) {}
};

class DoubleCircleList
{
private:
    // head 一直指向 dummy
    // tail 在空表时指向 dummy，否则指向 head 的前一个节点
    DLNode *head, *tail;
    int length;
    int capacity;

public:
    DoubleCircleList(int N=MAX_LEN)
    {
        head = new DLNode(0);
        head -> next = head;
        head -> prev = head;
        tail = head;
        length = 0;
        capacity = N;
    }

    bool removeHead()
    {
        if(isEmpty())
            return false;
        remove(get_head());
        return true;
    }

    bool removeTail()
    {
        if(isEmpty())
            return false;
        remove(get_tail());
        return true;
    }

    DLType getHead() const
    {
        if(isEmpty())
            return DLTypeNULL;
        return get_head() -> val;
    }

    DLType getTail() const
    {
        if(isEmpty())
            return DLTypeNULL;
        return get_tail() -> val;
    }

    DLNode* insertHead(DLType val)
    {
        if(isFull())
            return nullptr;
        return insert(head, val);
    }

    DLNode* insertTail(DLType val)
    {
        if(isFull())
            return nullptr;
        return insert(tail, val);
    }

    DLNode* insert(DLNode *pos, DLType val)
    {
        if(!pos || isFull())
            return nullptr;
        DLNode *cur = new DLNode(val);
        cur -> next = pos -> next;
        cur -> prev = pos;
        pos -> next -> prev = cur;
        pos -> next = cur;
        if(tail == pos)
            tail = cur;
        ++length;
        return cur;
    }

    DLType get(DLNode *pos) const
    {
        if(!pos || is_dummy(pos))
            return DLTypeNULL;
        return pos -> val;
    }

    DLNode* remove(DLNode *pos)
    {
        if(!pos || is_dummy(pos) || isEmpty())
            return nullptr;
        if(tail == pos)
            tail = tail -> prev;
        --length;
        pos -> prev -> next = pos -> next;
        pos -> next -> prev = pos -> prev;
        DLNode *result = pos -> next;
        delete pos;
        pos = nullptr;
        if(isEmpty())
            return nullptr;
        if(is_dummy(result))
            result = result -> next;
        return result;
    }

    bool change(DLNode* pos, DLType val)
    {
        if(!pos || is_dummy(pos))
            return false;
        pos -> val = val;
        return true;
    }

    DLNode* get_next(DLNode *pos) const
    {
        if(isEmpty())
            return nullptr;
        if(is_tail(pos))
            return get_head();
        return pos -> next;
    }

    DLNode* get_prev(DLNode *pos) const
    {
        if(isEmpty())
            return nullptr;
        if(is_head(pos))
            return get_tail();
        return pos -> prev;
    }

    bool is_dummy(DLNode *pos) const
    {
        return pos == head;
    }

    bool is_head(DLNode *pos) const
    {
        return (!isEmpty() && pos == head -> next);
    }

    bool is_tail(DLNode *pos) const
    {
        return (!isEmpty() && pos == tail);
    }

    DLNode* get_tail() const
    {
        if(isEmpty())
            return nullptr;
        return tail;
    }

    DLNode* get_head() const
    {
        if(isEmpty())
            return nullptr;
        return head -> next;
    }


    bool isEmpty() const
    {
        return head == tail;
    }

    int size() const
    {
        return length;
    }

    bool isFull() const
    {
        return length >= capacity;
    }

    void traverse() const
    {
        auto iter = head -> next;
        while(iter != head)
        {
            cout << iter -> val << " ";
            iter = iter -> next;
        }
        cout << endl;
    }
};


const int INF = 1e9;
typedef int hashType;
struct ValueType
{
    int value;
    DLNode *list_node;
    ValueType(int v=-1, DLNode *node=nullptr):value(v),list_node(node){}
    bool operator==(const ValueType& v) const
    {
        return value == v.value && list_node == v.list_node;
    }
    bool operator!=(const ValueType& v) const
    {
        return !(*this == v);
    }
};
ValueType VALUENULL = ValueType(-1, nullptr);

class CloseHashTable
{
private:
    struct Node
    {
        hashType data;
        ValueType item;
        int state;
        // 0: Empty  -1: deleted
        // >0: cnt / active
        Node()
        {
            state = 0;
        }
    };

    Node *arraytable;
    int sizetable;
    int (*key)(const hashType& x); // 将 key 变成一个整数，如果 key 本身是整数直接返回
    const double A = 0.6180339887;

    static int defaultKey(const int &k)
    {
        return k;
    }

    int hash1(const hashType& x) const
    {
        if(key(x) < 0)
            return key(x) % sizetable;
        return (key(x) + INF) % sizetable;
    }

    int hash2(const hashType& x) const
    {
        double d;
        if(key(x) < 0)
            d = (key(x) + INF) * A;
        else
            d = (key(x)) * A;
        return (int)(sizetable * (d - (int)d));
    }

public:
    CloseHashTable(int length=20011, int (*f)(const hashType &x)=defaultKey)
    {
        sizetable = length;
        arraytable = new Node[sizetable];
        key = f;
    }

    ~CloseHashTable()
    {
        delete [] arraytable;
    }

    ValueType& findx(const hashType& x) const;
    bool insertx(const hashType& x, const ValueType& v);
    bool removex(const hashType& x);
};

ValueType& CloseHashTable::findx(const hashType &x) const
{
    int initPos = hash2(x);
    int pos = initPos;

    do
    {
        if(arraytable[pos].state == 0)
            return VALUENULL;
        if(arraytable[pos].state > 0 && key(arraytable[pos].data) == key(x))
            return arraytable[pos].item;
        pos = (pos + 1) % sizetable;
    }while(pos != initPos);

    return VALUENULL;
}

bool CloseHashTable::insertx(const hashType& x, const ValueType& v)
{
    int initPos = hash2(x);
    int pos = initPos;

    do{
        if(arraytable[pos].state <= 0)
        {
            arraytable[pos].data = x;
            arraytable[pos].item = v;
            arraytable[pos].state = 1;
            return true;
        }
        else if(arraytable[pos].state > 0 && key(arraytable[pos].data) == key(x))
        {
            // 有重映射将用新值覆盖 item 改为将新值插入 items
            arraytable[pos].item = v;
            return true;
        }
        pos = (pos + 1) % sizetable;
    }while(pos != initPos);

    return false;
}

bool CloseHashTable::removex(const hashType &x)
{
    int initPos = hash2(x);
    int pos = initPos;

    do
    {
        if(arraytable[pos].state == 0)
            return false;
        if(arraytable[pos].state > 0 && key(arraytable[pos].data) == key(x))
        {
            // 有重映射改为将节点下的所有 item 删掉，将 arraytable[pos].state 改为 -1 后返回
            arraytable[pos].state = -1;
            return true;
        }
        pos = (pos + 1) % sizetable;
    }while(pos != initPos);

    return false;
}

class OrderedDict
{
public:
    OrderedDict()
    {
        linkedlist = DoubleCircleList();
        CloseHashTable mapping(hashtable_capacity);
    }

    ~OrderedDict(){}

    void put(int key, int value)
    {
        ValueType v = mapping.findx(key);
        if(v != VALUENULL)
        {
            DLNode *node = v.list_node;
            linkedlist.remove(node);
            mapping.removex(key);
        }
        DLNode *node = linkedlist.insertHead(key);
        mapping.insertx(key, ValueType(value, node));
    }

    int get(int key) const
    {
        ValueType v = mapping.findx(key);
        if(v == VALUENULL)
            return -1;
        else
            return v.value;
    }

    int remove(int key)
    {
        ValueType v = mapping.findx(key);
        if(v != VALUENULL)
        {
            DLNode *node = v.list_node;
            linkedlist.remove(node);
            mapping.removex(key);
            return v.value;
        }
        else
            return -1;
    }

    int remove_bottom()
    {
        int key = linkedlist.getTail();
        ValueType v = mapping.findx(key);
        if(v != VALUENULL)
        {
            // DLNode *node = v.list_node;
            // linkedlist.remove(node);
            linkedlist.removeTail();
            mapping.removex(key);
            return v.value;
        }
        else
            return -1;
    }

    int size() const
    {
        return linkedlist.size();
    }

    void traverse() const
    {
        DLNode *head = linkedlist.get_head();
        DLNode *iter = head;
        do{
            cout << iter -> val << " " << mapping.findx(iter -> val).value << "; ";
            iter = linkedlist.get_next(iter);
        }
        while(iter != head);
        cout << endl;
    }

protected:
    const int hashtable_capacity = 99991;
    DoubleCircleList linkedlist;
    CloseHashTable mapping;
};


class LRUCache : public OrderedDict
{
public:
    LRUCache(int capacity):capacity(capacity){}

    int get(int key)
    {
        ValueType &v = mapping.findx(key);
        if(v == VALUENULL)
            return -1;
        else
        {
            DLNode *node = v.list_node;
            DLNode *new_node = linkedlist.insertHead(key);
            linkedlist.remove(node);
            v.list_node = new_node;
            return v.value;
        }
    }

    void put(int key, int value)
    {
        ValueType v = mapping.findx(key);
        if(v != VALUENULL)
        {
            linkedlist.remove(v.list_node);
            mapping.removex(key);
        }
        if(linkedlist.size() == capacity)
            remove_bottom();
        DLNode *node = linkedlist.insertHead(key);
        mapping.insertx(key, ValueType(value, node));
    }

private:
    int capacity;
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法数据结构

用哈希表和和双向链表的代码模板实现LRU

LRU 的增删改查实现要点

LRU 在 OrderedDict 基础上的变化

代码 (C++，模板)