LRU页面缓存淘汰算法实现

LRU页面缓存淘汰算法，由于内存较为可贵，所以在系统设计中要秉持着将热数据长久存在内存缓存中而冷数据则被淘汰掉的思想，常见应用场景为数据库的缓存页。实质上是对数据进行操作的时候，查询缓存中是否存在，如果存在则将其位置调整到缓存头部，如果不存在则存入缓存并将其放入缓存头部。当放入缓存时超过指定的缓存大小则淘汰掉缓存数据最尾部的数据。

1.实现方式和各自的优劣

1. 使用数组实现，数组检索速度比较快，但是增删速度比较慢而LRU算法可能会频繁的进行在缓存中增删的操作，所以在此并不推荐。
2. 使用双向链表实现，但是链表检索效率极其低下，而LRU本质上还是要查询选定内容是否存在缓存中，所以在此也不推荐。
3. 通过Hash表加双向链表的方式进行数据存储，使用Hash表的key存放需要缓存的数据唯一标记，用val存放双向链表的节点信息，而双向链表的节点中保存数据以及它的前置、后置节点信息。

相关代码

package com.peachl.demo.lru;

import cn.hutool.core.util.ObjectUtil;
import lombok.Data;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: peach l
 * @date: 2022-09-20  17:21
 * @description:
 */
// TODO 可以针对synchronized进行优化，可以提升部分效率
@Data
public class CustomCache<T> {

    // 游标
    private static Integer index;
    // 缓存最大长度
    private static Integer maxSize;

    private Node<T> first = new Node<>();
    private Node<T> last = new Node<>();

    private Map<Integer, Node> cache;


    private static class Node<T> {
        private Node<T> pre;
        private Node<T> next;
        private Integer key;
        private T data;

        public Node() {
        }

        public Node(Integer k, T obj) {
            key = k;
            data = obj;
        }

    }

    // 初始化CustomCache
    public CustomCache() {
        first.next = last;
        last.pre = first;
        maxSize = 3;
        index = 1;
        cache = new HashMap<>();
    }


    // 存
    public synchronized Map put(Integer id, T obj) {
        Node oldNode = cache.get(id);
        if(ObjectUtil.isEmpty(oldNode)) {
            // 判断是否超长，超长则删除最后的元素
            if(index > maxSize) {
                removeLast();
            }

            Node<T> newNode = new Node<>(id, obj);
            // 如果是首次插入需要初始化first和last
            if(index.equals(1)) {
                first = newNode;
                last = newNode;
            } else {
                moveToHead(newNode);
            }
            index++;
            cache.put(id, newNode);
        } else {
            ifExisted(oldNode);
        }

        return cache;
    }

    // 拿
    public synchronized Object get(Integer id) {
        // 获取缓存
        Node oldNode = cache.get(id);
        if(ObjectUtil.isNotEmpty(oldNode)) {

            // 当不是第一个时才会进行解除绑定和移到最前面的效果
            ifExisted(oldNode);

            return oldNode.data;
        }
        return null;
    }

    // 如果存在则进行解除和移动两部操作
    private void ifExisted(Node oldNode) {
        // 当不是第一个时才会进行解除绑定和移到最前面的效果
        if (!oldNode.equals(first)) {
            // 解除原有绑定
            unbind(oldNode);
            // 移动到最前方
            moveToHead(oldNode);
        }
    }

    // 解除当前节点绑定的所有其他节点
    private void unbind(Node node) {
        // 解除原有绑定
        if(!node.equals(first)) {
            node.pre.next = node.next;
        }
        if(ObjectUtil.isEmpty(node.next)) {
            last = node.pre;
        } else {
            node.next.pre = node.pre;
        }
    }

    // 移动指定节点到缓存头部
    private void moveToHead(Node node) {
        first.pre = node;
        node.next = first;
        first = node;
    }

    // 移除缓存尾部最后一位数据
    private void removeLast() {
        cache.remove(last.key);
        last.pre.next = null;
        last = last.pre;
    }

    // 迭代
    public void iterator() {
        if(ObjectUtil.isNotEmpty(first)) {
            iterator(first);
        } else {
            System.out.println("collection is empty");
        }
    }

    // 迭代递归方法体
    private Node iterator(Node node) {
        if(ObjectUtil.isNotEmpty(node.next)) {
            return iterator(node.next);
        }
        return null;
    }

}