鲸域科技一面

一面就是做题
设计一个LRUCache
•get (key)：获取指定key 的value 值（如果存在），并将该key 移动到最近使用的位置。。
•put (key, value)：插入一个新的key-value 对，如果插入前缓存已经满了，那么将最久未使用的 key-value 对删除。
•可输出缓存结构内所有key-value对。

package thread;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LRUCache {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(5);
        cache.put(1,1);
        cache.put(2,2);
        cache.put(3,3);

        System.out.println(cache.get(0));
        cache.put(4,4);
        cache.put(5,5);

        cache.put(6,6);

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

        cache.put(2,3);
    }

    private int capacity;
    private Map<Integer, Integer> cache;
    private LinkedList<Integer> keyOrder;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        keyOrder = new LinkedList<>();
    }

    public Integer get(int key) {
        if(!cache.containsKey(key)){
            return null;
        }

        // 移动最近使用的位置
        keyOrder.remove(key);
        keyOrder.addLast(key);

        return cache.get(key);
    }

    public void put(int key, int value) {
        if (cache.size() > 5) {
            return;
        }

        // 先判断key是否已存在
        if (cache.containsKey(key)){
            // 如果已经存在了，移动到最近的位置
            cache.put(key,value);
            keyOrder.remove(key);
            keyOrder.addLast(key);
        }else{
            if(cache.size() == capacity){
                // 满了就删除最久没使用过的
                int old = keyOrder.removeFirst();
                cache.remove(old);
            }

            cache.put(key,value);
            keyOrder.addLast(key);
        }

    }

}