利用HashMap和LinkedList实现LRU

梦里梦外; 2021-09-27 09:56 249阅读 0赞

利用HashMap和LinkedList实现最近最久未使用算法  
java类库中包含LinkedHashMap用于实现LRU最好不过了，LinkedHashMap底层是就是HashMap和LinkedList，根据需要，LinkedList中可以保存访问的顺序或者插入的顺序，并且可以移除最老的节点。但是根据实际需要，判断最老的节点方式并不相同，因此，自己实现比较好。  
昨天遇到的一个问题是：  
实现一个LRU， 容量为n，put时不更新顺序，get时更新顺序。  
如：  
2 //容量  
p 1 1 //put 1 1  
p 2 2 //put 1 1  
g 1 // 输出1  
p 2 102 //将2对应的内容更新为102  
p 3 3 //将3放到缓存中，此时缓存区满，需将最近最久未使用的调出来 置换掉  
g 2 // 2是最近最久未使用，因此此时应该不存在2 输出 -1

import java.util.*;
    
    /** * Created by zfr on 2018/09/04. */
    class LRUCache{
        private int capacity;
        private Map<Integer,Integer> cache ;
        LinkedList<Integer> list;
        public LRUCache(int capacity){
            this.capacity = capacity ;
            this.cache = new HashMap<>();
            this.list = new LinkedList<>();
        }
        //添加元素
        public void put(Integer key , Integer value ){
            cache.put(key,value);
            if(!list.contains(key)){
                list.add(key);
            }
            afterPut(key,value);
        }
        //获取元素
        public int get(Integer key ){
            if(cache.containsKey(key)){
                afterGet(key);
                return cache.get(key);
            }else {
                return -1 ;
            }
        }
    
        //使用元素之后
        public void afterGet(Integer key ){
            list.remove(key);//移除现有元素，将其添加到最后
            list.addLast(key);
        }
    
        //添加元素后
        //超过长度后则移除最久未使用的函数
        public void afterPut(Integer key , Integer value ){
            if(cache.size() > capacity){
                Integer oldKey = list.getFirst();
                list.removeFirst();
               // System.out.println("old "+oldKey);
                cache.remove(oldKey);
            }
        }
    }
    public class LRU_Test {
        public static void main(String args[]){
            Scanner scanner = new Scanner(System.in);
            int n = Integer.valueOf(scanner.nextLine()) ;//容量
            LRUCache lru = new LRUCache(n);
            while (scanner.hasNextLine()){
                String[] str = scanner.nextLine().split(" ");
                String op = str[0] ;
                if(op.equals("p")){
       //put
                    int key = Integer.valueOf(str[1]);
                    int value = Integer.valueOf(str[2]);
                    lru.put(key,value);
                }else {
                    int key = Integer.valueOf(str[1]);
                    int value = lru.get(key);
                    System.out.println(value);
                }
            }
        }
    
    }

输入输出如下：

> 2  
> p 1 1  
> p 2 2  
> g 1  
> 1  
> p 2 102  
> p 3 3  
> g 1  
> 1  
> g 2  
> \-1