C++ LRU缓存设计

LRU cache design

提问by user297850

Least Recently Used (LRU) Cache is to discard the least recently used items first How do you design and implement such a cache class? The design requirements are as follows:

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

1) find the item as fast as we can

1）尽快找到项目

2) Once a cache misses and a cache is full, we need to replace the least recently used item as fast as possible.

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

How to analyze and implement this question in terms of design pattern and algorithm design?

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

回答by

A linked list + hashtable of pointers to the linked list nodes is the usual way to implement LRU caches. This gives O(1) operations (assuming a decent hash). Advantage of this (being O(1)): you can do a multithreaded version by just locking the whole structure. You don't have to worry about granular locking etc.

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

Briefly, the way it works:

简而言之，它的工作方式：

On an access of a value, you move the corresponding node in the linked list to the head.

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

When you need to remove a value from the cache, you remove from the tail end.

当你需要从缓存中移除一个值时，你从尾端移除。

When you add a value to cache, you just place it at the head of the linked list.

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

Thanks to doublep, here is site with a C++ implementation: Miscellaneous Container Templates.

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

回答by Tsuneo Yoshioka

This is my simple sample c++ implementation for LRU cache, with the combination of hash(unordered_map), and list. Items on list have key to access map, and items on map have iterator of list to access list.

这是我的 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;
        };

};

回答by Viren

Here is my implementation for a basic, simple LRU cache.

这是我对一个基本的、简单的 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;
    };

回答by Yang Liu

I implemented a thread-safe LRU cache two years back.

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

LRU is typically implemented with a HashMap and LinkedList. You can google the implementation detail. There are a lot of resources about it(Wikipedia have a good explanation too).

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

In order to be thread-safe, you need put lock whenever you modify the state of the LRU.

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

I will paste my C++ code here for your reference.

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

Here is the implementation.

这是实现。

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

Here is the unit tests.

这是单元测试。

#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);

回答by Andrushenko Alexander

I see here several unnecessary complicated implementations, so I decided to provide my implementation as well. The cache has only two methods, get and set. Hopefully it is better readable and understandable:

我在这里看到了几个不必要的复杂实现，所以我决定也提供我的实现。缓存只有两种方法，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;
    }
};

回答by burner

I have a LRU implementation here. The interface follows std::map so it should not be that hard to use. Additionally you can provide a custom backup handler, that is used if data is invalidated in the cache.

我在这里有一个 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"));

回答by Jerry Ju

Is cache a data structure that supports retrieval value by key like hash table? LRU means the cache has certain size limitation that we need drop least used entries periodically.

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

If you implement with linked-list + hashtable of pointers how can you do O(1) retrieval of value by key?

如果您使用链表+指针散列表来实现，您如何通过键进行 O(1) 值检索？

I would implement LRU cache with a hash table that the value of each entry is value + pointers to prev/next entry.

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

Regarding the multi-threading access, I would prefer reader-writer lock (ideally implemented by spin lock since contention is usually fast) to monitor.

关于多线程访问，我更喜欢读写锁（理想情况下由自旋锁实现，因为争用通常很快）来监视。

回答by Amit

This is my simple Java programmer with complexity O(1).

这是我的简单 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);
  }


}

回答by BlueStory

Detailed explanation here in my blogpost.

我的博文中有详细解释。

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

回答by SarthAk

Working of LRU Cache

LRU缓存的工作

Discards the least recently used items first. This algorithm requires keeping track of what was used when which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require keeping "age bits" for cache-lines and track the "Least Recently Used" cache-line based on age-bits. In such an implementation, every time a cache-line is used, the age of all other cache-lines changes.

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

The access sequence for the below example is A B C D E C D B.

以下示例的访问顺序是 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'))

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') 打印(cache.get('a')) 打印(cache.get('c'))