最不常用（LFU）是一种用于管理计算机内存的缓存算法。该方法的标准特征涉及系统跟踪块在内存中被引用的次数。当缓存已满并需要更多空间时，系统将清除具有最低参考频率的项目。
在Java中实现最近使用的对象缓存的最佳方法是什么？
我已经使用LinkedHashMap实现了一个（通过维护对象被访问的次数）但我很好奇是否有任何新的并发集合是更好的候选者。
考虑这种情况：假设缓存已满，我们需要为另一个缓存腾出空间。假设在缓存中记录了两个对象，这些对象仅被访问一次。如果我们知道其他（不在缓存中）对象被多次访问，那么要删除哪一个？
谢谢！
正如您所提到的，您可以使用LinkedHashMap，因为它在O（1）中提供元素访问，并且您还可以获得订单遍历。请找下LFU Cache的以下代码：（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;
}
}
您可能会受益于ActiveMQ的LFU实现：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中的位置以及哈希映射中是否存在）。所有操作都将以恒定的平均时间复杂度工作，这是您对缓存的期望。
这是LFU的o（1）实现 - http://dhruvbird.com/lfu.pdf
优先级队列怎么样？您可以使用表示频率的键来保存元素。访问后只需更新队列中的对象位置即可。您可以不时更新以优化性能（但降低精度）。
我见过的许多实现都有运行时复杂性O(log(n))。这意味着，当缓存大小为n时，在chache中插入/删除元素所需的时间是对数的。这种实现通常使用min heap来维持元素的使用频率。堆的根包含频率最低的元素，可以在O(1)时间访问。但是为了维护堆属性，每次在堆内部使用（并且频率递增）时，我们必须移动一个元素，将其置于适当的位置，或者当我们必须将新元素插入缓存时（以此类推）把它放进堆里）。但是当我们使用元素作为键维护O(1)（Java）或hashmap（C ++）时，运行时复杂性可以减少到unordered_map。另外，我们需要两种列表，frequency list和elements lists。 elements lists包含具有相同频率的元素，frequency list包含element lists。
frequency list
1 3 6 7
a k y x
c l z
m n
在这个例子中，我们看到frequency list有4个元素（4个elements lists）。元素列表1包含元素(a,c,m)，元素列表3包含元素(k, l, n)等。现在，当我们使用say元素y时，我们必须增加其频率并将其放在下一个列表中。因为频率为6的元素列表变为空，我们将其删除。结果是：
frequency list
1 3 7
a k y
c l x
m n z
我们将元素y放在elements list 7的开头。当我们以后必须从列表中删除元素时，我们将从结束开始（首先是z，然后是x，然后是y）。现在，当我们使用元素n时，我们必须增加其频率并将其放入新的列表中，频率为4：
frequency list
1 3 4 7
a k n y
c l x
m z
我希望这个想法很清楚。我现在提供LFU缓存的C ++实现，稍后将添加Java实现。该课程只有两种公共方法，void set(key k, value v)和bool get(key k, value &v)。在get方法中，将在找到元素时为每个引用设置要检索的值，在这种情况下，该方法返回true。找不到元素时，该方法返回false。
#include<unordered_map>
#include<list>
using namespace std;
typedef unsigned uint;
template<typename K, typename V = K>
struct Entry
{
K key;
V value;
};
template<typename K, typename V = K>
class LFUCache
{
typedef typename list<typename Entry<K, V>> ElementList;
typedef typename list <pair <uint, ElementList>> FrequencyList;
private:
unordered_map <K, pair<typename FrequencyList::iterator, typename ElementList::iterator>> cacheMap;
FrequencyList elements;
uint maxSize;
uint curSize;
void incrementFrequency(pair<typename FrequencyList::iterator, typename ElementList::iterator> p) {
if (p.first == prev(elements.end())) {
//frequency list contains single list with some frequency, create new list with incremented frequency (p.first->first + 1)
elements.push_back({ p.first->first + 1, { {p.second->key, p.second->value} } });
// erase and insert the key with new iterator pair
cacheMap[p.second->key] = { prev(elements.end()), prev(elements.end())->second.begin() };
}
else {
// there exist element(s) with higher frequency
auto pos = next(p.first);
if (p.first->first + 1 == pos->first)
// same frequency in the next list, add the element in the begin
pos->second.push_front({ p.second->key, p.second->value });
else
// insert new list before next list
pos = elements.insert(pos, { p.first->first + 1 , {{p.second->key, p.second->value}} });
// update cachMap iterators
cacheMap[p.second->key] = { pos, pos->second.begin() };
}
// if element list with old frequency contained this singe element, erase the list from frequency list
if (p.first->second.size() == 1)
elements.erase(p.first);
else
// erase only the element with updated frequency from the old list
p.first->second.erase(p.second);
}
void eraseOldElement() {
if (elements.size() > 0) {
auto key = prev(elements.begin()->second.end())->key;
if (elements.begin()->second.size() < 2)
elements.erase(elements.begin());
else
elements.begin()->second.erase(prev(elements.begin()->second.end()));
cacheMap.erase(key);
curSize--;
}
}
public:
LFUCache(uint size) {
if (size > 0)
maxSize = size;
else
maxSize = 10;
curSize = 0;
}
void set(K key, V value) {
auto entry = cacheMap.find(key);
if (entry == cacheMap.end()) {
if (curSize == maxSize)
eraseOldElement();
if (elements.begin() == elements.end()) {
elements.push_front({ 1, { {key, value} } });
}
else if (elements.begin()->first == 1) {
elements.begin()->second.push_front({ key,value });
}
else {
elements.push_front({ 1, { {key, value} } });
}
cacheMap.insert({ key, {elements.begin(), elements.begin()->second.begin()} });
curSize++;
}
else {
entry->second.second->value = value;
incrementFrequency(entry->second);
}
}
bool get(K key, V &value) {
auto entry = cacheMap.find(key);
if (entry == cacheMap.end())
return false;
value = entry->second.second->value;
incrementFrequency(entry->second);
return true;
}
};
以下是用法示例：
int main()
{
LFUCache<int>cache(3); // cache of size 3
cache.set(1, 1);
cache.set(2, 2);
cache.set(3, 3);
cache.set(2, 4);
rc = cache.get(1, r);
assert(rc);
assert(r == 1);
// evict old element, in this case 3
cache.set(4, 5);
rc = cache.get(3, r);
assert(!rc);
rc = cache.get(4, r);
assert(rc);
assert(r == 5);
LFUCache<int, string>cache2(2);
cache2.set(1, "one");
cache2.set(2, "two");
string val;
rc = cache2.get(1, val);
if (rc)
assert(val == "one");
else
assert(false);
cache2.set(3, "three"); // evict 2
rc = cache2.get(2, val);
assert(rc == false);
rc = cache2.get(3, val);
assert(rc);
assert(val == "three");
}