听说今日头条面试很喜欢问这个

LRU Cache 原理

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

LRU Cache 实现

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

C++ 实现

/*************************************************************************
	> 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