如何实现最少使用（LFU）缓存？

Question

最少使用（LFU）是一种高速缓存算法，用于管理计算机内的内存。此方法的标准特性涉及系统跟踪内存中块被引用的次数。当缓存已满且需要更多空间时，系统将以最低参考频率清除项目。

例如，用Java来实现最近使用的对象缓存的最佳方法是什么？

我已经使用LinkedHashMap实现了一个（通过保持访问对象的次数），但是我很好奇是否有任何新的并发集合会更好。

考虑这种情况：假设缓存已满，我们需要为另一个空间腾出空间。假设在缓存中记录了两个对象，它们只能访问一次。如果我们知道另一个（不在缓存中）对象被访问了不止一次，该删除哪个对象？

谢谢！

Answer 1

1. 根据我的说法，实现最近使用的对象缓存的最佳方法是为每个对象包括一个新变量作为“ latestTS”。TS代表时间戳。

//一个静态方法，该方法返回自1970年1月1日以来的当前日期和时间（以毫秒为单位）long long longTS =
System.currentTimeMillis（）;。

1. ConcurrentJava集合中尚未实现ConcurrentLinkedHashMap。（参考：Java Concurrent Collection API）。但是，您可以尝试使用ConcurrentHashMap和DoublyLinkedList

2. 关于要考虑的情况：在这种情况下，正如我已经说过的那样，您可以声明最新的变量，根据最新的变量的值，可以删除条目并添加新对象。（不要忘记更新添加的新对象的频率和最新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;
    }
}