缓存的LFU和LRU算法

LFU算法

LFU: Least Frequently Used (使用频率最低)

package com.lzlg.study.lfu;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Optional;

/
 * 自定义最不常用缓存算法(LFU)
 *
 * @author lzlg
 * 2023/1/30 9:45
 */
public class CustomLFUCache<K, V> {
    // 缓存容量
    int capacity;
    // 节点Map
    Map<K, Node<K, V>> nodeMap;
    // 频率Map,key为访问频率,value为相同访问频率的节点双向链表
    Map<Integer, LFULinkedList<K, V>> freqMap;
    // 记录最小访问频率
    int minFreq;

    public CustomLFUCache(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("容量必须大于0");
        }
        this.capacity = capacity;
        this.nodeMap = new HashMap<>();
        this.freqMap = new HashMap<>();
        this.minFreq = 0;
    }

    /
     * 打印节点数据
     */
    public void printNodes() {
        System.out.println(nodeMap);
    }

    /
     * 从缓存中取出数据
     *
     * @param key key
     * @return 数据
     */
    public Optional<V> get(K key) {
        Objects.requireNonNull(key);
        // 如果不包含该key,则直接返回空,使用Optional让客户端必须处理Null值的情况
        if (!nodeMap.containsKey(key)) {
            return Optional.empty();
        }
        // 取出节点
        Node<K, V> node = nodeMap.get(key);
        // 更新节点的访问频率
        this.freqNode(node);
        return Optional.ofNullable(node.value);
    }

    /
     * 更新节点的访问频率
     *
     * @param node 节点信息
     */
    private void freqNode(Node<K, V> node) {
        K key = node.key;
        V value = node.value;
        int freq = node.freq;
        // 根据节点频率查询对应的双向链表
        LFULinkedList<K, V> list = freqMap.get(freq);
        // 节点访问频率+1,要从原来的双向链表中剔除
        list.remove(node);
        nodeMap.remove(key);
        // 如果删除节点后,双向链表为空,则从频率Map中删除
        if (list.isEmpty()) {
            freqMap.remove(freq);
            // 如果当前节点的频率为最小频率,则最小频率+1
            if (freq == minFreq) {
                minFreq += 1;
            }
        }
        // 创建新节点,此时频率+1
        Node<K, V> newNode = new Node<>(key, value, freq + 1);
        nodeMap.put(key, newNode);
        // 查找频率+1的新链表,如果没有,则进行创建
        LFULinkedList<K, V> freqList = freqMap.getOrDefault(freq + 1, new LFULinkedList<>());
        // 添加新节点到链表头部
        freqList.addHead(newNode);
        freqMap.put(freq + 1, freqList);
    }

    /
     * 向缓存中放入数据
     *
     * @param key   key
     * @param value value
     */
    public void put(K key, V value) {
        Objects.requireNonNull(key);
        // 如果已经存在该key
        if (nodeMap.containsKey(key)) {
            // 取出节点
            Node<K, V> node = nodeMap.get(key);
            node.value = value;
            // 和get一样,更新节点的访问频率
            this.freqNode(node);
            return;
        }
        // 如果不存在,先判断容量是否已满
        if (nodeMap.size() == capacity) {
            // 如果容量已满,则从最低频率中取出链表删除链表的尾节点
            LFULinkedList<K, V> list = freqMap.get(minFreq);
            Node<K, V> tail = list.tail();
            // 从节点Map中删除此节点,从双向链表中删除此节点
            nodeMap.remove(tail.key);
            list.remove(tail);
            // 如果双向链表为空,则删除此链表
            if (list.isEmpty()) {
                freqMap.remove(minFreq);
            }
        }
        // 添加新节点
        Node<K, V> newNode = new Node<>(key, value);
        nodeMap.put(key, newNode);
        // 取出节点频率(新节点为1)对应的双向链表
        LFULinkedList<K, V> list = freqMap.getOrDefault(newNode.freq, new LFULinkedList<>());
        list.addHead(newNode);
        freqMap.put(newNode.freq, list);
        // 新节点添加,最小频率必然为1
        minFreq = 1;
    }

    /
     * 节点
     *
     * @param <K>
     * @param <V>
     */
    static class Node<K, V> {

        K key;

        V value;
        // 前节点
        Node<K, V> prev;
        // 后节点
        Node<K, V> next;
        // 记录节点访问次数(频率),不设置此频率,则不能从频率Map中查找
        int freq;

        public Node() {
            this.prev = this.next = null;
            this.freq = 1;
        }

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.prev = this.next = null;
            this.freq = 1;
        }

        public Node(K key, V value, int freq) {
            this.key = key;
            this.value = value;
            this.prev = this.next = null;
            this.freq = freq;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    ", freq=" + freq +
                    '}';
        }
    }

    /
     * 双向链表
     * 规定:头部是最新使用的,尾部是最不常用的
     *
     * @param <K>
     * @param <V>
     */
    static class LFULinkedList<K, V> {
        // 头节点
        Node<K, V> head;
        // 尾节点
        Node<K, V> tail;
        // 链表数据数量
        int size;

        public LFULinkedList() {
            this.head = new Node<>();
            this.tail = new Node<>();
            this.head.next = this.tail;
            this.tail.prev = this.head;
            this.size = 0;
        }

        /
         * 添加节点到头部
         *
         * @param node 节点
         */
        public void addHead(Node<K, V> node) {
            // 新节点的前节点是头节点
            node.prev = head;
            // 新节点的后节点是头节点的后节点
            node.next = head.next;
            // 头节点的后节点的前节点是新节点
            head.next.prev = node;
            // 头节点的后节点是新节点
            head.next = node;
            size++;
        }

        /
         * 添加节点到尾部
         *
         * @param node 节点
         */
        public void addTail(Node<K, V> node) {
            // 新节点的前节点是尾节点的前节点
            node.prev = tail.prev;
            // 新节点的后节点是尾节点
            node.next = tail;
            // 尾节点的前节点的后节点是新节点
            tail.prev.next = node;
            // 尾节点的前节点是新节点
            tail.prev = node;
            size++;
        }

        /
         * 删除节点
         *
         * @param node 节点
         */
        public void remove(Node<K, V> node) {
            // 删除节点的前节点的后节点是删除节点的后节点
            node.prev.next = node.next;
            // 删除节点的后节点的前节点是删除节点的前节点
            node.next.prev = node.prev;
            // 置空删除节点的前节点和后节点,方便GC回收
            node.next = null;
            node.prev = null;
            size--;
        }

        /
         * 获取尾节点数据(是尾节点的前一个)
         *
         * @return 节点
         */
        public Node<K, V> tail() {
            return tail.prev;
        }

        /
         * 是否为空
         *
         * @return 结果
         */
        public boolean isEmpty() {
            return this.size == 0;
        }
    }

    public static void main(String[] args) {
        CustomLFUCache<Integer, Integer> cache = new CustomLFUCache<>(2);
        cache.put(1, 1);   // cache=[1,_], cnt(1)=1
        cache.printNodes();
        cache.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
        cache.printNodes();
        cache.get(1);      // 返回1, cache=[1,2], cnt(2)=1, cnt(1)=2
        cache.printNodes();
        cache.put(3, 3);   // 去除键2,因为 cnt(2)=1 使用计数最小 cache=[3,1], cnt(3)=1, cnt(1)=2
        cache.printNodes();
        cache.get(2);      // 返回 -1(未找到)
        cache.get(3);      // 返回 3 cache=[3,1], cnt(3)=2, cnt(1)=2
        cache.printNodes();
        cache.put(4, 4);   // 去除键 1, 1 和 3 的 cnt 相同, 但 1 最久未使用 cache=[4,3], cnt(4)=1, cnt(3)=2
        cache.printNodes();
        cache.get(1);      // 返回 -1(未找到)
        cache.get(3);      // 返回 3 cache=[3,4], cnt(4)=1, cnt(3)=3
        cache.printNodes();
        cache.get(4);
        cache.printNodes();
    }
}

package com.lzlg.study.lru;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Optional;

/
 * 自己实现LRU算法实现缓存
 * 实现的是头部是最常使用(访问)的数据,尾部是最久未使用(访问)的数据
 *
 * @author lzlg
 * 2023/1/29 15:11
 */
public class CustomLRUCache<K, V> {
    // 容量
    private int capacity;

    // 存放节点的Map,用于根据Key快速查找节点
    private Map<K, Node<K, V>> map;

    private LRULinkedList<K, V> list;

    public CustomLRUCache(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("容量必须大于0");
        }
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.list = new LRULinkedList<>();
    }

    /
     * 从缓存中取出对应的value,
     *
     * @param key key
     * @return value
     */
    public Optional<V> get(K key) {
        Objects.requireNonNull(key);
        // 如果map没有包含此Key,则直接返回null
        if (!map.containsKey(key)) {
            return Optional.empty();
        }
        Node<K, V> node = map.get(key);
        // 将此节点删除并加入头部(头部数据最常用)
        list.remove(node);
        list.addHead(node);
        return Optional.ofNullable(node.value);
    }

    /
     * 放入缓存
     *
     * @param key   key
     * @param value value
     */
    public void put(K key, V value) {
        Objects.requireNonNull(key);
        // 看Map是否已经包含此Key,如果包含,则更新数据
        if (map.containsKey(key)) {
            Node<K, V> node = map.get(key);
            node.value = value;
            // 重新放入map中
            map.put(key, node);
            // 删除此节点并加入头部(头部数据最常访问)
            list.remove(node);
            list.addHead(node);
            return;
        }
        // 如果不包含,则判断容量是否已满
        if (map.size() >= capacity) {
            // 容量已满,则删除尾部节点的前节点数据(尾部最不常访问)
            Node<K, V> tail = list.tail();
            list.remove(tail);
            // 从map中也进行删除
            map.remove(tail.key);
        }
        // 创建新节点
        Node<K, V> newNode = new Node<>(key, value);
        // 放入头部(头部数据最常访问)
        list.addHead(newNode);
        // 添加到Map中
        map.put(key, newNode);
    }

    /
     * 打印节点数据
     */
    public void printNodes() {
        System.out.println(map);
    }

    /
     * 双向节点
     *
     * @param <K>
     * @param <V>
     */
    static class Node<K, V> {
        // key
        K key;
        // value
        V value;
        // 前节点
        Node<K, V> prev;
        // 后节点
        Node<K, V> next;

        public Node() {
            this.prev = this.next = null;
        }

        // 节点构造方法
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.prev = this.next = null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    '}';
        }
    }

    /
     * 双向链表
     *
     * @param <K>
     * @param <V>
     */
    static class LRULinkedList<K, V> {
        // 头节点
        private Node<K, V> head;
        // 尾节点
        private Node<K, V> tail;
        // 链表数据数量
        int size;

        public LRULinkedList() {
            this.head = new Node<>();
            this.tail = new Node<>();
            this.head.next = this.tail;
            this.tail.prev = this.head;
            this.size = 0;
        }

        /
         * 添加节点到头部
         *
         * @param node 节点
         */
        public void addHead(Node<K, V> node) {
            // 新节点的后节点是头节点的后节点
            node.next = head.next;
            // 头节点的后节点的前节点是新节点
            head.next.prev = node;
            // 头节点的后节点变更为新节点
            head.next = node;
            // 新节点的前节点为头节点
            node.prev = head;
            size++;
        }

        /
         * 添加节点到尾部
         *
         * @param node 节点
         */
        public void addTail(Node<K, V> node) {
            // 尾节点的前节点变为新节点的前节点
            node.prev = tail.prev;
            // 尾节点的前节点的后节点是新节点
            tail.prev.next = node;
            // 新节点的后节点是尾节点
            node.next = tail;
            // 尾节点的前节点变为新节点
            tail.prev = node;
            size++;
        }

        /
         * 删除节点
         *
         * @param node 节点
         */
        public void remove(Node<K, V> node) {
            // 删除节点的前节点的后节点变为删除节点的后节点
            node.prev.next = node.next;
            // 删除节点的后节点的前节点变为删除节点的前节点
            node.next.prev = node.prev;
            // 置空删除节点的前节点和后节点,方便GC回收
            node.next = null;
            node.prev = null;
            size--;
        }

        /
         * 获取尾节点数据(是尾节点的前一个)
         *
         * @return 节点
         */
        public Node<K, V> tail() {
            return tail.prev;
        }

        /
         * 是否为空
         *
         * @return 结果
         */
        public boolean isEmpty() {
            return this.size == 0;
        }
    }

    public static void main(String[] args) {
        CustomLRUCache<Integer, Integer> cache = new CustomLRUCache<>(2);
        cache.put(1, 1); // 缓存是 {1=1}
        cache.printNodes();
        cache.put(2, 2); // 缓存是 {1=1, 2=2}
        cache.printNodes();
        cache.get(1);    // 返回 1
        cache.put(3, 3); // 该操作会使得关键字 2 作废, 缓存是 {1=1, 3=3}
        cache.printNodes();
        cache.get(2);    // 返回 -1(未找到)
        cache.printNodes();
        cache.put(4, 4); // 该操作会使得关键字 1 作废, 缓存是 {4=4, 3=3}
        cache.printNodes();
        cache.get(1);    // 返回 -1(未找到)
        cache.get(3);    // 返回 3
        cache.printNodes();
        cache.get(4);    // 返回 4
        cache.printNodes();
    }
}