这是一个很经典的面试题
146. LRU 缓存 - 力扣（LeetCode）
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
这是一个设计数据结构的题
如果没有第三个要求，HashMap+List就可以是实现，
可是还需要O（1）的复杂度
可以使用双向链表加Hash表去解决，为什么要用hash表了，因为要快速判断这个key存在于这个链表，
解法一：自定义双向链表
class LRUCache3{private static class Node{int key,value;Node pre,next;public Node(int key,int value){this.key=key;this.value=value;}}private int capacity;private Node head=new Node(0,0);private HashMap<Integer,Node> map=new HashMap<>();public LRUCache3(int capacity) {this.capacity=capacity;head.pre=head;head.next=head;}public int get(int key){if(!map.containsKey(key)){return -1;}Node k=map.get(key);remove(k);add(k);return k.value;}public void put(int key,int value){if(map.containsKey(key)){Node node = map.get(key);node.value=value;remove(node);add(node);return ;}if(map.size()==capacity){Node last = head.pre;remove(last);map.remove(last.key);}add(new Node(key,value));}private void remove(Node k){k.pre.next=k.next;k.next.pre=k.pre;}private void add(Node k){k.pre=head;k.next=head.next;k.pre.next=k;k.next.pre=k;}
}解法二：使用LinkedHashmap 本身自带双向链表
LinkedHashMap
LinkedHashMap<Integer,String> linkedHashMap = new LinkedHashMap<>(16,0.75f,true);boolean accessOrder决定按什么排序，为true则为按访问顺序，为false则为插入顺序
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;}如果按照插入顺序写会固定不变，所以应该用true
class LRUCache2{// LinkedHashMap 最早是在上面， 最近使用的在下面。private int capacity;private LinkedHashMap<Integer, Integer> map;public LRUCache2(int capacity) {this.capacity = capacity;map = new LinkedHashMap<>();}public int get(int key) {Integer remove = map.remove(key);if(remove !=null ){map.put(key,remove);return remove;}return -1;}public void put(int key, int value) {if(map.remove(key)!=null){map.put(key,value);return ;}if(map.size()==capacity){map.remove(map.keySet().iterator().next());}map.put(key,value);}
}第三种 继承LinkedHashMap
class LRUCache extends LinkedHashMap<Integer, Integer>{private static final float DEFAULT_LOAD_FACTOR = 0.75f;private final int capacity;public LRUCache(int capacity) {super(capacity, DEFAULT_LOAD_FACTOR, true);this.capacity = capacity;}@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {return size() > capacity;}public int get(int key) {return super.getOrDefault(key, -1);}}
