线索：
1. LinkedHashMap 结构
2. 使用 LinkedHashMap 实现 LRU：按访问顺序和按插入顺序
1. LinkedHashMap 的结构。
HashMap 是使用链表法来解决散列冲突的，并且是单链表。在 LinkedHashMap 中，Entry 继承自 Node，是一个双向链表。
// 以下来自HashMapstatic class Node<K,V> implements Map.Entry<K,V> {Node<K,V> next;
// 以下来自LinkedHashMaptransient LinkedHashMap.Entry<K,V> head; // The head (eldest) of the doubly linked list.transient LinkedHashMap.Entry<K,V> tail; // The tail (youngest) of the doubly linked list.static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after;
复制代码
而 LinkedHashMap 继承自 HashMap，LinkedHashMap 并没有覆盖 HashMap 的 put 方法，使用的是 HashMap 的 put 方法。
而在 HashMap 的 putVal()方法中，预留了如下三个扩展点给 LinkedHashMap 去实现。
// Callbacks to allow LinkedHashMap post-actionsvoid afterNodeAccess(Node<K,V> p) { }void afterNodeInsertion(boolean evict) { }void afterNodeRemoval(Node<K,V> p) { }
复制代码
因此，插入的节点，即会保存在 HashMap 的单链表中，又会保存在 LinkedHashMap 的双向链表中。
如下所示，与散列表相连的“拉链”是用以解决散列冲突的。而“绕来绕去”的双向链表用于维护访问的时间顺序。
2. LRU 缓存淘汰算法。
缓存的大小是有上限的，因此，当缓存被用满的时候，就得清除掉一些数据。决定哪些数据应该被清理掉，哪些应该被保留，这就是缓存淘汰算法。
常见的策略有：
LFU 是按照总次数的最少使用，而 LRU 是时间上的最近最常使用和最不常使用。
3. 使用 LinkedHashMap 实现 LRU：按访问顺序和按插入顺序。
需要注意，LinkedHashMap 可以实现 LRU 淘汰算法，但如果没有自定义淘汰策略，那么 LinkedHashMap 与 HashMap 的区别仅仅是多了两个顺序：访问顺序和插入顺序。此外，只有控制好访问操作，我们同样可以使用单链表或数组实现 LRU
// accessOrder = true, 类似于get的访问操作会改变node的顺序（可以构建遍历顺序等于访问顺序）// accessOrder = false, 类似于get的访问操作并不会改变节点的顺序，即节点按插入顺序排序（可以构建变量顺序等于添加顺序）
LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<String, String>( 16, 0.75f, false){ @Override protected boolean removeEldestEntry(Map.Entry eldest) {// 实现自定义删除策略，否则行为就和普遍Map没有区别 return size() > 3; }};
linkedHashMap.put("1", "1");linkedHashMap.put("2", "2");linkedHashMap.put("3", "3");
linkedHashMap.get("1");linkedHashMap.get("2");linkedHashMap.put("4", "4");for (Map.Entry entry : linkedHashMap.entrySet()) { System.out.println(entry.getKey() + " : " + entry.getValue());}
// 越后面是越先被访问的// 如果accessOrder = true：1 : 12 : 24 : 4
// 如果accessOrder = false：2 : 23 : 34 : 4
复制代码
评论