JDK源码系列-LinkedHashMap实现原理

• 前言
• 1、 LinkedHashMap原理剖析
• • 1.1、LinkedHashMap基本结构
  • 1.2、LinkedHashMap构造方法解析
  • 1.3、LinkedHashMap元素结构解析
  • 1.4、LinkedHashMap常用方法解析
  • • 1.4.1、`afterNodeInsertion(boolean evict)`方法
    • 1.4.2、`afterNodeRemoval(Node

为什么有了HashMap还需要LinkedHashMap，因为HashMap是通过hash的方式进行插入元素，所以迭代的时候并不是插入的顺序，有些场景下我们需要实现一个有序的Map，就比如LRU缓存策略，这个时候就可以使用LinkedHashMap，它内部维护了一个双向链表，能根据元素的访问顺序遍历或根据元素的插入顺序遍历。

1. LinkedHashMap相当于HashMap+LinkedList，这里它继承了HashMap所以拥有HashMap的所有特性。

1. 这里可以看出来它内部维护了一个双向链表，这里定义链表的头尾节点。
2. accessOrder定义了访问顺序，true表示最近最少使用次序，false示插入顺序。

1. 这里可以看到这些重载的构造方法都是会调用父类也就是HashMap的构造方法来进行初始化
2. 这里默认的都采用插入顺序来维持取出键值对的次序。

这里发现LinkedHashMap中的元素成Entry，继承自HashMap的Node，在其之上扩展出前后指针，用于双向链表存储所有的指针，而HashMap中的Node的next指针是用于桶中的链表。

插入元素会调用hashMap的put方法来进行插入的，在元素插入完成会HashMap会调用afterNodeInsertion方法，就调用到LinkedHashMap中具体的实现了。
在这个方法中会做元素的驱逐，步骤如下：

1. 如果evict为true，并且头节点不为空么，并且removeEldestEntry(默认是false，可以覆写)返回true表示驱逐最老的元素，那么就会调用HashMap#removeNode把这个节点删除。
2. 移除之后会调用afterNodeRemoval，会调用到LinkedHashMap中具体的实现，会做双线链表的移除。