简单的LRU Cache设计与实现

时间:2023-01-26 04:52:07
要求:
设计并实现一个LRU缓存的数据结构,支持get和set操作

get(key):若缓存中存在key,返回对应的value,否则返回-1

set(key,value):若缓存中存在key,替换其value,否则插入key及其value,如果插入时缓存已经满了,应该使用LRU算法把最近最久没有使用的key踢出缓存。

设计1:

cache使用数组,每个key再关联一个时间戳,时间戳可以直接用个long long类型表示,在cache中维护一个最大的时间戳:

  • get的时候把key的时间戳变为最大时间戳+1
  • set的时候,数据从前往后存储
    如果key存在,更新key的时间戳为当前cache中最大的时间戳+1,并更新value;
    如果key不存在,
                     若缓存满,在整个缓存中查找时间戳最小的key,其存储位置作为新key的存储位置,设置key的时间戳为最大时间戳+1
                     若缓存未满,设置key的时间戳为最大时间戳+1,存储位置为第一个空闲位置

分析下时间空间复杂度,get的时候,需要从前往后找key,时间为O(N),set的时候,也要从前往后找key,当缓存满的时候,还得找到时间戳最小的key,时间复杂度为O(N)。除了缓存本身,并没有使用其他空间,空间复杂度为O(1)。 这个速度显然是比较慢的,随着数据量的增大,get和set速度越来越慢。可能有人会想到用哈希表作为底层存储,这样get的时间复杂度确实可以减低为O(1),set的时候,只要缓存没有满,也可以在O(1)的时间完,但在缓存满的时候,依然需要每次遍历找时间戳最小的key,时间复杂度还是O(N)。

设计2:

cache底层使用单链表,同时用一个哈希表存储每个key对应的链表结点的前驱结点,并记录链表尾结点的key

  • get时,从哈希表中找到key对应的链表结点,挪到链表头,更新指向尾结点的key
  • set时,如果key存在,那么找到链表结点,并挪到链表头,更新指向尾结点的key
              如果key不存在,
                                  若缓存满,重用链表尾结点,设置新key和value,并挪到链表头,更新指向尾结点的key
                              若缓存未满,直接插入结点到链表头,若是第一结点,更新指向尾结点的key

get,set时间复杂度O(1),总的空间复杂度O(N)。比前面的设计好一点。下面的再来看下关于设计2的两个实现

实现1,自定义链表

为了方便链表的插入与删除,使用了带头结点head的链表,所以真正有效的第一个结点是head->next。另外,只是简单的实现,没有容错,不支持并发,简单的内存管理

ps. 用双向链表来实现会简单写,这里用单链表和哈希表共同实现了双向链表的功效,也就是哈希除了用来查找,还指示了key对应的结点的前驱结点。

struct Node{
    int _key;
    int _value;
    Node* _next;
    Node(int key,int value,Node* next):_key(key),_value(value),_next(next){}
};

class LRUCache{
public:
    LRUCache(int capacity) {
        _capacity   = capacity;
        _size       = 0;
        _last       = 0;
        _cur_begin  = _begin = (char *) malloc(sizeof(Node)*(capacity+1));
        _head       = new (_cur_begin) Node(0,0,NULL);//在指定内存上构造对象
        _cur_begin += sizeof(Node);
    }

    ~LRUCache(){
        if(_begin!=NULL){
            while(_cur_begin > _begin){
                _cur_begin -= sizeof(Node);
                ((Node*)_cur_begin)->~Node();//先释放内存上的对象
            }
            free(_begin);//再释放内存
        }
    }

    int get(int key) {

        int value             = -1;//初始时假设key对应的结点不存在

        Node* pre_node_of_key = umap_prenodes[key];//key对应的结点的前驱结点

        if(pre_node_of_key !=NULL){//key结点存在

            Node* node             = pre_node_of_key->_next;//key对应的结点
            pre_node_of_key->_next = node->_next;
            if(pre_node_of_key->_next!=NULL){
                umap_prenodes[pre_node_of_key->_next->_key] = pre_node_of_key;
            }

            node->_next            = _head->_next;
            if(node->_next!=NULL){//node有后继,更新后继的前驱结点
                umap_prenodes[node->_next->_key] = node;
            }

            _head->_next           = node;
            umap_prenodes[key]     = _head;              

            /*更新_last*/
            if(_last == key ){
                _last = ( pre_node_of_key == _head ? key : pre_node_of_key->_key ); 
            }

            value = node->_value;
        }
        return value;
    }

    void set(int key, int value) {
        Node* node            = NULL;
        Node* pre_node_of_key = umap_prenodes[key];//key对应的结点的前驱结点

        if(pre_node_of_key != NULL){//key对应的结点存在,孤立key对应的结点,也就是从链表中把结点取出来,重新链接链表

            node                   = pre_node_of_key->_next;//key对应的结点
            pre_node_of_key->_next = node->_next;

            if(pre_node_of_key->_next!=NULL){
                umap_prenodes[pre_node_of_key->_next->_key] = pre_node_of_key;//更新前驱
            }

            node->_value           = value; //重置结点值

            /*更新_last*/
            if(_last == key ){
                _last = ( pre_node_of_key == _head ? key : pre_node_of_key->_key ); 
            }
        }else{//结点不存在

            if(_capacity == 0){//缓冲区为空
                return ;
            }

            if(_size == _capacity){//缓存满,重用最后一个结点

                Node* pre_node_of_last    = umap_prenodes[_last];//最后一个结点的前驱结点

                umap_prenodes[pre_node_of_last->_next->_key] = NULL;
                
                node                      = new (pre_node_of_last->_next) Node(key,value,NULL);//重用最后一个结点

                pre_node_of_last->_next   = NULL;//移出最后一个结点

                _last = ( pre_node_of_last == _head ? key : pre_node_of_last->_key ); //更新指向最后一个结点的key

            }else{//缓冲未满,使用新结点

                node    = new (_cur_begin) Node(key,value,NULL);
                _cur_begin += sizeof(Node);
                _size++;
                if(_size==1){
                    _last = key;
                }
            }
        }

        /*把node插入到第一个结点的位置*/
        node->_next            = _head->_next;
        if(node->_next!=NULL){//node有后继,更新后继的前驱结点
            umap_prenodes[node->_next->_key] = node;
        }
        _head->_next           = node;
        umap_prenodes[key]     = _head;  

    }

private:
    int   _size;
    int   _capacity;
    int   _last;//_last是链表中最后一个结点的key
    Node* _head;
    unordered_map<int,Node*> umap_prenodes;//存储key对应的结点的前驱结点,链表中第一个结点的前驱结点为_head
    
    char* _begin;//缓存的起始位置 
    char* _cur_begin;//用于分配结点内存的起始位置
};

实现2,使用stl的list

这个版本的实现来自LeetCode discuss

class LRUCache{
    size_t m_capacity;
    unordered_map<int,  list<pair<int, int>>::iterator> m_map; //m_map_iter->first: key, m_map_iter->second: list iterator;
    list<pair<int, int>> m_list;                               //m_list_iter->first: key, m_list_iter->second: value;
public:
    LRUCache(size_t capacity):m_capacity(capacity) {
    }
    int get(int key) {
        auto found_iter = m_map.find(key);
        if (found_iter == m_map.end()) //key doesn't exist
            return -1;
        m_list.splice(m_list.begin(), m_list, found_iter->second); //move the node corresponding to key to front
        return found_iter->second->second;                         //return value of the node
    }
    void set(int key, int value) {
        auto found_iter = m_map.find(key);
        if (found_iter != m_map.end()) //key exists
        {
            m_list.splice(m_list.begin(), m_list, found_iter->second); //move the node corresponding to key to front
            found_iter->second->second = value;                        //update value of the node
            return;
        }
        if (m_map.size() == m_capacity) //reached capacity
        {
           int key_to_del = m_list.back().first; 
           m_list.pop_back();            //remove node in list;
           m_map.erase(key_to_del);      //remove key in map
        }
        m_list.emplace_front(key, value);  //create new node in list
        m_map[key] = m_list.begin();       //create correspondence between key and node
    }
};

通过两个版本的实现,可以看到,使用stl的容器代码非常简洁,但也不是说自定义链表版本的实现就不好,如果从并发的角度来说,自定义的结构,在实现并发时,锁的粒度会小一点,而直接使用stl容器,锁的粒度为大一点,因为,使用stl,必须锁定一个函数,而使用自定义结构可以只锁定某个函数内部的某些操作,而且更方便实现无锁并发。另外,从leetcode的测试结果来看,这两个版本的性能差不多。