关于java:HashMap-vs-LinkedHashMap

8次阅读

共计 1680 个字符，预计需要花费 5 分钟才能阅读完成。

通过各类教科书，咱们能够总结 HashMap 和 LinkedHashMap 的区别：

LinkedHashMap 可放弃程序，HashMap 无奈放弃程序
数据量大、loadFactor 比拟小的时候，遍历 HashMap 比 LinkedHashMap 效率低、耗时
查找定位无差别，速度飞快，hash 值无抵触的状况下一步到位

理论对大多数利用场景来说，咱们只有记住第一个区别就能够了。如果某一场景要求依照存储时的程序获取数据，那咱们肯定要记得不能用 HashMap，必须用 LinkedHashMap。

本着二杆子程序员精力，咱们假如你肯定想晓得所以然。

所以咱们还是从两者底层数据结构开始剖析。

当初假如咱们把如下数据按程序别离放入到 HashMap 和 LinkeHashMap 中：

hm.put("Li si","45");   /** 节点 1 **/
hm.put("Zhang san","20");/** 节点 2 **/
hm.put("Zhao liu","70");/** 节点 3 **/
hm.put("Wang wu","30");/** 节点 4 **/

咱们心愿用下图来解释 HashMap 和 LinkeHashMap 在保留上述数据时的数据结构。当然，咱们只是为了阐明问题，hash 桶是随便调配的，理论调配的 hash 桶肯定不是这样的。

咱们假如存入节点 1 时 HashMap 失去的 hash 桶是 table[3], 所以节点 1 搁置在该桶中。

节点 2 取得的 hash 桶是 table[1], 并假如节点 3 与节点 2 的 hash 值抵触，也放入到 table[1] 中。节点 4 搁置在 table[15] 中。

由前两节的剖析咱们晓得，存放数据到 LinkedHashMap 中与存放数据到 HashMap 中的算法基本相同，因而其寄存到 table 数组中的地位、也就是获取到的 hash 桶是雷同的。

不同的是 LinkedHashMap 寄存在 table 数组中的对象是双向链表构造，通过 before 和 after 指针记录了上一节点和下一节点，上图简单明了的反馈了该构造。

须要留神的是，LinkedHashMap 用双向链表构造记录所有的节点，与是否产生 hash 抵触无关。

HashMap 和 LinkHashMap 对产生 hash 抵触后的解决形式是统一的：数据会搁置在同一个桶中、采纳单项链表（next 指向下一节点）构造进行记录。

你当然能够这么了解，HashMap（包含 LinkedHashMap）的 table 数组中只保留没有产生 hash 抵触的数据，产生 hash 抵触后的数据并没有保留在 table 数组中，只是通过 table 数组中的对象能够找到所有的其余抵触对象。

通过上述剖析，答案曾经不言而喻了，咱们再啰嗦一下。

第一点是：因为 HashMap 存储数据的时候是通过数据 key 值的 hash 值确定其在 table 数组中的存储地位，而不是程序寄存在 table 数组中的，所以存储是没有程序的。

如果你当初脑海中非要冒出来这样一个问题：那为啥不程序寄存、而非要去哈什么希？

那我只能弱弱的答复一下，HashMap 具备疾速获取数据的个性 …

第二点是：HashMap 键值遍历算法是顺次遍历 table 数组，并跳过空桶。

联合以上第一、第二点以及结构图，HashMap 不能放弃程序应该是不言而喻了。

第一点：LinkedHashMap 通过 table 数组与双向链表的形式保留数据，链表构造放弃了存储程序。
第二点：LinkedHashMap 遍历 key 值得算法是从 head 开始遍历链表直到 tail。所以咱们也能够看到，LinkedHashMap 不须要遍历空桶，是实打实的遍历，效率更高。

联合第一点、第二点以及结构图，LinkeHashMap 遍历 key 值时能放弃程序也是不言而喻的了。

顺便说一句，LinkedHashMap 这种 table 数组加双向列表的构造，可能达到：疾速程序遍历（应用双向链表）、疾速定位（通过 table 数组、hash 算法）。

真的是太 NB 了。

就到这儿了，再深入研究一段时间后，对于 HashMap，你就能够吊打面试官了。

正文完