LinkedHashMap的排序是如何实现的？

LinkedHashMap是如何实现排序的？

网上有个说法：

LinkedHashMap = HashMap + 双向链表

这个说法，对于我们快速理解LinkedHashMap很有启发性。LinkedHashMap不会去改变HashMap节点的性质，LinkedHashMap所做的，只是建立节点之间的联系，LinkedHashMap的增删改查操作，只是在HashMap的增删改查的基础上，进行head和tail指针的移动。

总之一句话：LinkedHashMap的所有操作，都是基于HashMap，对自己的双向链表的操作。

有点拗口，OK，再换一种说法大家理解一下：LinkedHashMap对HashMap进行了增强，如何增强呢？就是在HashMap上面套了一个双向链表。LinkedHashMap只操作自己维护的双向链表，对于复用HashMap的部分，LinkedHashMap不会做任何改变。为什么呢？因为LinkedHashMap是后来的功能，java的设计者们必须要保证，不能影响HashMap。为什么呢？其实和我们做项目是一个道理。因为大家生产上都用的是HashMap，你敢随便动老功能吗？

LinkedHashMap的排序是如何实现的？

LinkedHashMap定义了accessOrder变量，值为true表示按照访问顺序排序，值为false表示按照插入顺序排序。accessOrder的默认值为false，也就是按照插入顺序排序。

final boolean accessOrder;

什么是有序？我们这里讨论的有序，指的是插入的顺序。

一，按照访问顺序排序

按照访问顺序排序，指的是当调用get()方法查询一个元素后，LinkedHashMap会把该元素移到链表的尾部。

这里需要注意，最近最少使用算法LRU，Least Recently Used，就是基于LinkedHashMap的按访问顺序排序来实现的。

实现思路：LinkedHashMap重写了Map接口的get()方法，get()方法主要做了什么呢？其实就是把当前访问的节点，移到双向链表的尾部。具体细节就是指针的移动，这里不再详细说明，感兴趣的可以查看LinkedHashMap的源代码：先看get()方法，然后调用了afterNodeAccess()方法。

二，按照插入顺序排序

按照插入顺序排序，指的是根据调用put()方法插入元素的顺序来排序。这个是LinkedHashMap的默认排序方法。

按照插入顺序排序的实现，相对来说比较简单，每次调用put()方法插入元素时，都把这个元素放到双向链表的尾部，这样就是按照插入顺序排序。因为双向链表通过节点的head和tail保证有序。

思考：HashMap的单向链表有next指针，为什么不能保证有序？

答：因为单向链表只是发生hash碰撞时，存储具有多个相同hash值的数据结构。也就是说，只是桶内有序。但是HashMap的table数组是无序的，这个是按照哈希值来定位数组中的位置，并不是按照插入顺序排序的。

不过，从这点来看，HashMap也是“有序”的，只不过这里的“有序”不是插入时的顺序。

三，总结

LinkedHashMap继承自HashMap，复用了HashMap的很多方法，并且未改变HashMap的存储逻辑，只是加了指针，把元素串联了起来。

这里有个关键点：集合的迭代顺序，本质上是迭代器来决定的，因此LinkedHashMap还需要有自己的迭代器。关于这点，稍后完善。

下面来看一下源码。

LinkedHashMap的排序是如何实现的？

LinkedHashMap对Entry进行了扩展，增加了指针before和after。这样下来，LinkedHashMap的每个节点，就包含了6个属性：

hash：HashMap的键的hashcode，LinkedHashMap的键的hashcode。

key：该节点的键。

value：该节点的值。

next：单链表指针，HashMap专用。

before：双链表指针，LinkedHashMap专用。

after：双链表指针，LinkedHashMap专用。

LinkedHashMap的排序是如何实现的？

关于LinkedHashMap，有几点需要说明：

1，双向链表+哈希表。

2，非线程安全。

3，允许key为null，允许value为null。

4，有序。

最后附上网友的LinkedHashMap的结构图，方便理解。

LinkedHashMap的排序是如何实现的？