LRU算法实现--最近最少使用

淡淡的烟草味﹌ 2022-10-16 09:56 220阅读 0赞

## 实现缓存 ##

要求：

*  LinkedHashMap
    
     *  HashMap（保证查找操作为O(1)）
     *  双向Link（保证排序、新增操作为O(1)）

## LRU算法实现 ##

1.  实现代码：
    
    使用HashMap和双向链表实现功能，增删操作时链表和Map的信息需要同步。
    
    (1) 先定义一个Node对象链表
    
        public class Node{
              
             public String key;
             public String value;
             //用双向链表储存
             public Node pre;
             public Node next;
        
             public Node(String key,String value){
              
                 this.key = key;
                 this.value = value;
             }
         }
    
    (2) 实现LRU缓存
    
        class LRUCache{
              
            //先定义链表头部和尾部
            private Node head;
            private Node end;
            
            //缓存上限
            private int limit;
            //使用HashMap 存放key、value。map的key值就是node的key值，这样便于查询。
            private HashMap map;
            public LRUCache(int limit){
              
                this.limit = limit;
                map = new HashMap();
            }
            
            public String get(String key){
              
                Node node = (Node) map.get(key);
                if(null == node){
              
                    return null;
                }
                
                //调整node到尾部
                refreshNode(node);
                return node.value;
            }
            
            public put(String key,String value){
              
                Node node = (Node) map.get(key);
                if(null == node){
              
                    //key值不存在，则直接插入至尾部
                    //先判断缓存空间是否等于limit
                    whilr(limit <= map.size()){
              
                        //先删除头部的node:head
                        String oldKey = removeKey(head);
                        //删除map的缓存
                        map.remove(oldKey);
                    }
                    node = new Node(key,value);
                    //将新节点node插入
                    addNode(node);
                    //map中插入节点
                    map.put(key,node);
                }else{
              
                    //key值存在，更新value然后调整node至尾部
                    node.value = value;
                    refreshNode(node);
                }
            }
            
            private vode refreshNode(Node node){
              
                //如果是尾部节点end,就不用移动了
                if(end == node){
              
                    return ;
                }
                
                //先删除，在增加
                removeNode(node);
                addNode(node);
            }
            
            private String removeNode(Node node){
              
                //尾节点end和头节点head需要分开处理
                if(end == node){
              
                    end = end.pre;
                }else if(head == node){
              
                    head = head.next;
                }else{
              
                    //中间普通节点
                    node.pre.next = node.next;
                    node.next.pre = node.pre;
                    
                }
                return node.key;   
            }
            
            private void addNode(Node node){
              
                //如果链表为空，直接成为head
                if(null = head){
              
                    head = node;
                    end = node;
                    return;
                }
                if(end != null)
                {
              
                    //将node调整为最后一个
                 	end.next = node;
                    node.pre = end;
                    npde.next = null;
                    end = node;
                    return;
                }     
            }
            
        }