LinkedHashMap是如何实现有序的

1.LinkedHashMap有序

如果你用过HashMap那么肯定知道HashMap是不能保证有序性的，之所以HashMap不能保证有序性是因为存放数组位置的数据时根据hash函数决定的；但是有没有能够保证有序性的Map呢？那就是LinkedHashMap，下面我们通过代码来看一下HashMap的无序和LinkedHashMap的有序性。

HashMap无序

LinkedHashMap有序

LinkedHashMap一共有5个构造方法，其中有4个的构造方法都是指定了accessOrder为false，只有第一个可以自定义accessOrder的状态，accessOrder实际上就是指定排序的规则；如果accessOrder为false表示根据插入的顺序进行排序，当为true的时候表示根据获取排序。可看如下实例代码

插入顺序为45,55,53然后获取了55,45排序顺序变为53,44,45。

2.LinkedHashMap源码

同样在看源码之前我们先看一下LinkedHashMap的继承与实现关系图。可以看到LinkedHashMap继承HashMap，同时实现了Map接口。

LinkedHashMap对HashMap的newNode、afterNodeAccess、afterNodeInsertion方法进行都进行了重写，同时也对HashMap中的Node进行了重写增加了before和after字段。

回到LinkedHashMap的put方法。当我们debug进入到LinkedHashMap后实际上就是调用了HashMap的put方法。

在putVal中先判断Node是否需要为空，为空进行初始化，如果不为判断对应数组下标中是否有值，如果没有调用newNode方法。在newNode中调用linkNodeLast。

linkNodeLast拿到尾部节点。如果尾部为空直接把第一个当前节点设置为头和尾节点，如果不为空则拿到尾部节点同时将当前节点的before设置为尾部节点即前一个节点，而将前一个节点的after设置为当前节点。这个before和after是不是就是一个双向链表的意思。

在HashMap中实际上并没有对afterNodeInsertion方法进行任何实现，而在LinkedHashMap中做了具体的实现操作。但是在JDK8中不会执行，因为removeEldestEntry方法始终返回false。

实际上LinkedList能够实现有序就是因为重写了Node并增加了before和after字段，同时对newNode方法进行了重写，有序就是因为before和after字段

3.get方法

LinkedHashMap的get方法与HashMap中get方法的不同点也在于多了afterNodeAccess()方法。afterNodeAccess方法在执行时必须accessOrder为true，也就是必须是根据获取排序时才会执行。

详细看一下afterNodeAccess是怎么实现的，afterNodeAccess实际上就是把当前获取的节点的after和before进行重新变化，也就是移动到最后面去。

3.remove方法

reomve方法也直接使用了HashMap中的remove，LinkedHashMap重写了其中的afterNodeRemoval该方法在HashMap中没有具体实现，通过此方法在删除节点的时候调整了双链表的结构。

4.总结

LinkedHashMap之所以能保证有序性是因为在HashMap的Node基础上又增加了after和before字段，相当有又是一个双向链表来维护有序性。结构如下