最近最久未使用 如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小
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); } } }
