LinkedHashMap源码解析：插入有序的秘密

"LinkedHashMap是Java集合框架中的一个特殊HashMap，它不仅保留了HashMap的基本功能，还额外维护了元素的插入顺序。" 在Java编程中，`LinkedHashMap`是`HashMap`的一个子类，具备`HashMap`的所有特性，同时增加了两个关键特征：保持插入顺序和访问顺序。`LinkedHashMap`通过内部的双向链表结构实现这一特性，每个节点包含`before`和`after`引用，用于链接前后节点，形成一个循环链表。这使得在遍历`LinkedHashMap`时，元素会按照它们被插入或访问的顺序进行。 1. **继承体系**： `LinkedHashMap`继承自`HashMap`，因此它继承了`HashMap`的高效查找和哈希碰撞处理能力。`HashMap`中的每个元素都是一个`Node`，而`LinkedHashMap`中的`Node`是`HashMap.Node`的子类，扩展了`before`和`after`属性，以支持双向链表的结构。 2. **属性**： - **双向链表头（最老）**：这是链表的第一个元素，表示最早插入的节点。 - **双向链表尾（最小）**：这是链表的最后一个元素，通常是最小键值对，但不保证一定是。 - **accessOrder**：布尔值，决定按照插入顺序还是访问顺序进行迭代。默认为`false`，表示按照插入顺序。 3. **构造方法**： - **无参构造**：创建一个空的`LinkedHashMap`，默认容量16，负载因子0.75，保持插入顺序。 - **有参构造**：允许指定初始容量、负载因子以及是否按照访问顺序排序。 - **复制构造**：从另一个`Map`创建`LinkedHashMap`，保持原映射关系，插入顺序或访问顺序取决于原`Map`类型。 4. **插入顺序访问**： - `LinkedHashMap`没有重写`put`方法，而是通过重写`newNode`方法来控制节点插入的位置。当新的节点被创建时，`LinkedHashMap`确保它被添加到链表的尾部，以此保持插入顺序。 ```java // 简化示例 void linkNodeLast(Node<K,V> p) { // last 是尾部节点 Node<K,V> l = tail; if (l == null) { // 链表为空，p既是头也是尾 p.before = p.after = p; } else { // 插入到尾部 p.after = l; p.before = l.before; l.before.after = p; l.before = p; } // 更新尾部节点 tail = p; } ``` 5. **访问顺序**： 如果`accessOrder`设置为`true`，每次元素被访问（get或者put操作）后，该元素都会被移动到链表的尾部，这样在遍历时就按照访问的顺序来呈现元素。默认情况下，`accessOrder`为`false`，只保持插入顺序。 总结起来，`LinkedHashMap`结合了哈希表的快速查找和链表的顺序特性，提供了灵活的排序选项，使得在需要保持元素插入或访问顺序的场景下，成为了一个非常有用的工具。理解其内部工作原理对于优化Java程序性能和编写高效代码至关重要。