概述

HashMap是无序的,即put的顺序与遍历顺序不保证一样.

LinkedHashMap是HashMap的一个子类,它通过重写父类的相关方法,实现自己的功能. 它保留插入的顺序. 如果需要输出和输入顺序相同时,就选用此类.

LinkedHashMap原理

LinkedHashMap是如何保证输入输出顺序的呢?

LinkedHashMap重写了 HashMap 的Entry元素,该Entry额外保存了上一个元素与下一个元素的引用,从而在哈希表的基础上又构成了双向链表,源码:

这个链表维护了一个双向链表,用于保存顺序.

用于指定按照什么顺序来维护链表:

1.构造函数

其构造函数就是调用HashMap的构造函数. 在HashMap的构造函数中,会调用 init() 方法(在介绍HashMap时介绍过),LindedHashMap 重写init()方法,在init()方法中进行相关初始化.

2.存储

LinkedHashMap并没有重写父类的put方法,而是重写了父类put方法中调用的其他方法来实现自己的功能,父类put方法如下:

LindedHashMap重写的方法如下:

3.读取

LinkedHashMap重写了父类的get方法:

实际在调用父类getEntry方法取得查找的元素后,在判断是否记录访问顺序. 由于链表的添加、删除操作都是常量级的,不会带来性能的损失.

4.排序模式

LindedHashMap定义了 boolean 型变量 accessOrder,若为true,按照访问顺序排序,若为false,按照插入顺序排序. 默认为 false;

其实LinkedHashMap几乎和HashMap一样,只是LinkedHashMap定义了一个 Entry元素header,通过header中的before,after和header结合建立一个双向链表,用来实现元素的顺序.