LRU算法和实现

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

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

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

2.相关代码

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;
    }

}

3.LRU的缺点

当偶尔有冷数据被读取时，它便会被加入头节点，只有当所有尾部节点都被读取或超长移除时才会淘汰掉它，会造成空间的浪费。在此可以加入次数的限制，只有超过某个调用次数时才会将数据加入到某个范围，例如超过一次则被加入三分之二缓存处，超过三次则被加入头节点，当然会带来并发相关的问题。