实现LRU缓存的最佳方式
我正在研究LRU缓存实现的这个问题，其中在缓存大小已满之后，弹出最近最少使用的项目并将其替换为新项目。
我有两个实现：
1）。 创建两个看起来像这样的地图
std::map time_to_key std::map<key, std::pair> LRUCache 要插入新元素，我们可以将当前时间戳和值放在LRUCache中 。 当缓存的大小已满时，我们可以通过查找时间 _to_ 键中存在的最小时间戳并从LRUCache中删除相应的键来逐出最近的元素。 插入一个新项是O（1），更新时间戳是O（n）（因为我们需要在时间 _to_ 键中搜索对应于时间戳的k 。
2）。 有一个链表，其中最近最少使用的缓存出现在头部，新项目添加在尾部。 当项目到达时已经存在于高速缓存中，与该项目的键对应的节点被移动到列表的尾部。 插入一个新项是O（1），更新时间戳再次是O（n）（因为我们需要移动到列表的尾部），删除一个元素是O（1）。
现在我有以下问题：
-
对于LRUCache，这些实现中哪一个更好。
-
有没有其他方法来实现LRU Cache。
-
在Java中，我应该使用HashMap来实现LRUCache
-
我已经看到了诸如实现通用LRU缓存之类的问题，并且还遇到了诸如实现LRU缓存之类的问题。 通用LRU缓存是否与LRU缓存不同？
提前致谢！！！
编辑：
在Java中实现LRUCache的另一种方法（最简单的方法）是使用LinkedHashMap并覆盖boolean removeEldestEntry（Map.entry eldest）函数。
如果你想要一个LRU缓存，Java中最简单的就是LinkedHashMap。 默认行为是FIFO，但您可以将其更改为“访问顺序”，这使其成为LRU缓存。
public static Map lruCache(final int maxSize) { return new LinkedHashMap(maxSize*4/3, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > maxSize; } }; }
注意：我使用的构造函数将集合从最新的第一个更改为最近使用的集合。
来自Javadoc
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) Constructs an empty LinkedHashMap instance with the specified initial capacity, load factor and ordering mode. Parameters: initialCapacity - the initial capacity loadFactor - the load factor accessOrder - the ordering mode - true for access-order, false for insertion-order
当accessOrder为true时，只要你得到一个不是最后一个的条目，LinkedHashMap就会重新排列地图的顺序。
这样，最旧的条目是最近使用的最小条目。
通常，LRU高速缓存表示为LIFO结构 – 单个元素队列。 如果您的标准提供的那个不允许您从中间移除对象，例如，将它们放在顶部，那么您可能必须自己滚动。
考虑到缓存允许并发访问，LRU缓存的良好设计问题归结为：
a）我们可以在更新两个结构（缓存结构和LRU结构）时避免使用互斥锁。
b）缓存的读取（get）操作是否需要互斥锁？
更详细：比如说，如果我们使用java.util.concurrent.ConcuurentHashMap（缓存结构）和java.util.concurrent.ConcurrentLinkedQueue（LRU结构）实现它
a）在编辑操作上锁定这两个结构 – addEntry（），removeEntry（），evictEntries（）等。
b）上面的内容可能会因为写入操作速度慢而传递，但问题甚至是读取（get）操作，我们需要在两个结构上应用锁定。 因为，get意味着将条目放在LRU策略的队列前面。（假设条目从队列的末尾删除）。
使用高效的并发结构（如ConcurrentHashMap）并等待自由的ConcurrentLinkedQueue然后对它们进行锁定就会失去它的全部目的。
我使用相同的方法实现了LRU缓存，但LRU结构是异步更新的，无需在访问这些结构时使用任何互斥锁。 LRU是Cache的内部细节，可以以任何方式实现，而不会影响缓存的用户。
后来，我还读到了ConcurrentLinkedHashMap
https://code.google.com/p/concurrentlinkedhashmap/
并发现它也试图做同样的事情。 没有使用这种结构，但也许可能是一个很好的选择。
我想通过两种可能的实现来扩展其中一些建议。 一个不是线程安全的，可能是一个。
这是一个最简单的版本，unit testing显示它有效。
首先是非并发版本：
import java.util.LinkedHashMap; import java.util.Map; public class LruSimpleCache implements LruCache { Map map = new LinkedHashMap ( ); public LruSimpleCache (final int limit) { map = new LinkedHashMap (16, 0.75f, true) { @Override protected boolean removeEldestEntry(final Map.Entry eldest) { return super.size() > limit; } }; } @Override public void put ( K key, V value ) { map.put ( key, value ); } @Override public V get ( K key ) { return map.get(key); } //For testing only @Override public V getSilent ( K key ) { V value = map.get ( key ); if (value!=null) { map.remove ( key ); map.put(key, value); } return value; } @Override public void remove ( K key ) { map.remove ( key ); } @Override public int size () { return map.size (); } public String toString() { return map.toString (); } }
真正的标志将跟踪获取和放置的访问。 请参阅JavaDocs。 没有构造函数的true标志的removeEdelstEntry只会实现FIFO缓存（请参阅下面有关FIFO和removeEldestEntry的注释）。
以下测试certificate它可以作为LRU缓存使用：
public class LruSimpleTest { @Test public void test () { LruCache cache = new LruSimpleCache<> ( 4 ); cache.put ( 0, 0 ); cache.put ( 1, 1 ); cache.put ( 2, 2 ); cache.put ( 3, 3 ); boolean ok = cache.size () == 4 || die ( "size" + cache.size () ); cache.put ( 4, 4 ); cache.put ( 5, 5 ); ok |= cache.size () == 4 || die ( "size" + cache.size () ); ok |= cache.getSilent ( 2 ) == 2 || die (); ok |= cache.getSilent ( 3 ) == 3 || die (); ok |= cache.getSilent ( 4 ) == 4 || die (); ok |= cache.getSilent ( 5 ) == 5 || die (); cache.get ( 2 ); cache.get ( 3 ); cache.put ( 6, 6 ); cache.put ( 7, 7 ); ok |= cache.size () == 4 || die ( "size" + cache.size () ); ok |= cache.getSilent ( 2 ) == 2 || die (); ok |= cache.getSilent ( 3 ) == 3 || die (); ok |= cache.getSilent ( 4 ) == null || die (); ok |= cache.getSilent ( 5 ) == null || die (); if ( !ok ) die (); }
现在为并发版本……
import java.util.LinkedHashMap; import java.util.Map; import java.util.concurrent.locks.ReadWriteLock; import java.util.concurrent.locks.ReentrantReadWriteLock; public class LruSimpleConcurrentCache implements LruCache { final CacheMap[] cacheRegions; private static class CacheMap extends LinkedHashMap { private final ReadWriteLock readWriteLock; private final int limit; CacheMap ( final int limit, boolean fair ) { super ( 16, 0.75f, true ); this.limit = limit; readWriteLock = new ReentrantReadWriteLock ( fair ); } protected boolean removeEldestEntry ( final Map.Entry eldest ) { return super.size () > limit; } @Override public V put ( K key, V value ) { readWriteLock.writeLock ().lock (); V old; try { old = super.put ( key, value ); } finally { readWriteLock.writeLock ().unlock (); } return old; } @Override public V get ( Object key ) { readWriteLock.writeLock ().lock (); V value; try { value = super.get ( key ); } finally { readWriteLock.writeLock ().unlock (); } return value; } @Override public V remove ( Object key ) { readWriteLock.writeLock ().lock (); V value; try { value = super.remove ( key ); } finally { readWriteLock.writeLock ().unlock (); } return value; } public V getSilent ( K key ) { readWriteLock.writeLock ().lock (); V value; try { value = this.get ( key ); if ( value != null ) { this.remove ( key ); this.put ( key, value ); } } finally { readWriteLock.writeLock ().unlock (); } return value; } public int size () { readWriteLock.readLock ().lock (); int size = -1; try { size = super.size (); } finally { readWriteLock.readLock ().unlock (); } return size; } public String toString () { readWriteLock.readLock ().lock (); String str; try { str = super.toString (); } finally { readWriteLock.readLock ().unlock (); } return str; } } public LruSimpleConcurrentCache ( final int limit, boolean fair ) { int cores = Runtime.getRuntime ().availableProcessors (); int stripeSize = cores < 2 ? 4 : cores * 2; cacheRegions = new CacheMap[ stripeSize ]; for ( int index = 0; index < cacheRegions.length; index++ ) { cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair ); } } public LruSimpleConcurrentCache ( final int concurrency, final int limit, boolean fair ) { cacheRegions = new CacheMap[ concurrency ]; for ( int index = 0; index < cacheRegions.length; index++ ) { cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair ); } } private int stripeIndex ( K key ) { int hashCode = key.hashCode () * 31; return hashCode % ( cacheRegions.length ); } private CacheMap map ( K key ) { return cacheRegions[ stripeIndex ( key ) ]; } @Override public void put ( K key, V value ) { map ( key ).put ( key, value ); } @Override public V get ( K key ) { return map ( key ).get ( key ); } //For testing only @Override public V getSilent ( K key ) { return map ( key ).getSilent ( key ); } @Override public void remove ( K key ) { map ( key ).remove ( key ); } @Override public int size () { int size = 0; for ( CacheMap cache : cacheRegions ) { size += cache.size (); } return size; } public String toString () { StringBuilder builder = new StringBuilder (); for ( CacheMap cache : cacheRegions ) { builder.append ( cache.toString () ).append ( '\n' ); } return builder.toString (); } }
您可以看到为什么我首先覆盖非并发版本。 以上尝试创建一些条带以减少锁争用。 所以我们哈希键，然后查找该哈希以找到实际的缓存。 这使得极限大小更多地是在相当大的误差范围内的建议/粗略猜测，这取决于密钥散列算法的传播程度。
问题陈述 ：
创建LRU缓存并存储Employee对象Max = 5个对象，并找出谁首先登录和之后….
package com.test.example.dto; import java.sql.Timestamp; /** * * @author Vaquar.khan@gmail.com * */ public class Employee implements Comparable { private int id; private String name; private int age; private Timestamp loginTime ; public int getId() { return id; } public void setId(int id) { this.id = id; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } public Timestamp getLoginTime() { return loginTime; } public void setLoginTime(Timestamp loginTime) { this.loginTime = loginTime; } @Override public String toString() { return "Employee [id=" + id + ", name=" + name + ", age=" + age + ", loginTime=" + loginTime + "]"; } Employee(){} public Employee(int id, String name, int age, Timestamp loginTime) { super(); this.id = id; this.name = name; this.age = age; this.loginTime = loginTime; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + age; result = prime * result + id; result = prime * result + ((loginTime == null) ? 0 : loginTime.hashCode()); result = prime * result + ((name == null) ? 0 : name.hashCode()); return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Employee other = (Employee) obj; if (age != other.age) return false; if (id != other.id) return false; if (loginTime == null) { if (other.loginTime != null) return false; } else if (!loginTime.equals(other.loginTime)) return false; if (name == null) { if (other.name != null) return false; } else if (!name.equals(other.name)) return false; return true; } @Override public int compareTo(Employee emp) { if (emp.getLoginTime().before( this.loginTime) ){ return 1; } else if (emp.getLoginTime().after(this.loginTime)) { return -1; } return 0; } }
LRUObjectCacheExample
package com.test.example; import java.sql.Timestamp; import java.util.Calendar; import java.util.LinkedHashMap; import java.util.Map; import java.util.Map.Entry; import com.test.example.dto.Employee; /** * * @author Vaquar.khan@gmail.com * */ public class LRUObjectCacheExample { LinkedHashMap lruCacheLinkedQueue; public LRUObjectCacheExample(int capacity) { lruCacheLinkedQueue = new LinkedHashMap(capacity, 1.0f, true) { /** * */ private static final long serialVersionUID = 1L; @Override protected boolean removeEldestEntry( //calling map's entry method Map.Entry eldest) { return this.size() > capacity; } }; } void addDataIntoCache(Employee employee) { lruCacheLinkedQueue.put(employee, true); displayLRUQueue(); } boolean checkIfDataPresentIntoLRUCaache(int data) { return lruCacheLinkedQueue.get(data) != null; } void deletePageNo(int data) { if (lruCacheLinkedQueue.get(data) != null){ lruCacheLinkedQueue.remove(data); } displayLRUQueue(); } void displayLRUQueue() { System.out.print("-------------------------------------------------------"+"\n"); System.out.print("Data into LRU Cache : "); for (Entry mapEntry : lruCacheLinkedQueue.entrySet()) { System.out.print("[" + mapEntry.getKey() + "]"); } System.out.println(""); } public static void main(String args[]) { Employee employee1 = new Employee(1,"Shahbaz",29, getCurrentTimeStamp()); Employee employee2 = new Employee(2,"Amit",35,getCurrentTimeStamp()); Employee employee3 = new Employee(3,"viquar",36,getCurrentTimeStamp()); Employee employee4 = new Employee(4,"Sunny",20,getCurrentTimeStamp()); Employee employee5 = new Employee(5,"sachin",28,getCurrentTimeStamp()); Employee employee6 = new Employee(6,"Sneha",25,getCurrentTimeStamp()); Employee employee7 = new Employee(7,"chantan",19,getCurrentTimeStamp()); Employee employee8 = new Employee(8,"nitin",22,getCurrentTimeStamp()); Employee employee9 = new Employee(9,"sanuj",31,getCurrentTimeStamp()); // LRUObjectCacheExample lru = new LRUObjectCacheExample(5); lru.addDataIntoCache(employee5);//sachin lru.addDataIntoCache(employee4);//Sunny lru.addDataIntoCache(employee3);//viquar lru.addDataIntoCache(employee2);//Amit lru.addDataIntoCache(employee1);//Shahbaz -----capacity reached // lru.addDataIntoCache(employee6);/Sneha lru.addDataIntoCache(employee7);//chantan lru.addDataIntoCache(employee8);//nitin lru.addDataIntoCache(employee9);//sanuj // lru.deletePageNo(3); lru.deletePageNo(4); } private static Timestamp getCurrentTimeStamp(){ return new java.sql.Timestamp(Calendar.getInstance().getTime().getTime()); } }
结果：
**Data into LRU Cache :** [Employee [id=1, name=Shahbaz, age=29, loginTime=2015-10-15 18:47:28.1 [Employee [id=6, name=Sneha, age=25, loginTime=2015-10-15 18:47:28.125 [Employee [id=7, name=chantan, age=19, loginTime=2015-10-15 18:47:28.125 [Employee [id=8, name=nitin, age=22, loginTime=2015-10-15 18:47:28.125 [Employee [id=9, name=sanuj, age=31, loginTime=2015-10-15 18:47:28.125
LinkedHashMap允许您覆盖removeEldestEntry函数，这样无论何时执行put，您都可以指定是否删除最旧的条目，从而允许实现LRU。
myLRUCache = new LinkedHashMap() { protected boolean removeEldestEntry(Map.Entry eldest) { if(this.size()>1000) return true; else return false; } };
对于O（1）访问，我们需要一个哈希表并维护顺序，我们可以使用DLL。 基本算法是 – 从页码我们可以使用哈希表到达DLL节点。 如果页面存在，我们可以将节点移动到DLL的头部，否则在DLL和哈希表中插入节点。 如果DLL的大小已满，我们可以从尾部删除最近最少使用的节点。
这是一个基于双向链表和C ++中unordered_map的实现。
#include #include #include using namespace std; // List nodeclass class Node { public: int data; Node* next; Node* prev; }; //Doubly Linked list class DLList { public: DLList() { head = NULL; tail = NULL; count = 0; } ~DLList() {} Node* addNode(int val); void print(); void removeTail(); void moveToHead(Node* node); int size() { return count; } private: Node* head; Node* tail; int count; }; // Function to add a node to the list Node* DLList::addNode(int val) { Node* temp = new Node(); temp->data = val; temp->next = NULL; temp->prev = NULL; if ( tail == NULL ) { tail = temp; head = temp; } else { head->prev = temp; temp->next = head; head = temp; } count++; return temp; } void DLList::moveToHead(Node* node) { if (head == node) return; node->prev->next = node->next; if (node->next != NULL) { node->next->prev = node->prev; } else { tail = node->prev; } node->next = head; node->prev = NULL; head->prev = node; head = node; } void DLList::removeTail() { count--; if (head == tail) { delete head; head = NULL; tail = NULL; } else { Node* del = tail; tail = del->prev; tail->next = NULL; delete del; } } void DLList::print() { Node* temp = head; int ctr = 0; while ( (temp != NULL) && (ctr++ != 25) ) { cout << temp->data << " "; temp = temp->next; } cout << endl; } class LRUCache { public: LRUCache(int aCacheSize); void fetchPage(int pageNumber); private: int cacheSize; DLList dlist; unordered_map< int, Node* > directAccess; }; LRUCache::LRUCache(int aCacheSize):cacheSize(aCacheSize) { } void LRUCache::fetchPage(int pageNumber) { unordered_map< int, Node* >::const_iterator it = directAccess.find(pageNumber); if (it != directAccess.end()) { dlist.moveToHead( (Node*)it->second); } else { if (dlist.size() == cacheSize-1) dlist.removeTail(); Node* node = dlist.addNode(pageNumber); directAccess.insert(pair< int, Node* >(pageNumber,node)); } dlist.print(); } int main() { LRUCache lruCache(10); lruCache.fetchPage(5); lruCache.fetchPage(7); lruCache.fetchPage(15); lruCache.fetchPage(34); lruCache.fetchPage(23); lruCache.fetchPage(21); lruCache.fetchPage(7); lruCache.fetchPage(32); lruCache.fetchPage(34); lruCache.fetchPage(35); lruCache.fetchPage(15); lruCache.fetchPage(37); lruCache.fetchPage(17); lruCache.fetchPage(28); lruCache.fetchPage(16); return 0; }
延伸彼得劳雷的答案
可以重写removeEldestEntry(java.util.Map.Entry)方法，以强制在将新映射添加到映射时自动删除过时映射的策略。
因此可以覆盖LinkedHashMap的FIFO行为以生成LRU
public class LRUCache extends LinkedHashMap { private int cacheSize; public LRUCache(int cacheSize) { super(cacheSize * 4 / 3, 0.75f, true); this.cacheSize = cacheSize; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() >= cacheSize; } public static void main(String args[]) { LRUCache lruCache = new LRUCache<>(5); lruCache.put(1, 1); lruCache.put(2, 2); lruCache.put(3, 3); lruCache.put(1, 4); lruCache.put(2, 5); lruCache.put(7, 6); System.out.println(lruCache.keySet()); lruCache.put(1, 4); lruCache.put(2, 5); System.out.println(lruCache.keySet()); } }
class LRU { Map ageMap = new HashMap(); int age = 1; void addElementWithAge(String element) { ageMap.put(element, age); age++; } String getLeastRecent(Map ageMap) { Integer oldestAge = (Integer) ageMap.values().toArray()[0]; String element = null; for (Entry entry : ageMap.entrySet()) { if (oldestAge >= entry.getValue()) { oldestAge = entry.getValue(); element = entry.getKey(); } } return element; } public static void main(String args[]) { LRU obj = new LRU(); obj.addElementWithAge("M1"); obj.addElementWithAge("M2"); obj.addElementWithAge("M3"); obj.addElementWithAge("M4"); obj.addElementWithAge("M1"); } }