题解 | 设计LFU缓存结构

import java.util.*;


public class Solution {
    // LFU缓存
    Map<Integer, Element> lfuMap = new HashMap<>();
    //频次对应的链表，链表的头结点为最热结点，尾结点为最不热结点
    Map<Integer, LinkedList<Element>> freqMap = new HashMap<>();
    //最小频次,用来定位需要删除的缓存
    int minFrequency = 1;

    public int[] LFU(int[][] operators, int k) {
        //用来存放 get 的结果
        List<Integer> resList = new ArrayList<>();
        for (int[] operator : operators) {
            //操作类型为1时，表示插入缓存，操作类型为2时，表示获取缓存
            if (operator[0] == 1) {
                set(operator[1], operator[2], k);
            } else {
                get(resList, operator[1]);
            }
        }
        
        return resList.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     * 设置缓存,缓存已存在则更新缓存，缓存不存在则插入缓存
     */
    private void set(int key, int value, int k) {
        if (lfuMap.containsKey(key)) {
            update(key, value);
        } else {
            insert(key, value, k);
        }
    }

    /**
     * 更新缓存,更新缓存的同时更新缓存的频次
     *
     * @param key
     * @param value
     */
    private void update(int key, int value) {
        //需要更新的缓存数据
        Element element = lfuMap.get(key);
        //更新缓存
        int freq = element.freq;
        element.freq = freq + 1;
        element.value = value;
        //当前缓存的频次有变化，则需要更新老的频次数据
        LinkedList<Element> elements = freqMap.get(freq);
        elements.remove(element);
        if (elements.isEmpty()) {
            freqMap.remove(freq);
            //如果最小缓存频次的链表为空，则更新最小缓存频次
            if (minFrequency == freq) {
                minFrequency++;
            }
        }

        //当前缓存的频次有变化，则需要插入新的频次数据
        LinkedList<Element> newElements = freqMap.get(element.freq);
        if (newElements == null) {
            newElements = new LinkedList<>();
            newElements.addFirst(element);
            freqMap.put(element.freq, newElements);
        } else {
            newElements.addFirst(element);
        }
    }

    /**
     * 插入缓存,插入缓存的同时更新缓存的频次
     */
    private void insert(int key, int value, int k) {
        Element element = new Element(key, value);
        if (lfuMap.size() >= k) {
            Element last = freqMap.get(minFrequency).removeLast();
            lfuMap.remove(last.key);
        }
        lfuMap.put(key, element);
        LinkedList<Element> elements = freqMap.computeIfAbsent(1,
                                       k1 -> new LinkedList<>());
        elements.addFirst(element);
        minFrequency = 1;
    }

    private void get(List<Integer> resList, int key) {
        if (lfuMap.containsKey(key)) {
            resList.add(lfuMap.get(key).value);
            update(key, lfuMap.get(key).value);
        } else {
            resList.add(-1);
        }
    }


    private class Element {
        private int key;
        private int value;
        private int freq;

        public Element(int key, int value) {
            this.key = key;
            this.value = value;
            this.freq = 1;
        }
    }
}