0. 前情提要
面试官： 你能手写个LRU缓存吗？
你： LRU是什么货色？（一脸懵逼状）
面试官： LRU全称Least Recently Used（最近起码应用），用来淘汰不罕用数据，保留热点数据。你写了5分钟，然而只写了个get和put办法体，外面逻辑切实不晓得咋写。
面试官： 明天的面试先到这吧，有其余面试咱们会再分割你。我信你个鬼，你个糟老头子坏滴很，还分割啥，凉凉了。
别放心，再有人问你LRU，就把这篇文章丢给他，保障当场发offer。
1. 实现思路
目标是把最不罕用的数据淘汰掉，所以须要记录一下每个元素的拜访次数。最简略的办法就是把所有元素按应用状况排序，最近应用的，移到开端。缓存满了，就从头部删除。
2. 应用哪种数据结构实现？
罕用的数据结构有数组、链表、栈、队列，思考到要从两端操作元素，就不能应用栈和队列。
每次应用一个元素，都要把这个元素移到开端，蕴含一次删除和一次增加操作，应用数组会有大量的拷贝操作，不适宜。
又思考到删除一个元素，要把这个元素的前一个节点指向下一个节点，应用双链接最合适。
链表不适宜查问，因为每次都要遍历所有元素，能够和HashMap配合应用。
双链表 + HashMap
3. 代码实现
import java.util.HashMap;import java.util.Map;/** * @author yideng */public class LRUCache<K, V> { /** * 双链表的元素节点 */ private class Entry<K, V> { Entry<K, V> before; Entry<K, V> after; private K key; private V value; } /** * 缓存容量大小 */ private Integer capacity; /** * 头结点 */ private Entry<K, V> head; /** * 尾节点 */ private Entry<K, V> tail; /** * 用来存储所有元素 */ private Map<K, Entry<K, V>> caches = new HashMap<>(); public LRUCache(int capacity) { this.capacity = capacity; } public V get(K key) { final Entry<K, V> node = caches.get(key); if (node != null) { // 有拜访，就移到链表开端 afterNodeAccess(node); return node.value; } return null; } /** * 把该元素移到开端 */ private void afterNodeAccess(Entry<K, V> e) { Entry<K, V> last = tail; // 如果e不是尾节点，才须要挪动 if (last != e) { // 删除该该节点与前一个节点的分割，判断是不是头结点 if (e.before == null) { head = e.after; } else { e.before.after = e.after; } // 删除该该节点与后一个节点的分割 if (e.after == null) { last = e.before; } else { e.after.before = e.before; } // 把该节点增加尾节点，判断尾节点是否为空 if (last == null) { head = e; } else { e.before = last; last.after = e; } e.after = null; tail = e; } } public V put(K key, V value) { Entry<K, V> entry = caches.get(key); if (entry == null) { entry = new Entry<>(); entry.key = key; entry.value = value; // 新节点增加到开端 linkNodeLast(entry); caches.put(key, entry); // 节点数大于容量，就删除头节点 if (this.caches.size() > this.capacity) { this.caches.remove(head.key); afterNodeRemoval(head); } return null; } entry.value = value; // 节点有更新就挪动到未节点 afterNodeAccess(entry); caches.put(key, entry); return entry.value; } /** * 把该节点增加到尾节点 */ private void linkNodeLast(Entry<K, V> e) { final Entry<K, V> last = this.tail; if (head == null) { head = e; } else { e.before = last; last.after = e; } tail = e; } /** * 删除该节点 */ void afterNodeRemoval(Entry<K, V> e) { if (e.before == null) { head = e.after; } else { e.before.after = e.after; } if (e.after == null) { tail = e.before; } else { e.after.before = e.before; } }}4. 其实还有更简略的实现
import java.util.LinkedHashMap;import java.util.Map;/** * @author yideng */public class LRUCache<K, V> extends LinkedHashMap<K, V> { // 最大容量 private final int maximumSize; public LRUCache(final int maximumSize) { // true代表按拜访程序排序，false代表按插入程序 super(maximumSize, 0.75f, true); this.maximumSize = maximumSize; } /** * 当节点数大于最大容量时，就删除最旧的元素 */ @Override protected boolean removeEldestEntry(final Map.Entry eldest) { return size() > this.maximumSize; }}