LRU缓存设计

Question

最近最少使用（LRU）缓存是先丢弃最近最少使用的项 如何设计和实现这样一个缓存类？设计要求如下：

1）尽快找到该项目

2）一旦缓存未命中且缓存已满，我们需要尽快替换最近最少使用的项目。

如何从设计模式和算法设计角度来分析和实现这个问题？

Answer 1

链表 + 指向链表节点的指针的哈希表是实现 LRU 缓存的常用方法。这提供了 O(1) 操作（假设散列不错）。这样做的优点（O(1)）：您可以通过锁定整个结构来实现多线程版本。您不必担心粒度锁定等问题。

简单地说，它的工作方式是：

在访问值时，将链表中的相应节点移动到头部。

当需要从缓存中删除一个值时，可以从尾部删除。

当你向缓存添加一个值时，只需将它放在链表的头部即可。

感谢 doublep，这里有一个 C++ 实现的网站：杂项容器模板。

Answer 2

这是我的 LRU 缓存的简单 C++ 实现示例，结合了哈希（unordered_map）和列表。列表上的项目有访问映射的键，地图上的项目有列表的迭代器来访问列表。

#include <list>
#include <unordered_map>
#include <assert.h>

using namespace std;

template <class KEY_T, class VAL_T> class LRUCache{
private:
        list< pair<KEY_T,VAL_T> > item_list;
        unordered_map<KEY_T, decltype(item_list.begin()) > item_map;
        size_t cache_size;
private:
        void clean(void){
                while(item_map.size()>cache_size){
                        auto last_it = item_list.end(); last_it --;
                        item_map.erase(last_it->first);
                        item_list.pop_back();
                }
        };
public:
        LRUCache(int cache_size_):cache_size(cache_size_){
                ;
        };

        void put(const KEY_T &key, const VAL_T &val){
                auto it = item_map.find(key);
                if(it != item_map.end()){
                        item_list.erase(it->second);
                        item_map.erase(it);
                }
                item_list.push_front(make_pair(key,val));
                item_map.insert(make_pair(key, item_list.begin()));
                clean();
        };
        bool exist(const KEY_T &key){
                return (item_map.count(key)>0);
        };
        VAL_T get(const KEY_T &key){
                assert(exist(key));
                auto it = item_map.find(key);
                item_list.splice(item_list.begin(), item_list, it->second);
                return it->second->second;
        };

};

Answer 3

我在这里看到了一些不必要的复杂实现，因此我决定也提供我的实现。缓存只有两个方法，get和set。希望它具有更好的可读性和理解性：

#include<unordered_map>
#include<list>

using namespace std;

template<typename K, typename V = K>
class LRUCache
{

private:
    list<K>items;
    unordered_map <K, pair<V, typename list<K>::iterator>> keyValuesMap;
    int csize;

public:
    LRUCache(int s) :csize(s) {
        if (csize < 1)
            csize = 10;
    }

    void set(const K key, const V value) {
        auto pos = keyValuesMap.find(key);
        if (pos == keyValuesMap.end()) {
            items.push_front(key);
            keyValuesMap[key] = { value, items.begin() };
            if (keyValuesMap.size() > csize) {
                keyValuesMap.erase(items.back());
                items.pop_back();
            }
        }
        else {
            items.erase(pos->second.second);
            items.push_front(key);
            keyValuesMap[key] = { value, items.begin() };
        }
    }

    bool get(const K key, V &value) {
        auto pos = keyValuesMap.find(key);
        if (pos == keyValuesMap.end())
            return false;
        items.erase(pos->second.second);
        items.push_front(key);
        keyValuesMap[key] = { pos->second.first, items.begin() };
        value = pos->second.first;
        return true;
    }
};

Answer 4

这是我的一个基本、简单的 LRU 缓存的实现。

//LRU Cache
#include <cassert>
#include <list>

template <typename K,
          typename V
          >
class LRUCache
    {
    // Key access history, most recent at back
    typedef std::list<K> List;

    // Key to value and key history iterator
    typedef unordered_map< K,
                           std::pair<
                                     V,
                                     typename std::list<K>::iterator
                                    >
                         > Cache;

    typedef V (*Fn)(const K&);

public:
    LRUCache( size_t aCapacity, Fn aFn ) 
        : mFn( aFn )
        , mCapacity( aCapacity )
        {}

    //get value for key aKey
    V operator()( const K& aKey )
        {
        typename Cache::iterator it = mCache.find( aKey );
        if( it == mCache.end() ) //cache-miss: did not find the key
            {
            V v = mFn( aKey );
            insert( aKey, v );
            return v;
            }

        // cache-hit
        // Update access record by moving accessed key to back of the list
        mList.splice( mList.end(), mList, (it)->second.second );

        // return the retrieved value
        return (it)->second.first;
        }

private:
        // insert a new key-value pair in the cache
    void insert( const K& aKey, V aValue )
        {
        //method should be called only when cache-miss happens
        assert( mCache.find( aKey ) == mCache.end() );

        // make space if necessary
        if( mList.size() == mCapacity )
            {
            evict();
            }

        // record k as most-recently-used key
        typename std::list<K>::iterator it = mList.insert( mList.end(), aKey );

        // create key-value entry, linked to the usage record
        mCache.insert( std::make_pair( aKey, std::make_pair( aValue, it ) ) );
        }

        //Purge the least-recently used element in the cache
    void evict()
        {
        assert( !mList.empty() );

        // identify least-recently-used key
        const typename Cache::iterator it = mCache.find( mList.front() );

        //erase both elements to completely purge record
        mCache.erase( it );
        mList.pop_front();
        }

private:
    List mList;
    Cache mCache;
    Fn mFn;
    size_t mCapacity;
    };

Answer 5

两年前我实现了一个线程安全的 LRU 缓存。

LRU 通常使用 HashMap 和 LinkedList 来实现。你可以谷歌一下实现细节。有很多关于它的资源（维基百科也有很好的解释）。

为了线程安全，每当修改 LRU 的状态时都需要加锁。

我将我的C++代码贴在这里供您参考。

这是实现。

/***
    A template thread-safe LRU container.

    Typically LRU cache is implemented using a doubly linked list and a hash map.
    Doubly Linked List is used to store list of pages with most recently used page
    at the start of the list. So, as more pages are added to the list,
    least recently used pages are moved to the end of the list with page
    at tail being the least recently used page in the list.

    Additionally, this LRU provides time-to-live feature. Each entry has an expiration
    datetime.
***/
#ifndef LRU_CACHE_H
#define LRU_CACHE_H

#include <iostream>
#include <list>

#include <boost/unordered_map.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/make_shared.hpp>
#include <boost/date_time/posix_time/posix_time.hpp>
#include <boost/thread/mutex.hpp>

template <typename KeyType, typename ValueType>
  class LRUCache {
 private:
  typedef boost::posix_time::ptime DateTime;

  // Cache-entry
  struct ListItem {
  ListItem(const KeyType &key,
           const ValueType &value,
           const DateTime &expiration_datetime)
  : m_key(key), m_value(value), m_expiration_datetime(expiration_datetime){}
    KeyType m_key;
    ValueType m_value;
    DateTime m_expiration_datetime;
  };

  typedef boost::shared_ptr<ListItem> ListItemPtr;
  typedef std::list<ListItemPtr> LruList;
  typedef typename std::list<ListItemPtr>::iterator LruListPos;
  typedef boost::unordered_map<KeyType, LruListPos> LruMapper;

  // A mutext to ensuare thread-safety.
  boost::mutex m_cache_mutex;

  // Maximum number of entries.
  std::size_t m_capacity;

  // Stores cache-entries from latest to oldest.
  LruList m_list;

  // Mapper for key to list-position.
  LruMapper m_mapper;

  // Default time-to-live being add to entry every time we touch it.
  unsigned long m_ttl_in_seconds;

  /***
      Note : This is a helper function whose function call need to be wrapped
      within a lock. It returns true/false whether key exists and
      not expires. Delete the expired entry if necessary.
  ***/
  bool containsKeyHelper(const KeyType &key) {
    bool has_key(m_mapper.count(key) != 0);
    if (has_key) {
      LruListPos pos = m_mapper[key];
      ListItemPtr & cur_item_ptr = *pos;

      // Remove the entry if key expires
      if (isDateTimeExpired(cur_item_ptr->m_expiration_datetime)) {
        has_key = false;
        m_list.erase(pos);
        m_mapper.erase(key);
      }
    }
    return has_key;
  }

  /***
      Locate an item in list by key, and move it at the front of the list,
      which means make it the latest item.
      Note : This is a helper function whose function call need to be wrapped
      within a lock.
  ***/
  void makeEntryTheLatest(const KeyType &key) {
    if (m_mapper.count(key)) {
      // Add original item at the front of the list,
      // and update <Key, ListPosition> mapper.
      LruListPos original_list_position = m_mapper[key];
      const ListItemPtr & cur_item_ptr = *original_list_position;
      m_list.push_front(cur_item_ptr);
      m_mapper[key] = m_list.begin();

      // Don't forget to update its expiration datetime.
      m_list.front()->m_expiration_datetime = getExpirationDatetime(m_list.front()->m_expiration_datetime);

      // Erase the item at original position.
      m_list.erase(original_list_position);
    }
  }

 public:

  /***
      Cache should have capacity to limit its memory usage.
      We also add time-to-live for each cache entry to expire
      the stale information. By default, ttl is one hour.
  ***/
 LRUCache(std::size_t capacity, unsigned long ttl_in_seconds = 3600)
   : m_capacity(capacity), m_ttl_in_seconds(ttl_in_seconds) {}

  /***
      Return now + time-to-live
  ***/
  DateTime getExpirationDatetime(const DateTime &now) {
    static const boost::posix_time::seconds ttl(m_ttl_in_seconds);
    return now + ttl;
  }

  /***
      If input datetime is older than current datetime,
      then it is expired.
  ***/
  bool isDateTimeExpired(const DateTime &date_time) {
    return date_time < boost::posix_time::second_clock::local_time();
  }

  /***
      Return the number of entries in this cache.
   ***/
  std::size_t size() {
    boost::mutex::scoped_lock lock(m_cache_mutex);
    return m_mapper.size();
  }

  /***
      Get value by key.
      Return true/false whether key exists.
      If key exists, input paramter value will get updated.
  ***/
  bool get(const KeyType &key, ValueType &value) {
    boost::mutex::scoped_lock lock(m_cache_mutex);
    if (!containsKeyHelper(key)) {
      return false;
    } else {
      // Make the entry the latest and update its TTL.
      makeEntryTheLatest(key);

      // Then get its value.
      value = m_list.front()->m_value;
      return true;
    }
  }

  /***
      Add <key, value> pair if no such key exists.
      Otherwise, just update the value of old key.
  ***/
  void put(const KeyType &key, const ValueType &value) {
    boost::mutex::scoped_lock lock(m_cache_mutex);
    if (containsKeyHelper(key)) {
      // Make the entry the latest and update its TTL.
      makeEntryTheLatest(key);

      // Now we only need to update its value.
      m_list.front()->m_value = value;
    } else { // Key exists and is not expired.
      if (m_list.size() == m_capacity) {
        KeyType delete_key = m_list.back()->m_key;
        m_list.pop_back();
        m_mapper.erase(delete_key);
      }

      DateTime now = boost::posix_time::second_clock::local_time();
      m_list.push_front(boost::make_shared<ListItem>(key, value,
                                                     getExpirationDatetime(now)));
      m_mapper[key] = m_list.begin();
    }
  }
};
#endif

这是单元测试。

#include "cxx_unit.h"
#include "lru_cache.h"

struct LruCacheTest
  : public FDS::CxxUnit::TestFixture<LruCacheTest>{
  CXXUNIT_TEST_SUITE();
  CXXUNIT_TEST(LruCacheTest, testContainsKey);
  CXXUNIT_TEST(LruCacheTest, testGet);
  CXXUNIT_TEST(LruCacheTest, testPut);
  CXXUNIT_TEST_SUITE_END();

  void testContainsKey();
  void testGet();
  void testPut();
};


void LruCacheTest::testContainsKey() {
  LRUCache<int,std::string> cache(3);
  cache.put(1,"1"); // 1
  cache.put(2,"2"); // 2,1
  cache.put(3,"3"); // 3,2,1
  cache.put(4,"4"); // 4,3,2

  std::string value_holder("");
  CXXUNIT_ASSERT(cache.get(1, value_holder) == false); // 4,3,2
  CXXUNIT_ASSERT(value_holder == "");

  CXXUNIT_ASSERT(cache.get(2, value_holder) == true); // 2,4,3
  CXXUNIT_ASSERT(value_holder == "2");

  cache.put(5,"5"); // 5, 2, 4

  CXXUNIT_ASSERT(cache.get(3, value_holder) == false); // 5, 2, 4
  CXXUNIT_ASSERT(value_holder == "2"); // value_holder is still "2"

  CXXUNIT_ASSERT(cache.get(4, value_holder) == true); // 4, 5, 2
  CXXUNIT_ASSERT(value_holder == "4");

  cache.put(2,"II"); // {2, "II"}, 4, 5

  CXXUNIT_ASSERT(cache.get(2, value_holder) == true); // 2, 4, 5
  CXXUNIT_ASSERT(value_holder == "II");

  // Cache-entries : {2, "II"}, {4, "4"}, {5, "5"}
  CXXUNIT_ASSERT(cache.size() == 3);
  CXXUNIT_ASSERT(cache.get(2, value_holder) == true);
  CXXUNIT_ASSERT(cache.get(4, value_holder) == true);
  CXXUNIT_ASSERT(cache.get(5, value_holder) == true);
}

void LruCacheTest::testGet() {
  LRUCache<int,std::string> cache(3);
  cache.put(1,"1"); // 1
  cache.put(2,"2"); // 2,1
  cache.put(3,"3"); // 3,2,1
  cache.put(4,"4"); // 4,3,2

  std::string value_holder("");
  CXXUNIT_ASSERT(cache.get(1, value_holder) == false); // 4,3,2
  CXXUNIT_ASSERT(value_holder == "");

  CXXUNIT_ASSERT(cache.get(2, value_holder) == true); // 2,4,3
  CXXUNIT_ASSERT(value_holder == "2");

  cache.put(5,"5"); // 5,2,4
  CXXUNIT_ASSERT(cache.get(5, value_holder) == true); // 5,2,4
  CXXUNIT_ASSERT(value_holder == "5");

  CXXUNIT_ASSERT(cache.get(4, value_holder) == true); // 4, 5, 2
  CXXUNIT_ASSERT(value_holder == "4");


  cache.put(2,"II");
  CXXUNIT_ASSERT(cache.get(2, value_holder) == true); // {2 : "II"}, 4, 5
  CXXUNIT_ASSERT(value_holder == "II");

  // Cache-entries : {2, "II"}, {4, "4"}, {5, "5"}
  CXXUNIT_ASSERT(cache.size() == 3);
  CXXUNIT_ASSERT(cache.get(2, value_holder) == true);
  CXXUNIT_ASSERT(cache.get(4, value_holder) == true);
  CXXUNIT_ASSERT(cache.get(5, value_holder) == true);
}

void LruCacheTest::testPut() {
  LRUCache<int,std::string> cache(3);
  cache.put(1,"1"); // 1
  cache.put(2,"2"); // 2,1
  cache.put(3,"3"); // 3,2,1
  cache.put(4,"4"); // 4,3,2
  cache.put(5,"5"); // 5,4,3

  std::string value_holder("");
  CXXUNIT_ASSERT(cache.get(2, value_holder) == false); // 5,4,3
  CXXUNIT_ASSERT(value_holder == "");

  CXXUNIT_ASSERT(cache.get(4, value_holder) == true); // 4,5,3
  CXXUNIT_ASSERT(value_holder == "4");

  cache.put(2,"II");
  CXXUNIT_ASSERT(cache.get(2, value_holder) == true); // II,4,5
  CXXUNIT_ASSERT(value_holder == "II");

  // Cache-entries : {2, "II"}, {4, "4"}, {5, "5"}
  CXXUNIT_ASSERT(cache.size() == 3);
  CXXUNIT_ASSERT(cache.get(2, value_holder) == true);
  CXXUNIT_ASSERT(cache.get(4, value_holder) == true);
  CXXUNIT_ASSERT(cache.get(5, value_holder) == true);
}

CXXUNIT_REGISTER_TEST(LruCacheTest);

Answer 6

是否允许 LRU 近似？这是针对某些图像平滑算法每秒执行 2000 万次获取/设置操作的算法。我不知道它是否不是最糟糕的，但它肯定比 Javascript 更快，后者每秒仅执行 150 万次获取/设置。

Unordered_map 用于跟踪循环缓冲区上的项目。循环缓冲区不会像其他链表版本那样添加/删除节点。因此，它至少应该对 CPU 的 L1/L2/L3 缓存友好，除非缓存大小比这些缓存大得多。算法很简单。有一只时钟指针驱逐受害者槽位，而另一只手确实将其中一些槽位作为“第二次机会”从驱逐中拯救出来，但将驱逐阶段滞后了 50%，因此，如果缓存很大，则缓存项有很长的时间获得第二次机会/免遭驱逐。

由于这是一个近似值，因此您不应期望它总是驱逐最近的一个。但它确实可以加速某些比 RAM 慢的网络 I/O、磁盘读/写等。我在 VRAM 虚拟缓冲区类中使用了它，该类使用 100% 的系统视频 RAM（来自多个显卡）。 VRAM 比 RAM 慢，因此对于某些缓存友好的访问模式，在 RAM 中进行缓存使得 6GB VRAM 看起来与 RAM 一样快。

这是实现：

#ifndef LRUCLOCKCACHE_H_
#define LRUCLOCKCACHE_H_

#include<vector>
#include<algorithm>
#include<unordered_map>
#include<functional>
#include<mutex>
#include<unordered_map>
/* LRU-CLOCK-second-chance implementation */
template<   typename LruKey, typename LruValue>
class LruClockCache
{
public:
    // allocates circular buffers for numElements number of cache slots
    // readMiss:    cache-miss for read operations. User needs to give this function
    //              to let the cache automatically get data from backing-store
    //              example: [&](MyClass key){ return redis.get(key); }
    //              takes a LruKey as key, returns LruValue as value
    // writeMiss:   cache-miss for write operations. User needs to give this function
    //              to let the cache automatically set data to backing-store
    //              example: [&](MyClass key, MyAnotherClass value){ redis.set(key,value); }
    //              takes a LruKey as key and LruValue as value
    LruClockCache(size_t numElements,
                const std::function<LruValue(LruKey)> & readMiss,
                const std::function<void(LruKey,LruValue)> & writeMiss):size(numElements)
    {
        ctr = 0;
        // 50% phase difference between eviction and second-chance hands of the "second-chance" CLOCK algorithm
        ctrEvict = numElements/2;

        loadData=readMiss;
        saveData=writeMiss;

        // initialize circular buffers
        for(size_t i=0;i<numElements;i++)
        {
            valueBuffer.push_back(LruValue());
            chanceToSurviveBuffer.push_back(0);
            isEditedBuffer.push_back(0);
            keyBuffer.push_back(LruKey());
        }
    }

    // get element from cache
    // if cache doesn't find it in circular buffers,
    // then cache gets data from backing-store
    // then returns the result to user
    // then cache is available from RAM on next get/set access with same key
    inline
    const LruValue get(const LruKey & key)  noexcept
    {
        return accessClock2Hand(key,nullptr);
    }

    // thread-safe but slower version of get()
    inline
    const LruValue getThreadSafe(const LruKey & key)  noexcept
    {
        std::lock_guard<std::mutex> lg(mut);
        return accessClock2Hand(key,nullptr);
    }

    // set element to cache
    // if cache doesn't find it in circular buffers,
    // then cache sets data on just cache
    // writing to backing-store only happens when
    //                  another access evicts the cache slot containing this key/value
    //                  or when cache is flushed by flush() method
    // then returns the given value back
    // then cache is available from RAM on next get/set access with same key
    inline
    void set(const LruKey & key, const LruValue & val) noexcept
    {
        accessClock2Hand(key,&val,1);
    }

    // thread-safe but slower version of set()
    inline
    void setThreadSafe(const LruKey & key, const LruValue & val)  noexcept
    {
        std::lock_guard<std::mutex> lg(mut);
        accessClock2Hand(key,&val,1);
    }

    void flush()
    {
        for (auto mp = mapping.cbegin(); mp != mapping.cend() /* not hoisted */; /* no increment */)
        {
          if (isEditedBuffer[mp->second] == 1)
          {
                isEditedBuffer[mp->second]=0;
                auto oldKey = keyBuffer[mp->second];
                auto oldValue = valueBuffer[mp->second];
                saveData(oldKey,oldValue);
                mapping.erase(mp++);    // or "it = m.erase(it)" since C++11
          }
          else
          {
                ++mp;
          }
        }
    }

    // CLOCK algorithm with 2 hand counters (1 for second chance for a cache slot to survive, 1 for eviction of cache slot)
    // opType=0: get
    // opType=1: set
    LruValue const accessClock2Hand(const LruKey & key,const LruValue * value, const bool opType = 0)
    {

        typename std::unordered_map<LruKey,size_t>::iterator it = mapping.find(key);
        if(it!=mapping.end())
        {

            chanceToSurviveBuffer[it->second]=1;
            if(opType == 1)
            {
                isEditedBuffer[it->second]=1;
                valueBuffer[it->second]=*value;
            }
            return valueBuffer[it->second];
        }
        else
        {
            long long ctrFound = -1;
            LruValue oldValue;
            LruKey oldKey;
            while(ctrFound==-1)
            {
                if(chanceToSurviveBuffer[ctr]>0)
                {
                    chanceToSurviveBuffer[ctr]=0;
                }

                ctr++;
                if(ctr>=size)
                {
                    ctr=0;
                }

                if(chanceToSurviveBuffer[ctrEvict]==0)
                {
                    ctrFound=ctrEvict;
                    oldValue = valueBuffer[ctrFound];
                    oldKey = keyBuffer[ctrFound];
                }

                ctrEvict++;
                if(ctrEvict>=size)
                {
                    ctrEvict=0;
                }
            }

            if(isEditedBuffer[ctrFound] == 1)
            {
                // if it is "get"
                if(opType==0)
                {
                    isEditedBuffer[ctrFound]=0;
                }

                saveData(oldKey,oldValue);

                // "get"
                if(opType==0)
                {
                    LruValue loadedData = loadData(key);
                    mapping.erase(keyBuffer[ctrFound]);
                    valueBuffer[ctrFound]=loadedData;
                    chanceToSurviveBuffer[ctrFound]=0;

                    mapping[key]=ctrFound;
                    keyBuffer[ctrFound]=key;

                    return loadedData;
                }
                else /* "set" */
                {
                    mapping.erase(keyBuffer[ctrFound]);


                    valueBuffer[ctrFound]=*value;
                    chanceToSurviveBuffer[ctrFound]=0;


                    mapping[key]=ctrFound;
                    keyBuffer[ctrFound]=key;
                    return *value;
                }
            }
            else // not edited
            {
                // "set"
                if(opType == 1)
                {
                    isEditedBuffer[ctrFound]=1;
                }

                // "get"
                if(opType == 0)
                {
                    LruValue loadedData = loadData(key);
                    mapping.erase(keyBuffer[ctrFound]);
                    valueBuffer[ctrFound]=loadedData;
                    chanceToSurviveBuffer[ctrFound]=0;

                    mapping[key]=ctrFound;
                    keyBuffer[ctrFound]=key;

                    return loadedData;
                }
                else // "set"
                {
                    mapping.erase(keyBuffer[ctrFound]);


                    valueBuffer[ctrFound]=*value;
                    chanceToSurviveBuffer[ctrFound]=0;


                    mapping[key]=ctrFound;
                    keyBuffer[ctrFound]=key;
                    return *value;
                }
            }

        }
    }



private:
    size_t size;
    std::mutex mut;
    std::unordered_map<LruKey,size_t> mapping;
    std::vector<LruValue> valueBuffer;
    std::vector<unsigned char> chanceToSurviveBuffer;
    std::vector<unsigned char> isEditedBuffer;
    std::vector<LruKey> keyBuffer;
    std::function<LruValue(LruKey)> loadData;
    std::function<void(LruKey,LruValue)> saveData;
    size_t ctr;
    size_t ctrEvict;
};



#endif /* LRUCLOCKCACHE_H_ */

这是用法：

using MyKeyType = std::string;
using MyValueType = MinecraftChunk;

LruClockCache<MyKeyType,MyValueType> cache(1024*5,[&](MyKeyType key){ 
  // cache miss (read)
  // access data-store (network, hdd, graphics card, anything that is slower than RAM or higher-latency than RAM-latency x2)
  return readChunkFromHDD(key);
  },[&](MyKeyType key,MyValueType value){ 
  
  // cache miss (write)
  // access data-store
  writeChunkToHDD(key,value);
});

// cache handles all cace-miss functions automatically
MinecraftChunk chunk = cache.get("world coordinates 1500 35 2000");

// cache handles all cace-miss functions automatically
cache.set("world coordinates 1502 35 1999",chunk);

cache.flush(); // clears all pending-writes in the cache and writes to backing-store

Answer 7

我在此处实现了 LRU。该接口遵循 std::map 所以它应该不难使用。此外，您还可以提供自定义备份处理程序，当数据在缓存中失效时使用该处理程序。

sweet::Cache<std::string,std::vector<int>, 48> c1;
c1.insert("key1", std::vector<int>());
c1.insert("key2", std::vector<int>());
assert(c1.contains("key1"));

Answer 8

Java代码：

package DataStructures;

import java.util.HashMap;

class Node2 {
    
    int key;
    int value;
    Node2 pre;
    Node2 next;
    
    Node2(int key ,int value)
    {
        this.key=key;
        this.value=value;
    }
}
class LRUCache {

    private HashMap<Integer,Node2> lrumap;
    private int capacity;
    private Node2 head,tail;
    
    LRUCache(int capacity)
    {
        this.capacity=capacity;
        lrumap=new HashMap<Integer,Node2>();
        head=null;
        tail=null;
        }
    
    public void deleteNode(Node2 node)
    {
        
        if(node==head)
        {
            head.next.pre=null;
            head=head.next;
            node=null;          
        }
        else if(node==tail)
        {
            tail.pre.next=null;
            tail=tail.pre;
            node=null;          
        }
        else
        {
            node.pre.next=node.next;
            node.next.pre=node.pre;
            node=null;
        }
    }
    
    public void addToHead(Node2 node)
    {
        if(head==null && tail==null)
        {
            head=node;
            tail=node;
        }
        else
        {
        node.next=head;
        head.pre=node;
        head=node;
        }
        
    }
    
    public int get(int key)
    {
        if(lrumap.containsKey(key))
        {
            Node2 gnode=lrumap.get(key);
            int result=gnode.value;
            deleteNode(gnode);
            addToHead(gnode);
            
            return result;
        }
        
        return -1;
    }
    
    public void set(int key,int value)
    {
        if(lrumap.containsKey(key))
        {
            Node2 snode=lrumap.get(key);
            snode.value=value;
            deleteNode(snode);
            addToHead(snode);
        }
        else
        {
            Node2 node=new Node2(key,value);
            //System.out.println("mapsize="+lrumap.size()+"   capacity="+capacity);
            if(lrumap.size()>=capacity)
            {
            System.out.println("remove="+tail.key);
                lrumap.remove(tail.key);
                deleteNode(tail);
            
            }
            lrumap.put(key, node);
            addToHead(node);
            
        }
    }
    
    public void show()
    {
        Node2 node = head;
        
        while(node.next!=null)
        {   
        System.out.print("["+node.key+","+node.value+"]--");
        node=node.next;
        }
        System.out.print("["+node.key+","+node.value+"]--");
        System.out.println();
    }
    
    
}


public class LRUCacheDS{
    

    public static void main(String[] args) {
        
        LRUCache lr= new LRUCache(4);
        lr.set(4,8);
        lr.set(2,28);
        lr.set(6,38);
        lr.show();
        lr.set(14,48);
        lr.show();
        lr.set(84,58);
        lr.show();
        lr.set(84,34);
        lr.show();
        lr.get(6);
        System.out.println("---------------------------------------------------------");
        lr.show();
        
    }
}

Answer 9

我们必须创建一个数据结构，使我们能够
同时优化所有三个主要操作。

根据上图，我们可以推断：

• 对于一般情况，使用树是最佳选择。

• 如果我们知道缓存的大小足够大（并且新元素的插入不频繁），则哈希表将是最佳选择
  足够），很少需要删除最旧的条目。

• 如果删除旧条目比存储条目或查找缓存元素更重要，则链表可能是一个有效的选项：但在
  这种情况下，缓存基本上就没用了，加上它就可以了
  没有提供任何好处。

• 在所有情况下，存储 n 个条目所需的内存都是 O(n)。

现在我最喜欢的问题是，我们能做得更好吗？

单个数据结构可能不足以构建最多
有效解决问题。一方面我们有数据
特别适合快速存储和存储的结构
检索条目。哈希表几乎不可能被击败，如果
这就是游戏。另一方面，当哈希表
当涉及到维持事物的秩序时，它们就不是很好了
涉及检索它们包含的最小（或最大）元素，
但我们还有其他结构可以很好地处理这个问题。根据
我们想要保持的秩序，我们可能需要树木，或者我们
列表可能没问题。

我们只需要保持缓存条目的顺序，就可以
从最少使用到最近使用。由于订单仅
根据插入时间，新元素不会改变顺序
较旧的元素；因此，我们不需要任何花哨的东西：我们只需要
需要一个支持 FIFO 的结构。我们可以只使用一个列表或一个
队列。当我们不知道情况时，链表通常是最好的选择
提前我们必须存储的元素数量或者可以的数量
动态变化，而队列通常使用
数组（因此维​​度更静态），但针对插入进行了优化
头部去除，尾部去除。

链接列表还可以支持在其末端快速插入/删除。我们
然而，需要一个双向链表，我们可以在其中插入元素
前面并从尾部取出它们。通过始终保持指向
尾部以及从每个节点到其前任节点的链接，我们可以实现
在 O(1) 时间内去除尾部。

您可以看到为缓存存储的三个数据元素
每次操作后都需要更新：

(1) 哈希表。

(2) 双向链表的头。

(3) 指向列表中最后一个元素的指针。

注意哈希表中的每个元素如何指向
存储所有数据的列表。要从列表条目获取
对应的哈希条目，我们必须对公司名称进行哈希处理
存储在节点中，这是表的键。

我们分别考虑了哈希表和链表，但是我们
需要让他们同步工作。我们可能会存储很多
缓存中的大对象，我们绝对不想重复
它们在两种数据结构中。避免重复的一种方法是存储
仅在其中一个结构中的条目并从以下位置引用它们
另一个。我们可以将条目添加到哈希表中，然后
将哈希表的密钥存储在另一个 DS 中，反之亦然。

现在，我们需要决定哪个数据结构应该保存值并
哪一个应该留下参考。最好的选择是拥有
哈希表条目存储指向链表节点的指针，并且具有
后者存储实际值。 （如果我们做相反的事情，那么方法
我们从链表节点链接到哈希表条目将被捆绑
到哈希表的实现。它可能是一个开放索引
如果我们使用链接，则寻址或指针。该耦合至
实施既不是好的设计，也常常是不可能的，就像你一样
通常无法访问标准库内部）。

此缓存称为最近最少使用。这不仅仅是最近
额外。这意味着排序不仅仅基于我们第一次的时间
添加一个元素到缓存，但最后一次访问它。

• 当我们向缓存添加一个新条目时，如果发生缓存未命中，尝试访问不在缓存中的元素，我们只需添加一个
  链接列表前面的新条目。

• 但是当我们遇到缓存命中，访问确实存储在缓存中的元素时，我们需要移动现有的列表元素
  到列表的前面，我们只有在以下情况下才能有效地做到这一点：
  都可以在常量中检索（我们仍然需要包括时间
  计算我们查找的条目的每个哈希值。）计时一个指向
  现有条目的链表节点（可以是任何地方
  据我们所知，在列表中），并从列表中删除一个元素
  恒定时间（同样，我们需要一个双向链表；
  基于数组的队列实现，在中间删除
  队列需要线性时间）。

• 如果缓存已满，我们需要先删除最近最少使用的条目，然后才能添加新条目。在这种情况下，删除的方法
  最旧的条目可以访问常量链表的尾部
  时间，我们从中恢复要删除的条目。要将其定位在
  哈希表并从中删除它，我们需要对条目进行哈希处理（或
  它的 ID）需要额外的费用（可能是非常量的：对于字符串，它
  将取决于字符串的长度）。

参考

Answer 10

缓存是不是像哈希表一样支持按键检索值的数据结构？ LRU 意味着缓存有一定的大小限制，我们需要定期删除最少使用的条目。

如果你用链表+指针哈希表来实现，你怎么能通过键来进行 O(1) 检索值呢？

我将使用哈希表实现 LRU 缓存，其中每个条目的值是 value + 指向上一个/下一个条目的指针。

关于多线程访问，我更喜欢监视读写锁（最好通过自旋锁实现，因为争用通常很快）。

Answer 11

LRU页面替换技术：

当一个页面被引用时，所需的页面可能在缓存中。

如果在缓存中：我们需要将其放到缓存队列的前面。

如果不在缓存中：我们将其放入缓存中。简单来说，我们将一个新页面添加到缓存队列的前面。如果缓存满了，即所有帧都满了，我们从缓存队列的后面删除一个页面，并将新页面添加到缓存队列的前面。

# Cache Size
csize = int(input())

# Sequence of pages 
pages = list(map(int,input().split()))

# Take a cache list
cache=[]

# Keep track of number of elements in cache
n=0

# Count Page Fault
fault=0

for page in pages:
    # If page exists in cache
    if page in cache:
        # Move the page to front as it is most recent page
        # First remove from cache and then append at front
        cache.remove(page)
        cache.append(page)
    else:
        # Cache is full
        if(n==csize):
            # Remove the least recent page 
            cache.pop(0)
        else:
            # Increment element count in cache
            n=n+1

        # Page not exist in cache => Page Fault
        fault += 1
        cache.append(page)

print("Page Fault:",fault)

输入/输出

Input:
3
1 2 3 4 1 2 5 1 2 3 4 5

Output:
Page Fault: 10

Answer 12

这是我的简单 Java 程序员，复杂度为 O(1)。

//

package com.chase.digital.mystack;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {

  private int size;
  private Map<String, Map<String, Integer>> cache = new HashMap<>();

  public LRUCache(int size) {
    this.size = size;
  }

  public void addToCache(String key, String value) {
    if (cache.size() < size) {
      Map<String, Integer> valueMap = new HashMap<>();
      valueMap.put(value, 0);
      cache.put(key, valueMap);
    } else {
      findLRUAndAdd(key, value);
    }
  }


  public String getFromCache(String key) {
    String returnValue = null;
    if (cache.get(key) == null) {
      return null;
    } else {
      Map<String, Integer> value = cache.get(key);
      for (String s : value.keySet()) {
        value.put(s, value.get(s) + 1);
        returnValue = s;
      }
    }
    return returnValue;
  }

  private void findLRUAndAdd(String key, String value) {
    String leastRecentUsedKey = null;
    int lastUsedValue = 500000;
    for (String s : cache.keySet()) {
      final Map<String, Integer> stringIntegerMap = cache.get(s);
      for (String s1 : stringIntegerMap.keySet()) {
        final Integer integer = stringIntegerMap.get(s1);
        if (integer < lastUsedValue) {
          lastUsedValue = integer;
          leastRecentUsedKey = s;
        }
      }
    }
    cache.remove(leastRecentUsedKey);
    Map<String, Integer> valueMap = new HashMap<>();
    valueMap.put(value, 0);
    cache.put(key, valueMap);
  }


}

Answer 13

详细说明请参见我的博文。

class LRUCache {
  constructor(capacity) {
    
        this.head = null;
        this.tail = null;
        this.capacity = capacity;
        this.count = 0;
    this.hashMap  = new Map();    
  }
 
  get(key) {
    var node = this.hashMap.get(key);
    if(node) {
      if(node == this.head) {
        // node is already at the head, just return the value
        return node.val;
      }      
      if(this.tail == node && this.tail.prev) {
        // if the node is at the tail,
        // set tail to the previous node if it exists.
        this.tail = this.tail.prev;
        this.tail.next = null;
      }
      // link neibouring nodes together
      if(node.prev)
        node.prev.next = node.next;
      if(node.next)
        node.next.prev = node.prev;      
      // add the new head node
      node.prev = null;
      node.next = this.head;
      this.head.prev = node;
      this.head = node;
      return node.val;
    }
    return -1;
  }
  put(key, val) {
    this.count ++;
    var newNode = { key, val, prev: null, next: null };
    if(this.head == null) {
      // this.hashMap is empty creating new node
      this.head =  newNode;
      this.tail = newNode;
    }
    else {
      var oldNode = this.hashMap.get(key);
      if(oldNode) {
        // if node with the same key exists, 
        // clear prev and next pointers before deleting the node.
        if(oldNode.next) {
          if(oldNode.prev)
            oldNode.next.prev = oldNode.prev;
          else
            this.head = oldNode.next;
        }
        if(oldNode.prev) {          
          oldNode.prev.next = oldNode.next;
          if(oldNode == this.tail)
            this.tail = oldNode.prev;
        }
        // removing the node
        this.hashMap.delete(key);
        this.count --;        
      }
      // adding the new node and set up the pointers to it's neibouring nodes      
      var currentHead = this.head;
      currentHead.prev = newNode;        
      newNode.next = currentHead;
      this.head = newNode;
      if(this.tail == null)
        this.tail = currentHead;
      if(this.count == this.capacity + 1) {
        // remove last nove if over capacity
        var lastNode = this.tail;
        this.tail = lastNode.prev;
        if(!this.tail) {
          //debugger;
        }
        this.tail.next = null;
        this.hashMap.delete(lastNode.key);
        this.count --;
      }
    }
    this.hashMap.set(key, newNode);
    return null;
  }
}

var cache = new LRUCache(3);
cache.put(1,1); // 1
cache.put(2,2); // 2,1
cache.put(3,3); // 3,2,1

console.log( cache.get(2) ); // 2,3,1
console.log( cache.get(1) ); // 1,2,3
cache.put(4,4);              // 4,1,2 evicts 3
console.log( cache.get(3) ); // 3 is no longer in cache

Answer 14

LRU 缓存的工作

首先丢弃最近最少使用的项目。如果想确保算法始终丢弃最近最少使用的项目，则该算法需要跟踪使用的内容，这是昂贵的。该技术的一般实现需要保留高速缓存行的“年龄位”，并根据年龄位跟踪“最近最少使用”的高速缓存行。在这样的实现中，每次使用高速缓存行时，所有其他高速缓存行的寿命都会改变。

以下示例的访问顺序为 ABCDECD B。

class Node:
    def __init__(self, k, v):
        self.key = k
        self.value = v
        self.next = None
        self.prev = None
class LRU_cache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.dic = dict()
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
    def _add(self, node):
        p = self.tail.prev
        p.next = node
        self.tail.prev = node
        node.next = self.tail
        node.prev = p
    def _remove(self, node):
        p = node.prev
        n = node.next
        p.next = n
        n.prev = p
    def get(self, key):
        if key in self.dic:
            n = self.dic[key]
            self._remove(n)
            self._add(n)
            return n.value
        return -1
    def set(self, key, value):
        n = Node(key, value)
        self._add(n)
        self.dic[key] = n
        if len(self.dic) > self.capacity:
            n = self.head.next
            self._remove(n)
            del self.dic[n.key]
cache = LRU_cache(3)
cache.set('a', 'apple')
cache.set('b', 'ball')
cache.set('c', 'cat')
cache.set('d', 'dog')
print(cache.get('a'))
print(cache.get('c'))