java实现LFU缓存淘汰算法

原理：

1.使用变量 cap 记录允许存储的缓存数量，超过cap时原先最老且访问次数最少的淘汰

2.使用两个 values 和 counts分别记录缓存 和 缓存被访问的次数（put或get时访问此数会加1）

3.使用 frequency记录每个访问次数对应哪些缓存的key，且这些key是按加入缓存的先后顺序保存的。 frequency用于淘汰时确定要删除的最老且访问次数最少的缓存。

4.min是frequency的key，用于确定要淘汰的缓存。

代码如下：

import java.util.HashMap;
import java.util.linkedHashSet;

public class LFUCache {

    int cap;//最大缓存的数量
    HashMap values;//缓存
    HashMap counts;//缓存的访问频次的key-count
    HashMap> frequency;//同一访问频次的缓存
    int min = -1; //记录要淘汰时的count

    public LFUCache(int cap) {
        this.cap = cap;
        values = new HashMap<>();
        counts = new HashMap<>();
        frequency = new HashMap<>();
        frequency.put(1, new linkedHashSet<>());
    }

    
    public void put(String key, String value) {
        Integer count = 1;
        //put时key已经存在则覆盖原来的值，并调用get方法将count加1
        if (values.containsKey(key)) {
            values.put(key, value);
            get(key);
            return;
        }
        //缓存的数量超过cap时淘汰距今最久且访问次数最少的
        if (values.size() >= cap) {
            String removeKey = frequency.get(min).iterator().next();
            values.remove(removeKey);
            counts.remove(removeKey);
            frequency.get(min).remove(removeKey);
        }
        //缓存未满或缓存满了后淘汰一个后put值到缓存中
        values.put(key, value);
        counts.put(key, count);
        frequency.get(count).add(key);
        min = 1;
    }

    
    public String get(String key) {
        String value = "-1";
        if (values.containsKey(key)) {
            value = values.get(key);
            //更新counts中记录的key对应的数量
            int count = counts.get(key);
            counts.put(key, count + 1);
            //更新最少访问的key的数量min
            if (count == min && frequency.get(count).size() == 0) {
                min++;
            }
            //更新frequency中记录的数量对应的key
            frequency.get(count).remove(key);
            if (!frequency.containsKey(count + 1)) {
                frequency.put(count + 1, new linkedHashSet<>());
            }
            frequency.get(count + 1).add(key);
        }
        return value;
    }

    public int getCap() {
        return cap;
    }

    public HashMap getValues() {
        return values;
    }

    public HashMap getCounts() {
        return counts;
    }

    public HashMap> getFrequency() {
        return frequency;
    }

    public int getMin() {
        return min;
    }
}

测试：

public class MainServer {
    public static void main(String[] args) throws IOException {
        //设置缓存
        LFUCache cache = new LFUCache(4);
        cache.put("a","a");
        cache.put("b","b");
        cache.put("c","c");
        cache.put("d","d");
        //访问缓存
        cache.get("a");
        cache.get("a");
        cache.get("c");
        cache.get("c");
        cache.get("c");
        System.out.println("缓存"+cache.getValues());
        System.out.println("缓存和访问数量"+cache.getCounts());
        System.out.println("缓存访问数量和访问顺序"+cache.getFrequency());
        System.out.println("getFrequency中将淘汰的缓存位置"+cache.getMin());
        System.out.println();
		//添加新缓存e,将淘汰b
        cache.put("e","e");
        System.out.println("缓存"+cache.getValues());
        System.out.println("缓存和访问数量"+cache.getCounts());
        System.out.println("缓存访问数量和访问顺序"+cache.getFrequency());
        System.out.println("getFrequency中将淘汰的缓存位置"+cache.getMin());
    }

结果：

缓存{a=a, b=b, c=c, d=d}
缓存和访问数量{a=3, b=1, c=4, d=1}
缓存访问数量和访问顺序{1=[b, d], 2=[], 3=[a], 4=[c]}
getFrequency中将淘汰的缓存位置1

缓存{a=a, c=c, d=d, e=e}
缓存和访问数量{a=3, c=4, d=1, e=1}
缓存访问数量和访问顺序{1=[d, e], 2=[], 3=[a], 4=[c]}
getFrequency中将淘汰的缓存位置1