如何实现最少使用（LFU）缓存？
最不常用（LFU）是一种用于管理计算机内存的缓存算法。 该方法的标准特性涉及系统跟踪内存中引用块的次数。 当缓存已满且需要更多空间时，系统将以最低参考频率清除项目。
在Java中实现最近使用的对象缓存的最佳方式是什么？
我已经使用LinkedHashMap实现了一个（通过保持访问对象的次数）但是我很好奇新的并发集合是否会成为更好的候选者。
考虑这种情况：假设缓存已满，我们需要为另一个缓存空间。 假设两个对象在高速缓存中被记录，它们只被访问一次。 如果我们知道其他（不在缓存中的）对象被多次访问，哪一个要删除？
谢谢！
根据我的观点，实现最近使用的对象缓存的最好方法是为每个对象包含一个新变量'latestTS'。 TS代表时间戳。
//返回自1970年1月1日以来的毫秒数的当前日期和时间的静态方法long latestTS = System.currentTimeMillis（）;
ConcurrentLinkedHashMap尚未在并发Java集合中实现。 （参考：Java Concurrent Collection API）。 但是，您可以尝试使用ConcurrentHashMap和DoublyLinkedList
关于要考虑的情况：在这种情况下，正如我所说的，您可以根据latestTS变量的值声明latestTS变量，您可以删除一个条目并添加新的对象。 （不要忘记更新添加的新对象的频率和最新的TS）
正如你所提到的，你可以使用LinkedHashMap，因为它给出了O（1）中的元素访问，并且你也可以进行顺序遍历。 请找到下面的LFU缓存代码：（PS：下面的代码是标题问题的答案，即“如何实现LFU缓存”）
import java.util.LinkedHashMap;
import java.util.Map;
public class LFUCache {
class CacheEntry
{
private String data;
private int frequency;
// default constructor
private CacheEntry()
{}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public int getFrequency() {
return frequency;
}
public void setFrequency(int frequency) {
this.frequency = frequency;
}
}
private static int initialCapacity = 10;
private static LinkedHashMap<Integer, CacheEntry> cacheMap = new LinkedHashMap<Integer, CacheEntry>();
/* LinkedHashMap is used because it has features of both HashMap and LinkedList.
* Thus, we can get an entry in O(1) and also, we can iterate over it easily.
* */
public LFUCache(int initialCapacity)
{
this.initialCapacity = initialCapacity;
}
public void addCacheEntry(int key, String data)
{
if(!isFull())
{
CacheEntry temp = new CacheEntry();
temp.setData(data);
temp.setFrequency(0);
cacheMap.put(key, temp);
}
else
{
int entryKeyToBeRemoved = getLFUKey();
cacheMap.remove(entryKeyToBeRemoved);
CacheEntry temp = new CacheEntry();
temp.setData(data);
temp.setFrequency(0);
cacheMap.put(key, temp);
}
}
public int getLFUKey()
{
int key = 0;
int minFreq = Integer.MAX_VALUE;
for(Map.Entry<Integer, CacheEntry> entry : cacheMap.entrySet())
{
if(minFreq > entry.getValue().frequency)
{
key = entry.getKey();
minFreq = entry.getValue().frequency;
}
}
return key;
}
public String getCacheEntry(int key)
{
if(cacheMap.containsKey(key)) // cache hit
{
CacheEntry temp = cacheMap.get(key);
temp.frequency++;
cacheMap.put(key, temp);
return temp.data;
}
return null; // cache miss
}
public static boolean isFull()
{
if(cacheMap.size() == initialCapacity)
return true;
return false;
}
}
您可能从LFU实施ActiveMQ： LFUCache中获益
他们提供了一些很好的功能。
我认为，LFU数据结构必须结合优先级队列（用于保持对lfu项目的快速访问）和散列图（用于通过其密钥提供对任何项目的快速访问）; 我会建议缓存中存储的每个对象的以下节点定义：
class Node<T> {
// access key
private int key;
// counter of accesses
private int numAccesses;
// current position in pq
private int currentPos;
// item itself
private T item;
//getters, setters, constructors go here
}
您需要key才能参考项目。 您需要numAccesses作为优先队列的关键字。 您需要currentPos才能够通过按键快速找到物品的pq位置。 现在，您将使用访问次数作为优先级，组织哈希映射（键（ Integer ） - >节点（ Node<T> ））以快速访问项目和基于最小堆的优先级队列。 现在，您可以快速执行所有操作（访问，添加新项目，更新加载数量，删除lfu）。 您需要仔细编写每个操作，以便它保持所有节点的一致性（访问次数，它们在pq中的位置以及散列映射中存在的位置）。 所有操作都将以不变的平均时间复杂度工作，这是您对缓存的期望。