众所周知 HashMap 是一个无序的 Map，因为每次根据 key 的 hashcode 映射到 Entry数组上，所以遍历出来的顺序并不是写入的顺序。

因此 JDK 推出一个基于 HashMap 但具有顺序的 LinkedHashMap 来解决有排序需求的场景。

它的底层是继承于 HashMap 实现的，由一个双向链表所构成。

LinkedHashMap 的排序方式有两种：

根据写入顺序排序。

根据访问顺序排序。

其中根据访问顺序排序时，每次 get 都会将访问的值移动到链表末尾，这样重复操作就能的到一个按照访问顺序排序的链表。数据结构

1 @Test

2 public void test(){

3 Map

map = new LinkedHashMap

();

4 map.put("1",1) ;

5 map.put("2",2) ;

6 map.put("3",3) ;

7 map.put("4",4) ;

8 map.put("5",5) ;

9 System.out.println(map.toString());

10 }

调试可以看到 map 的组成：

​

打开源码可以看到：

1 /**

2 * The head of the doubly linked list.

3 */

4 private transient Entry

header;

5 /**

6 * The iteration ordering method for this linked hash map:

true

7 * for access-order,

false

for insertion-order.

8 *

9 * @serial

10 */

11 private final boolean accessOrder;

12 private static class Entry

extends HashMap.Entry

{

13 // These fields comprise the doubly linked list used for iteration.

14 Entry

before, after;

15 Entry(int hash, K key, V value, HashMap.Entry

next) {

16 super(hash, key, value, next);

17 }

18 }

其中 Entry 继承于 HashMap 的 Entry，并新增了上下节点的指针，也就形成了双向链表。

还有一个 header 的成员变量，是这个双向链表的头结点。

上边的 demo 总结成一张图如下：

​

第一个类似于 HashMap 的结构，利用 Entry 中的 next 指针进行关联。

下边则是 LinkedHashMap 如何达到有序的关键。

就是利用了头节点和其余的各个节点之间通过 Entry 中的 after 和 before 指针进行关联。

其中还有一个 accessOrder 成员变量，默认是 false，默认按照插入顺序排序，为 true 时按照访问顺序排序，也可以调用:

1 public LinkedHashMap(int initialCapacity,

2 float loadFactor,

3 boolean accessOrder) {

4 super(initialCapacity, loadFactor);

5 this.accessOrder = accessOrder;

6 }

这个构造方法可以显示的传入 accessOrder。构造方法

LinkedHashMap 的构造方法:

1 public LinkedHashMap() {

2 super();

3 accessOrder = false;

4 }

其实就是调用的 HashMap 的构造方法:

HashMap 实现：

1 public HashMap(int initialCapacity, float loadFactor) {

2 if (initialCapacity

MAXIMUM_CAPACITY)

6 initialCapacity = MAXIMUM_CAPACITY;

7 if (loadFactor <= 0 || Float.isNaN(loadFactor))

8 throw new IllegalArgumentException("Illegal load factor: " +

9 loadFactor);

10 this.loadFactor = loadFactor;

11 threshold = initialCapacity;

12 //HashMap 只是定义了改方法，具体实现交给了 LinkedHashMap

13 init();

14 }

可以看到里面有一个空的 init()，具体是由 LinkedHashMap 来实现的：

1 @Override

2 void init() {

3 header = new Entry<>(-1, null, null, null);

4 header.before = header.after = header;

5 }

其实也就是对 header 进行了初始化。put 方法

看 LinkedHashMap 的 put() 方法之前先看看 HashMap 的 put 方法：

1 public V put(K key, V value) {

2 if (table == EMPTY_TABLE) {

3 inflateTable(threshold);

4 }

5 if (key == null)

6 return putForNullKey(value);

7 int hash = hash(key);

8 int i = indexFor(hash, table.length);

9 for (Entry

e = table[i]; e != null; e = e.next) {

10 Object k;

11 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

12 V oldValue = e.value;

13 e.value = value;

14 //空实现，交给 LinkedHashMap 自己实现

15 e.recordAccess(this);

16 return oldValue;

17 }

18 }

19 modCount++;

20 // LinkedHashMap 对其重写

21 addEntry(hash, key, value, i);

22 return null;

23 }

24 // LinkedHashMap 对其重写

25 void addEntry(int hash, K key, V value, int bucketIndex) {

26 if ((size >= threshold) && (null != table[bucketIndex])) {

27 resize(2 * table.length);

28 hash = (null != key) ? hash(key) : 0;

29 bucketIndex = indexFor(hash, table.length);

30 }

31 createEntry(hash, key, value, bucketIndex);

32 }

33 // LinkedHashMap 对其重写

34 void createEntry(int hash, K key, V value, int bucketIndex) {

35 Entry

e = table[bucketIndex];

36 table[bucketIndex] = new Entry<>(hash, key, value, e);

37 size++;

38 }

主体的实现都是借助于 HashMap 来完成的，只是对其中的 recordAccess(), addEntry(), createEntry() 进行了重写。

LinkedHashMap 的实现：

1

2

3 //就是判断是否是根据访问顺序排序，如果是则需要将当前这个 Entry 移动到链表的末尾

4 void recordAccess(HashMap

m) {

5 LinkedHashMap

lm = (LinkedHashMap

)m;

6 if (lm.accessOrder) {

7 lm.modCount++;

8 remove();

9 addBefore(lm.header);

10 }

11 }

12 //调用了 HashMap 的实现，并判断是否需要删除最少使用的 Entry(默认不删除)

13 void addEntry(int hash, K key, V value, int bucketIndex) {

14 super.addEntry(hash, key, value, bucketIndex);

15 // Remove eldest entry if instructed

16 Entry

eldest = header.after;

17 if (removeEldestEntry(eldest)) {

18 removeEntryForKey(eldest.key);

19 }

20 }

21 void createEntry(int hash, K key, V value, int bucketIndex) {

22 HashMap.Entry

old = table[bucketIndex];

23 Entry

e = new Entry<>(hash, key, value, old);

24 //就多了这一步，将新增的 Entry 加入到 header 双向链表中

25 table[bucketIndex] = e;

26 e.addBefore(header);

27 size++;

28 }

29 //写入到双向链表中

30 private void addBefore(Entry

existingEntry) {

31 after = existingEntry;

32 before = existingEntry.before;

33 before.after = this;

34 after.before = this;

35 }

36

37

38get 方法

LinkedHashMap 的 get() 方法也重写了：

1

2

3 public V get(Object key) {

4 Entry

e = (Entry

)getEntry(key);

5 if (e == null)

6 return null;

7 //多了一个判断是否是按照访问顺序排序，是则将当前的 Entry 移动到链表头部。

8 e.recordAccess(this);

9 return e.value;

10 }

12 void recordAccess(HashMap

m) {

13 LinkedHashMap

lm = (LinkedHashMap

)m;

14 if (lm.accessOrder) {

15 lm.modCount++;

16 //删除

17 remove();

18 //添加到头部

19 addBefore(lm.header);

20 }

21 }

clear() 清空就要比较简单了：

1 //只需要把指针都指向自己即可，原本那些 Entry 没有引用之后就会被 JVM 自动回收。

2 public void clear() {

3 super.clear();

4 header.before = header.after = header;

5 }总结

总的来说 LinkedHashMap 其实就是对 HashMap 进行了拓展，使用了双向链表来保证了顺序性。

因为是继承与 HashMap 的，所以一些 HashMap 存在的问题 LinkedHashMap 也会存在，比如不支持并发等。欢迎关注，欢迎留言探讨