LRUCache

港控/mmm° 2022-09-26 03:17 137阅读 0赞

**要求：**

设计并实现一个LRU缓存的数据结构，支持get和set操作  
capacity 缓存数量

get(key)：若缓存中存在key，返回对应的value，否则返回-1

set(key,value):若缓存中存在key，替换其value，否则插入key及其value，如果插入时缓存已经满了，应该使用LRU算法把最近最久没有使用的key踢出缓存。

package test;
    
    import java.util.LinkedHashMap;
    import java.util.Map;
    import java.util.Scanner;
    
    public class LRUCache {
    	
        private int capacity;
        private Map<Integer, Integer> cache;
     
        public LRUCache(final int capacity) {
            this.capacity = capacity;
            this.cache = new LinkedHashMap<Integer, Integer> (capacity, 0.75f, true) {
                // 定义put后的移除规则，大于容量就删除eldest
                protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                    return size() > capacity;
                }
            };
        }
     
        public int get(int key) {
            if (cache.containsKey(key)) {
                return cache.get(key);
            } else
                return -1;
        }
     
        public void set(int key, int value) {
            cache.put(key, value);
        }
        public static void main(String[] args) {
        	
    		Scanner scan = new Scanner(System.in);
    		int c = scan.nextInt();
    		LRUCache l = new LRUCache(c);
    		String s =scan.nextLine();
    		while(scan.hasNext()){
    			s = scan.nextLine();
    			String[] s1 = s.split(" ");
    			int key = Integer.parseInt(s1[0]);
    			if(s1.length ==2){
    				int value= Integer.parseInt(s1[1]);
    				l.set(key, value);
    			}else if(s1.length ==1){
    				System.out.println(l.get(key));
    			}
    		}
    
    	}
    }

1. 构造函数参数：0.75表示hashmap数量达到0.75比重时，扩容2倍；true表示链表顺序是访问顺序。  
2. removeEldestEntry方法，回收策略的重写方法。  
输入

100 100

200 200

300 300

100 100

400 400

100

200

300

500

输出

100