LinkedHashMap的使用和内部实现

LinkedHashMap是HashMap的子类，它继承了HashMap大多数的优点，它和HashMap最大的不同点是，HashMap是无序的，而LinkedHashMap是有序的。

一、成员变量accessOrder

accessOrder是LinkedHashMap一个影响排序规则的变量，可以在构造参数中指定，默认是false。

• 当accessOrder是false时，表示插入顺序模式，LinkedHashMap内部保持元素插入的顺序，注：这种模式重复插入相同的key，不更新key的顺序。
• 当accessOrder是false时，表示访问顺序模式，LinkedHashMap内部保持元素访问的顺序，即最近访问的排后面，get，put，replace等操作都算访问，注：这种模式重复插入相同的key，会更新key的顺序。

二、removeEldestEntry方法

该方法用于控制在插入新节点后是否删除最年长的节点，在插入顺序的模式下就是最先插入的节点，在访问顺序的模式下就是最早访问的节点，默认是不删除。因为访问顺序模式的特性，再结合removeEldestEntry方法，LinkedHashMap经常会被用来实现LRU（Least recently used，最近最少使用）缓存。

三、LinkedHashMap内部有序的实现

LinkedHashMap对内部的节点进行了扩展，在每个节点内部添加了前驱和后驱节点的引用，在对Map进行put、get和remove操作时会同时更新操作节点的前驱和后驱节点，同时保存了全局的一个头部节点和尾部节点，这样在遍历的时候就能拿到链表头部节点然后按顺序遍历整个链表。

在HashMap中，专门为LinkedHashMap定义了三个方法，用于在插入、删除，访问节点后进行后续操作。

下面看看在HashMap插入键值对时，LinkedHashMap执行了哪些操作来维护链表顺序，首先重写了newNode方法，在插入节点时，将当前节点添加在链表尾部。

在HashMap的putVal方法中会调用newNode方法来生成新的节点，实际调用的是上面提到的LinkedHashMap中重写的newNode方法。

在HashMap的putVal方法的末尾会调用afterNodeInsertion，这个方法是在LinkedHashMap中实现的。

这个方法主要是用来调用removeEldestEntry，根据结果来确定是否要删除最年长的节点，这样就完成插入操作，并且维护了LinkedHashMap内部的顺序。