题解 | #设计LRU缓存结构#

解法一：使用双向链表（Linkedlist)+数组实现（数组arr[0]为key,arr[1]为value）。 需要了解的是，每次访问到的数据需要放到链表最前面，无论这个访问是get或是set，那么在set或者get进行之前，首先去缓存中查找是否已经有这个key。对于set操作：缓存中已经有key的情况下，需要把缓存原来的位置清空，然后把key-value放在链表头，没有key直接放在表头。对于get操作那就比较简单了，直接去链表中查询即可，命中也同样先清空数据并插入到表头。

public class Solution {
    List<int[]>list = new LinkedList<int[]>();
    int capacity = 0;
    public Solution(int capacity) {
        this.capacity = capacity;
    }
    public int get(int key) {
        for(int i=0;i<capacity&&i<list.size();++i){
            int [] temp = list.get(i);
            if(temp[0]==key){
                list.remove(i);
                list.add(0,temp);
                return temp[1];
            }
        }
        return -1;
    }
    public void set(int key, int value) {
        for(int i = 0;i<capacity&&i<list.size();++i){
            if(list.get(i)[0]==key){
                int[]temp = list.get(i);
                list.remove(i);
                temp[1] = value;
                list.add(0,temp);
                return ;
            }
        }
        list.add(0,new int[]{key,value});
        return ;
    }
}

方法二：采用有序哈希（可以避免查找时的遍历情况）。LinkedHashSet会根据插入的先后进行一个排序，这种方法相比于使用链表的方式，只需要在超出容量时，把老数据remove即可（可以使用迭代器或者Entry获得超出那一部分数据）。

public class Solution {
    Map<Integer,Integer> map = new LinkedHashMap<>();
    int capacity = 0;
    public Solution(int capacity) {
        this.capacity = capacity;
    }
    public int get(int key) {
        if(map.containsKey(key)){
            int value = map.get(key);
            map.remove(key);
            map.put(key,value);
            return value;
        }
        return -1;
    }
    public void set(int key, int value) {
        if(map.containsKey(key))
            map.remove(key);
        map.put(key,value);
        if(map.size()>capacity){
            List<Map.Entry<Integer,Integer>> list = new ArrayList<>(map.entrySet());
            for(int i=0;i<=map.size()-capacity;++i){
                map.remove(list.get(i).getKey());
            }
        }
        
        return ;
    }
}