LinkedHashMap 底层原理？

逃离我推掉我的手 2023-03-06 03:52 2阅读 0赞

> https://www.cnblogs.com/xiaowangbangzhu/p/10445574.html

针对LinkedHashMap 的总结有一下几点

1.LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构。该结构由**数组和链表+红黑树** 在此基础上LinkedHashMap 增加了一条**双向链表**，保持遍历顺序和插入顺序一致的问题。

2. 在实现上，LinkedHashMap 很多方法直接继承自 HashMap（比如put remove方法就是直接用的父类的），仅为维护双向链表覆写了部分方法（get（）方法是重写的）。

3.LinkedHashMap使用的键值对节点是Entity 他继承了hashMap 的Node,并新增了两个引用，分别是 before 和 after。这两个引用的用途不难理解，也就是用于维护双向链表.

4.链表的建立过程是在插入键值对节点时开始的，初始情况下，让 LinkedHashMap 的 head 和 tail 引用同时指向新节点，链表就算建立起来了。随后不断有新节点插入，通过将新节点接在 tail 引用指向节点的后面，即可实现链表的更新

5.LinkedHashMap **允许使用null值和null键，** 线程是不安全的，虽然底层使用了双线链表，但是增删相快了。因为他底层的Entity 保留了hashMap node 的next 属性。

6.如何实现迭代有序？

重新定义了数组中保存的元素Entry（继承于HashMap.node)，该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表。仍然保留next属性，所以既可像HashMap一样快速查找，

用next获取该链表下一个Entry，也可以通过双向链接，通过after完成所有数据的有序迭代.

7.竟然inkHashMap 的put 方法是直接调用父类hashMap的，但在 HashMap 中，put 方法插入的是 HashMap 内部类 Node 类型的节点，该类型的节点并不具备与 LinkedHashMap 内部类 Entry 及其子类型节点组成链表的能力。那么，LinkedHashMap 是怎样建立链表的呢？

*虽然linkHashMap* 调用的是hashMap中的put 方法，但是linkHashMap 重写了，了一部分方法，其中就有

newNode(int hash, K key, V value, Node<K,V> e)
    linkNodeLast(LinkedHashMap.Entry<K,V> p)

这两个方法就是 第一个方法就是新建一个 linkHasnMap 的Entity 方法，而 linkNodeLast 方法就是为了把Entity 接在链表的尾部。

8.链表节点的删除过程

与插入操作一样，LinkedHashMap 删除操作相关的代码也是直接用父类的实现，但是LinkHashMap 重写了`removeNode()方法 afterNodeRemoval（）方法，该removeNode方法在hashMap 删除的基础上有调用了afterNodeRemoval 回调方法。完成删除。`

删除的过程并不复杂，上面这么多代码其实就做了三件事：

1.  根据 hash 定位到桶位置
2.  遍历链表或调用红黑树相关的删除方法
3.  从 LinkedHashMap 维护的双链表中移除要删除的节点