[数据结构与算法]0X02 LRU算法

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

/**
 * 0X02 LRU算法
 * @author Green.Gee
 * @date 2022/4/24 9:47
 * @email green.gee.lu@gmail.com
 */
public class SolveQ8 {

    public static void main(String[] args) {
        //System.err.println(LRU_LINKEDHASHMAP(1));
        /**
         * 关于数据申请范围是2的倍数的设计思路
         *         2的倍数  - 1 的二进制方式一定是全部是1
         *              15 = 二进制 1111
         *              全部是1进行&运算之后一定是奇数
         *              如果是非2的倍数则二进制末尾一定是0，任何&运算都是偶数
         *         这样会导致三列分布不均匀
         */
        LRUCache chche = new LRUCache(3);
        chche.put(1,11);
        chche.put(2,22);
        chche.put(3,33);
        chche.put(1,111);
        System.err.println(chche.get(1));
    }




    /**
     * LinkedHashMap
     *      LRU
     */
    public static Object LRU_LINKEDHASHMAP(Object key){
        LinkedHashMap<Object, Object> objectObjectLinkedHashMap = new LinkedHashMap<Object, Object>(2);
        objectObjectLinkedHashMap.put(1,"zhangsan");
        objectObjectLinkedHashMap.put(2,"lisi");
        objectObjectLinkedHashMap.put(3,"wangwu");
        return objectObjectLinkedHashMap.get(key);
    }
}

/**
 * LRU 实现
 */
class LRUCache{

    Map<Integer,Node> map = new HashMap<>(8);// 非线程安全
    DoubleList doubleList;
    int maxSize;
    public LRUCache(int capacity){
        doubleList = new DoubleList();
        maxSize = capacity;
    }

    /**
     * 获取缓存
     *  如果命中则更改当前缓存的LRU
     *  为命中则nothing
     * @param key
     * @return
     */
    public int get(int key){
        int val;
        if(!map.containsKey(key)){
            return -1;
        }
        val = map.get(key).value;
        // LRU
        Node team = map.get(key);// 获取节点信息
        doubleList.deleteNode(team);// 删除链表中的缓存
        doubleList.add(team);// LRU 位置
        // return cache value
        return val;
    }

    /**
     * 缓存存取
     *
     */
    public void put(int key,int value){
        if(map.containsKey(key)){
            //删除双链表原始位置缓存
            Node deleteNode = map.get(key);
            doubleList.deleteNode(deleteNode);// 维护最远未被使用
        }
        if(maxSize == doubleList.length){// max
            Node first = doubleList.head.next;//
            map.remove(first.key);// 删除缓存
            doubleList.deleteFirst();// 删除双链表第一个
        }
        // 增加LRU 最新缓存
        Node node = new Node(key,value);
        map.put(key,node);
        doubleList.add(node);
    }

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

    class DoubleList{
        private Node head;
        private Node tail;
        private int length;
        public DoubleList(){
            head = new Node(-1,-1);
            tail = head;
            length = 0;
        }

        // 添加 默认尾巴节点
        void add(Node teamNode){
            tail.next = teamNode;
            teamNode.pre = tail;
            tail = teamNode;
            length++;
        }

        // 删除第一
        void deleteFirst(){
            if(head.next == null)
                return;
            if(head.next == tail)
                head = tail;
            head.next = head.next.next;
            if(head.next != null)
                head.next.pre = head;
            length--;
        }

        // 删除节点
        void deleteNode(Node teamNode){
            teamNode.pre.next = teamNode.next;
            if(teamNode.next != null)
                teamNode.next.pre = teamNode.pre;
            if(teamNode == tail)
                tail = tail.pre;
            teamNode.pre = null;
            teamNode.next = null;
            length--;
        }
    }
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖