最近最久未使用 如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小
1.用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。

2.利用一个链表来实现，每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃。

3.利用链表和hashmap。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。

对于第一种方法， 需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。对于第二种方法，链表在定位数据的时候时间复杂度为O(n)。所以在一般使用第三种方式来是实现LRU算法。 实现方案

4.使用LinkedHashMap实现
LinkedHashMap底层就是用的HashMap加双链表实现的，而且本身已经实现了按照访问顺序的存储。此外，LinkedHashMap中本身就实现了一个方法removeEldestEntry用于判断是否需要移除最不常读取的数，方法默认是直接返回false，不会移除元素，所以需要重写该方法。即当缓存满后就移除最不常用的数。

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}

class LRUCache {
    // 最大容量
    int cap;
    // LUR的关键：哈希链表 
    LinkedHashMap<Integer,Integer> cache = new LinkedHashMap<>();

    public LRUCache(int capacity) {
        this.cap = capacity;
    }
    
    public int get(int key) {
        if (!cache.containsKey(key)){
            return -1;
        }
        // 调用了，所以把key置为最近使用
        makeRencently(key);
        return cache.get(key);

    }
    
    public void put(int key, int value) {
        // 如果已经包含key，先修改key的值，再将它变为最近使用
        if(cache.containsKey(key)){
            // 修改key的值（因为key的唯一性，放入的时候回自动覆盖原来的value）
            cache.put(key,value);
            // 再将它变为最近使用
            makeRencently(key);
            return;
        }
        // 如果超过了储存量，则删除头节点（因为实现的是尾插入，所以头结点就是最久没有用的，删去）
        if (cache.size() >= this.cap){
            // 获取头结点
            // Map中所有的键存入到set集合中。因为set具备迭代器。所有可以迭代方式取出所有的键
            // 使用.iterator()迭代器后的指针其实指向的是第一个元素的上方，即指向一个空
            // .next()指针下移一位，指向头节点。hasNext方法的，判断下一个元素的有无，并不移动指针
            int oldestKey = cache.keySet().iterator().next();
            //删去头结点
            cache.remove(oldestKey);
        }
        // 放入，将新的key添加到链表尾部
        cache.put(key,value);
    }
    
    // 将节点移到链表尾部，变为最近使用
    public void makeRencently(int key){
        // 获取key对应的值
        int val = cache.get(key);
        // 删除key,重新插入队尾
        cache.remove(key);
        cache.put(key,val);
    }
}

==============================================

注意、以上都不是面试官想要看到的，需要自己实现双向链表+hashmap的映射关系。

只需要三步：
1.构建Node节点
2.构建双向链表
3.构建hashmap映射

一、Node节点

// 一、节点类
class Node {
    public int key, val;
    public Node next, prev; //下一个和前面一个
    public Node (int key, int val) {
        this.key = key;
        this.val = val;
    }
}

// 二、双端链表
class DoubleLinked {
    private Node head, tail;//头结点和尾结点
    private int size;//链表的元素数目

    public DoubleLinked() {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    // 在头部插入node结点
    public void addFirst(Node x) {
        x.prev = head;
        x.next = head.next;

        head.next.prev = x;
        head.next = x;
        size++;
    }

    // 移除指定结点
    public void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size--;
    }

    // 删除链表的第一个结点，并返回该结点
    public Node removeLast() {
        if(head.next == tail) return null;//返回空

        Node last = tail.prev;
        remove(last);//删除尾结点；
        return last;
    }

    public int size() {
        return size;
    }
}

// 三、构造hashMap映射
class LRUCache {
    HashMap<Integer, Node> map;
    DoubleLinked linked;
    int cap; //容量

    public LRUCache(int capacity) {
        map = new  HashMap<>();
        linked = new DoubleLinked();
        this.cap = capacity;
    }

    public int get(int key) {
        if(!map.containsKey(key)) return -1;
        int val = map.get(key).val;
        put(key, val);//放入头结点
        return val;
    }

    public void put(int key, int value) {
        Node x = new Node(key, value);
        if(map.containsKey(key)) {
            linked.remove(map.get(key));//移除结点
            linked.addFirst(x);
            map.put(key, x);
        }else {
            if(cap == cache.size()) {
                Node last = linked.removeLast();
                map.remove(last.key);
            }
            linked.addFirst(x);
            map.put(key, x);
        }
    }
}