参考文章

  • LinkedHashMap 源码详细分析（JDK1.8）

    继承关系

    LinkedHashMap 继承自 HashMap，其大部分方法都是直接使用或稍微修改 Hash Map 的方法，不同点在于它还维护了一个双向链表结构
    image.png

    数据结构

    底层由桶数组+链表或红黑树组成，并在此基础上维护了双向链表保证遍历的顺序性
    LinkedHashMap - 图2

    如何实现维护双向链表？

  1. 按照插入顺序维护双向链表

当 accessOrder = false 时（默认），按照插入顺序维护双向链表。LinkedHashMap 没有直接重写 put 或 putVal，remove 或 removeNode 方法，而是：

  • 在插入时：重写了 newNode(...)方法，将节点替换为内部类LinkedHashMap.Entry ，然后通过新增的 linkNodeLast(...)方法将插入的节点连接起来；
  • 在删除时：重写了 afterNodeRemoval(...)方法，HashMap 在实现时已经考虑到 LinkedHashMap 删除节点，因此在 removeNode(...)调用了此方法，只不过在 HashMap 中此方法的实现是空的
  1. 在上面的基础上，按照访问顺序维护双向链表

当 accessOrder = true 时，按照访问顺序维护维护双向链表，访问完指定的 key 之后会调用 afterNodeAccess(...)把此节点移动到链表尾部
LinkedHashMap - 图3

HashMap 为 LinkedHashMap 预留了哪些回调函数

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
1和3在上面已经介绍了用处了，2需要配合 removeEldestEntry(...)一起用，不过在 LinkedHashMap 中是不起作用的，需要子类继承后重写 removeEldestEntry(...)方法，并以实现不同策略的淘汰方法（e.g. 实现缓存的淘汰）