LRU Cache 解析及实现

发表于 | 更新于: | 分类于 |

LRU Cache 原理

LRU是Least Recently Used 的缩写，是一种缓存替换算法，当系统中的缓存满时，通过删除最近最少使用的元素来填充新的内容。LRU 算法在操作系统中有广泛应用，如CPU与物理内存之间的Cache替换算法， 物理内存与硬盘之间Cache替换算法。

LRU Cache 实现

我们可以使用一个双向链表和hash map 实现LRU Cache，其中hash map 存储缓存的内容，hash map 的value 存储指向双向链表节点的指针，双向链表存储缓存的内容，当有节点被加入时，该节点放到双向列表的头部，当访问已经存在的节点时，把该节点移动到双向链表头部，当双向链表满时，删除双向链表最后一个元素。简单的讲，双向链表的作用是记录缓存内容的使用顺序。

C++ 实现

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
/*************************************************************************
	> File Name: lru_cache_template.hpp
	> Author: ce39906
	> Mail: ce39906@163.com
	> Created Time: 2018-04-02 16:44:58
 ************************************************************************/
#ifndef LRU_CACHE_TEMPLATE_HPP
#define LRU_CACHE_TEMPLATE_HPP
#include <unordered_map>

template <class Key,class Value>
struct Node
{
    Node(Key k,Value v) :
        key(k), value(v), prev(NULL), next(NULL)
    {
    }

    Node()
    {
    }

    Key key;
    Value value;
    Node* prev;
    Node* next;
};

template <class Key, class Value>
class LruCache
{
  public:

    LruCache(int capacity) :
        size_(0), capacity_(capacity)
    {
        head = new Node<Key,Value>;
        tail = new Node<Key,Value>;
        head->next = tail;
        head->prev = NULL;
        tail->next = NULL;
        tail->prev = head;
        container_.clear();
    };

    ~LruCache()
    {
        while(head)
        {
            Node<Key,Value>* temp = head->next;
            delete head;
            head = temp;
        }
    };

    void Put(Key key ,Value value)
    {
        //insert
        if (container_.find(key) == container_.end())
        {
            //not full
            if (size_ != capacity_)
            {
                Node<Key,Value>* data = new Node<Key,Value>(key,value);
                attach(data);
                container_.insert(std::make_pair(key,data));
                size_++;
            }
            else
            {
                Node<Key,Value>* temp = tail->prev;
                container_.erase(temp->key);
                detach(temp);
                if (temp)
                    delete temp;
                Node<Key,Value>* data = new Node<Key,Value>(key,value);
                attach(data);
                container_.insert(std::make_pair(key,data));
            }
        }
        else //update
        {
            Node<Key,Value>* data = container_[key];
            detach(data);
            if (data)
                delete data;
            data = new Node<Key,Value>(key,value);
            container_[key] = data;
            attach(data);
        }
    }

    Value Get(Key key)
    {
        //find
        if (container_.find(key) != container_.end())
        {
            Node<Key,Value>* data = container_[key];
            detach(data);
            attach(data);
            return data->value;
        }
        else // not find
        {
            return Value();
        }
    }

  private:

    int size_;
    int capacity_;
    std::unordered_map<Key,Node<Key,Value>*> container_;
    Node<Key,Value>* head;
    Node<Key,Value>* tail;

    void attach(Node<Key,Value>* node)
    {
        Node<Key,Value>* temp = head->next;
        head->next = node;
        node->next = temp;
        node->prev = head;
        temp->prev = node;
    }

    void detach(Node<Key,Value>* node)
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
};

#endif
Donate
0%