LFU算法

LFU(Least Frequently Used)算法，即最不经常使用算法，是置换算法(也叫淘汰算法)的一种，最早是在学习操作系统时接触的。

原理

当内存不足时，选择淘汰访问次数最少的页面。

实现方法

为每一个页面设置一个访问次数计数器。当一个页面刚被移到内存时，对应的计数器初始化为0；当一个页面被访问时，对应的计数器值加1；当需要淘汰时，取计数器值最小的页面，如果存在多个访问次数最少的页面，淘汰最近最久未使用的页面。

LeetCode上实现LFU算法的题目：460. LFU 缓存。

主要使用两个Map：cache用来存K, Node，Node中有K, V和使用频率；frequencyMap用来存使用频率对应的节点链表，该节点链表使用LinkedHashSet双向链表来存Node。

public class LFUCache {
    private Map<Integer, Node> cache;
    private Map<Integer, LinkedHashSet<Node>> frequencyMap;
    private int capacity;
    private int size;
    private int minFrequency;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>(this.capacity);
        frequencyMap = new HashMap<>();
    }

    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        node.frequency++;
        // 将该Node移动到对应的频率队列中
        addNodeToNewList(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        Node node = cache.get(key);
        if (node == null) {
            node = new Node(key, value);
            // 必须在这里判断是否要移除最不经常使用的节点，不然新加入的节点就直接被移除了
            if (size == capacity) {
                // 移除最不经常使用的节点
                removeEldestNode();
            }
            cache.put(key, node);
            minFrequency = 0;
            size++;
        } else {
            node.value = value;
            node.frequency++;
        }
        // 将该Node移动到对应的频率队列中
        addNodeToNewList(node);
    }

    /**
     * 将Node移动到对应的频率队列中
     *
     * @param node 节点
     */
    private void addNodeToNewList(Node node) {
        if (node.frequency > 0) {
            // 将该节点从原先的队列删除
            removeNodeOnOldList(node);
        }
        // 将该节点加入新的频率队列
        LinkedHashSet<Node> frequencyList = frequencyMap.get(node.frequency);
        if (frequencyList == null) {
            frequencyList = new LinkedHashSet<>();
            frequencyMap.put(node.frequency, frequencyList);
        }
        frequencyList.add(node);
    }

    /**
     * 移除最不经常使用的节点
     */
    private void removeEldestNode() {
        LinkedHashSet<Node> minFrequencyList = frequencyMap.get(minFrequency);
        Node eldestNode = minFrequencyList.iterator().next();
        if (minFrequencyList.size() == 1) {
            frequencyMap.remove(minFrequency);
            // 这里不用minFrequency++，因为移除最不经常使用的节点一定发生在添加新节点时，那么之后minFrequency一定为0
        } else {
            minFrequencyList.remove(eldestNode);
        }
        cache.remove(eldestNode.key);
        size--;
    }

    /**
     * 将节点从原先的队列删除
     *
     * @param node
     */
    private void removeNodeOnOldList(Node node) {
        int oldFrequency = node.frequency - 1;
        LinkedHashSet<Node> oldFrequencyList = frequencyMap.get(oldFrequency);
        if (oldFrequencyList.size() == 1) {
            frequencyMap.remove(oldFrequency);
            if (minFrequency == oldFrequency) {
                minFrequency = node.frequency;
            }
        } else {
            oldFrequencyList.remove(node);
        }
    }

    private class Node {
        private int key;
        private int value;
        // 使用频率
        private int frequency;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}

缺点

该算法的不足之处是：以前曾经多次使用的页面，虽然目前不用也会留在内存，而刚刚移入内存的页面因其访问次数很少反而会被淘汰。