go语言可以做网站吗,代理记账0申报一年多少钱,wordpress标签别名转换,网站建设有什么好建议LinkedHashMap 是 Java 中的一种有序 Map#xff0c;它扩展了 HashMap#xff0c;提供了有序的元素存储方式。在 LinkedHashMap 中#xff0c;元素的有序性可以按照插入顺序或访问顺序来维护#xff0c;而这个有序性是通过维护一个双向链表来实现的#xff0c;这也是实现 …LinkedHashMap 是 Java 中的一种有序 Map它扩展了 HashMap提供了有序的元素存储方式。在 LinkedHashMap 中元素的有序性可以按照插入顺序或访问顺序来维护而这个有序性是通过维护一个双向链表来实现的这也是实现 LRU Cache 功能的基础。在接下来的源码解析中我们将深入探讨 LinkedHashMap 的实现。 主要结论
在开始分析源码之前让我们首先总结一些关键结论 LinkedHashMap 继承了 HashMap因此它的底层数据结构与 HashMap 相同都是由数组、链表或红黑树组成同时也使用相同的扩容机制。 /*** 用指定的初始容量、加载因子和排序模式构造一个空的LinkedHashMap实例。** param initialCapacity 初始容量* param loadFactor 加载因子* param accessOrder 排序模式 - tttrue/tt 表示按访问顺序ttfalse/tt 表示按插入顺序* throws IllegalArgumentException 如果初始容量为负数或加载因子为非正数*/
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {// 调用 HashMap 的构造方法继承了 HashMap 的底层数据结构和扩容机制super(initialCapacity, loadFactor);this.accessOrder accessOrder;
}LinkedHashMap 使用双向链表来维护数据的顺序与 HashMap 的拉链式存储方式不同。 /** 实现说明。此类的先前版本在内部结构上略有不同。由于超类 HashMap 现在对一些节点使用树结构类 LinkedHashMap.Entry 现在被视为中介节点类也可以转换为树形结构。在当前上下文中此类的名称 LinkedHashMap.Entry 在几个方面都有点令人困惑但不能更改。否则即使它不被导出到此包外已知一些现有源代码依赖于调用 removeEldestEntry 时的符号解析特例规则以抑制由于模糊的用法而导致的编译错误。因此我们保留名称以保持编译性不变。** 节点类的更改还需要使用两个字段head、tail而不是指向头节点的指针来维护双向链接的前后列表。该类以前也使用了不同风格的回调方法来进行访问、插入和删除。*//*** 用于常规 LinkedHashMap 条目的 HashMap.Node 子类。*/
static class EntryK,V extends HashMap.NodeK,V {EntryK,V before, after;Entry(int hash, K key, value, NodeK,V next) {super(hash, key, value, next);}
}LinkedHashMap 存储顺序与添加顺序一致但也可以通过 accessOrder 参数决定是否在访问元素时移动元素以实现 LRU 缓存功能。 /*** 在删除元素之后将元素从双向链表中删除*/
void afterNodeRemoval(NodeK,V e) { // unlinkLinkedHashMap.EntryK,V p (LinkedHashMap.EntryK,V)e, b p.before, a p.after;p.before p.after null;if (b null)head a;elseb.after a;if (a null)tail b;elsea.before b;
}/*** 在访问元素之后将该元素放到双向链表的尾巴处*/
void afterNodeAccess(NodeK,V e) { // move node to lastLinkedHashMap.EntryK,V last;if (accessOrder (last tail) ! e) {LinkedHashMap.EntryK,V p (LinkedHashMap.EntryK,V)e, b p.before, a p.after;p.after null;if (b null)head a;elseb.after a;if (a ! null)a.before b;elselast b;if (last null)head p;else {p.before last;last.after p;}tail p;modCount;}
}内部结构
LinkedHashMap 内部类 Entry 继承自 HashMap 的 Node同时增加了 “前继节点” 和 “后继节点” 来支持双向链表的特性。此外LinkedHashMap 中还有两个重要的成员变量
head记录 LinkedHashMap 的头节点。tail记录 LinkedHashMap 的尾节点。accessOrder表示是否根据访问顺序进行排序如果 accessOrder 为 trueLinkedHashMap 会在元素被访问时将其移至链表末尾实现 LRU 缓存。
内部方法
LinkedHashMap 定义了一些私有的内部方法用于操作双向链表 linkNodeLast(LinkedHashMap.EntryK,V p)将元素连接到链表尾部。 /*** 将元素连接到链表尾部。** param p 要连接到链表尾部的元素*/
private void linkNodeLast(LinkedHashMap.EntryK,V p) {LinkedHashMap.EntryK,V last tail;tail p;if (last null)head p;else {p.before last;last.after p;}
}transferLinks(LinkedHashMap.EntryK,V src, LinkedHashMap.EntryK,V dst)将一个节点的前继节点和后继节点链接到另一个节点。 /*** 将一个节点的前继节点和后继节点链接到另一个节点。** param src 要转移链接的源节点* param dst 目标节点*/
private void transferLinks(LinkedHashMap.EntryK,V src,LinkedHashMap.EntryK,V dst) {LinkedHashMap.EntryK,V b dst.before src.before;LinkedHashMap.EntryK,V a dst.after src.after;if (b null)head dst;elseb.after dst;if (a null)tail dst;elsea.before dst;
}afterNodeRemoval(NodeK,V e)在删除元素后将元素从双向链表中删除。 /*** 在删除元素后将元素从双向链表中删除。** param e 要删除的元素*/
void afterNodeRemoval(NodeK,V e) { LinkedHashMap.EntryK,V p (LinkedHashMap.EntryK,V)e, b p.before, a p.after;p.before p.after null;if (b null)head a;elseb.after a;if (a null)tail b;elsea.before b;
}afterNodeInsertion(boolean evict)在插入元素后可能删除最老的元素。 /*** 在插入元素后可能删除最老的元素。** param evict 如果为 true可能会删除最老的元素*/
void afterNodeInsertion(boolean evict) { // 可能删除最老的元素LinkedHashMap.EntryK,V first;if (evict (first head) ! null removeEldestEntry(first)) {K key first.key;removeNode(hash(key), key, null, false, true);}
}afterNodeAccess(NodeK,V e)在访问元素后将元素放到链表的尾部。 /*** 在访问元素后将元素放到链表的尾部。** param e 要移动的元素*/
void afterNodeAccess(NodeK,V e) { // 将节点移动到最后LinkedHashMap.EntryK,V last;if (accessOrder (last tail) ! e) { // 如果 accessOrder 与 (last tail) ! e 为 trueLinkedHashMap.EntryK,V p (LinkedHashMap.EntryK,V)e, b p.before, a p.after;p.after null;if (b null)head a;elseb.after a;if (a ! null)a.before b;elselast b;if (last null)head p;else {p.before last;last.after p;}tail p;modCount;}
}构造方法
LinkedHashMap 提供了多个构造方法包括 LinkedHashMap(int initialCapacity, float loadFactor)指定初始容量和加载因子的构造方法。 /*** 指定初始容量和加载因子的构造方法。** param initialCapacity 初始容量* param loadFactor 加载因子*/
public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor);accessOrder false;
}LinkedHashMap(int initialCapacity)指定初始容量的构造方法。 /*** 指定初始容量的构造方法。** param initialCapacity 初始容量*/
public LinkedHashMap(int initialCapacity) {super(initialCapacity);accessOrder false;
}LinkedHashMap()默认构造方法。 /*** 默认构造方法。*/
public LinkedHashMap() {super();accessOrder false;
}LinkedHashMap(Map? extends K, ? extends V m)使用现有映射初始化构造方法。 /*** 使用现有映射初始化构造方法。** param m 要使用的映射*/
public LinkedHashMap(Map? extends K, ? extends V m) {super();accessOrder false;putMapEntries(m, false);
}LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)可以设置 accessOrder 参数以决定是否按照访问顺序排序。 /*** 可以设置 accessOrder 参数以决定是否按照访问顺序排序。** param initialCapacity 初始容量* param loadFactor 加载因子* param accessOrder 如果为 true则按照访问顺序排序否则按照插入顺序排序*/
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder accessOrder;
}LinkedHashMap 的源码解析包括实现 newNode、replacementNode、newTreeNode、replacementTreeNode 等节点插入和替换的方法以及实现 containsValue、get、getOrDefault、keySet、entrySet 等其他操作。这些方法负责在 LinkedHashMap 中维护元素的顺序和实现 LRU 缓存功能。
总结
LinkedHashMap 是一个有序的 Map它维护元素的有序性可以按照插入顺序或访问顺序排列元素。这个有序性是通过维护一个双向链表来实现的。另外LinkedHashMap 提供了 accessOrder 参数来决定是否在访问元素时移动元素以实现 LRU 缓存功能。这使得 LinkedHashMap 成为一个非常有用的数据结构适用于需要有序性和缓存功能的场景。
