LRU缓存

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

解题思路：本题巧妙的使用linkedhashmap数据结构。linkedhashmap中使用了双向链表实现有序，其中有一个boolean字段accessOrder,默认为false,表示按照插入的顺序保持有序，如果为true，则表示按照访问的顺序保持有序。每次访问map中的元素时，被访问的元素会被插入到链表头，当容量超过map的指定容量时，删除链表头部的方法(即为最近最少使用的)。

首先设计一个map继承linkedhashmap

/**
 * @author jy
 * @date 2018年9月20日
 * <p>Description: </p> 
 */
package design;

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

/**
 * @author jy
 *
 */
public class LRULinkedHashMap<K,V> extends LinkedHashMap<K, V>{
    private int capacity;
    public LRULinkedHashMap(int capacity){
        super(capacity,0.75f,true);//按照访问顺序维护双向循环链表
        this.capacity=capacity;
    }
    
    /**
     * 当map中的容量超过指定的容量后，删除eldest
     */
    public boolean removeEldestEntry(Map.Entry<K, V> entry){
        if(this.entrySet().size()>capacity){
            return true;
        }
        return false;
        
    }
}

然后写自己的LRUCache

public class LRUCache {
   
   private LRULinkedHashMap<Integer, Integer> cache;
   public LRUCache(int capacity){
       cache=new LRULinkedHashMap<>(capacity);
   }
   public void set(int key,int value){
       cache.put(key, value);
   }
   
   public int get(int key){
       Integer value=this.cache.get(key);
       if(null == value){
           return -1;
       }
       return value;
   }
   

   /**
    * @param args
    *<p>Description: </p>  
    */
   public static void main(String[] args) {

       LRUCache cache=new LRUCache(3);
       cache.set(1, 1);
       cache.set(2, 2);
       cache.set(3, 3);
       
       int value1=cache.get(3);
       int value2=cache.get(2);
       int value3=cache.get(1);
       
       cache.set(4, 4);
       
       System.out.println(cache.get(1));
       System.out.println(cache.get(2));

       System.out.println(cache.get(3));
       System.out.println(cache.get(4));


   }

}

image.png