算法------手写LRU算法

超、凢脫俗 2024-03-31 16:11 32阅读 0赞

## 算法------手写LRU算法 ##

LRU是Redis中常用的内存淘汰算法。  
意思是：当缓存容量满的时候，淘汰最近很少使用的数据。  
具体实现逻辑： 把缓存放到双向链表当中，最近使用过、或新放入的缓存，放到队头，而最久未使用的数据，放在队尾巴。  
当容量满时，将队头数据指定为，最新的数据，将队尾数据移除。  
需要：双线链表（Node节点，头结点、尾结点，链表长度，以及链表总长度、和Map\[key\]value）  
map用于Node节点和Map的绑定，实现查找获取value的效率为O（1）。  
注意：每次新增或者删除、或者修改节点时，也都要同步更新到Map中。  
Node节点定义：  
Node节点的特性：  
1.该结点有一个头结点  
2.该结点有一个尾结点  
3.key  
4.value  
**【重点在于双向链表的构思、以及在匹配时，通过hashmap进行key、value值的存取，减少遍历，时间复杂度O（1）】**

/**
         * 定义节点
         * 节点数据为HashMap
         */
        public static class Node{
        
            //前一个节点
            public Node before;
            //后一个节点
            public Node after;
            //key值
            public Integer key;
            //value值
            public Integer value;
    
            public Node(Integer key,Integer value){
        
                this.key = key;
                this.value = value;
            }
            public Node(){
        }
        }

初始化链表方法：

/**
         * 初始化链表
         * 初始化长度、头结点和尾结点
         */
        public LRUcache(Integer capacity){
        
            this.capacity = capacity;
            this.head = new Node();
            this.tail = new Node();
            this.head.after = this.tail;
            this.tail.before = this.head;
            this.size = 0;
            this.cache = new HashMap<>(capacity+2);
        }

put方法，添加元素  
/\*\*  
\* put放入元素的方法  
\* 放入元素存在多种情况  
\* 1.链表中已存在当前元素 ，则覆盖原value，并且将当前元素放入队头  
\* 2.链表中没有元素  
\* 2.1 如果链表长度没满，则放入队头  
\* 2.2 如果链表长度已满，则删除队尾，放入队头  
\*/

/**
         * put放入元素的方法
         * 放入元素存在多种情况
         * 1.链表中已存在当前元素  ，则覆盖原value，并且将当前元素放入队头
         * 2.链表中没有元素
         * 2.1 如果链表长度没满，则放入队头
         * 2.2 如果链表长度已满，则删除队尾，放入队头
         */
        public void put(Integer key,Integer value){
        
            Node node = new Node(key,value);
            if (cache.containsKey(key)){
        
                // 覆盖原value，并且将当前元素放入队头
                Node node1 = cache.get(key);
                node1.value = value;
                //放入队头方法
                moveToHead(node);
            }else {
        
                //如果不存在则,需要判断size和capacity的大小
                if (size < capacity){
        
                    addNode(node);
                    size ++ ;
                }else {
        
                    Node lastNode = tail.before;
                    //删除尾结点
                    delete(lastNode);
                    cache.remove(lastNode.key);
                    //添加节点到头部
                    addNode(node);
                }
                cache.put(key,node);
            }
    
        }

取缓存：

/**
         * 取缓存
         */
        public Integer get(Integer key){
        
            if (cache.containsKey(key)){
        
                Node node = cache.get(key);
                Integer value = node.value;
                moveToHead(node);
                return value;
            }else {
        
                return -1;
            }
        }

完整代码：

package com.example.springboot01.Test;
    
    
    import java.util.HashMap;
    import java.util.Map;
    
    /**
     * 手写LRU算法
     */
    public class LRUcache {
        
        /**
         * 定义头结点和尾结点
         */
        Node head;
        Node tail;
        //缓存容量
        public int capacity;
        //当前缓存个数
        public int size;
        //和双向链表对应,降低查找key的复杂度
        Map<Integer,Node> cache = new HashMap<Integer,Node>();
        /**
         * 定义节点
         * 节点数据为HashMap
         */
        public static class Node{
        
            //前一个节点
            public Node before;
            //后一个节点
            public Node after;
            //key值
            public Integer key;
            //value值
            public Integer value;
    
            public Node(Integer key,Integer value){
        
                this.key = key;
                this.value = value;
            }
            public Node(){
        }
        }
    
        /**
         * 初始化链表
         * 初始化长度、头结点和尾结点
         */
        public LRUcache(Integer capacity){
        
            this.capacity = capacity;
            this.head = new Node();
            this.tail = new Node();
            this.head.after = this.tail;
            this.tail.before = this.head;
            this.size = 0;
            this.cache = new HashMap<>(capacity+2);
        }
        /**
         * put放入元素的方法
         * 放入元素存在多种情况
         * 1.链表中已存在当前元素  ，则覆盖原value，并且将当前元素放入队头
         * 2.链表中没有元素
         * 2.1 如果链表长度没满，则放入队头
         * 2.2 如果链表长度已满，则删除队尾，放入队头
         */
        public void put(Integer key,Integer value){
        
            Node node = new Node(key,value);
            if (cache.containsKey(key)){
        
                // 覆盖原value，并且将当前元素放入队头
                Node node1 = cache.get(key);
                node1.value = value;
                //放入队头方法
                moveToHead(node);
            }else {
        
                //如果不存在则,需要判断size和capacity的大小
                if (size < capacity){
        
                    addNode(node);
                    size ++ ;
                }else {
        
                    Node lastNode = tail.before;
                    //删除尾结点
                    delete(lastNode);
                    cache.remove(lastNode.key);
                    //添加节点到头部
                    addNode(node);
                }
                cache.put(key,node);
            }
    
        }
    
        /**
         * 放入队头 包括 断开原链接，以及放入队头
         * @param node
         */
        private void moveToHead(Node node) {
        
            delete(node);
            addNode(node);
    
        }
        //添加到头结点
        private void addNode(Node node) {
        
            //头结点后面的结点要指向头结点
            Node headAfter = head.after;
            headAfter.before = node;
            node.after = headAfter;
            //节点要指向头结点
            head.after = node;
            node.before = head;
        }
    
        //断开节点
        private void delete(Node node) {
        
            Node before = node.before;
            Node after = node.after;
            before.after = after;
            after.before = before;
        }
    
        /**
         * 取缓存
         */
        public Integer get(Integer key){
        
            if (cache.containsKey(key)){
        
                Node node = cache.get(key);
                Integer value = node.value;
                moveToHead(node);
                return value;
            }else {
        
                return -1;
            }
        }
    
        public static void main(String[] args) {
        
            LRUcache lrUcache = new LRUcache(3);
            lrUcache.put(5,6);
            lrUcache.put(7,8);
            lrUcache.put(9,10);
            System.out.println(lrUcache.get(5));
            lrUcache.put(3,4);
            Integer integer = lrUcache.get(7);
            System.out.println(integer);
        }
    }