成都网站开发团队,wordpress create a network,wordpress上传不了主题,视觉中国网站前言 我们知道HashMap底层是采用数组单向线性链表/红黑树来实现的#xff0c;HashMap在扩容或者链表与红黑树转换过程时可能会改变元素的位置和顺序。如果需要保存元素存入或访问的先后顺序#xff0c;那就需要采用LinkedHashMap了。 LinkedHashMap结构 LinkedHashMap继承自H…前言 我们知道HashMap底层是采用数组单向线性链表/红黑树来实现的HashMap在扩容或者链表与红黑树转换过程时可能会改变元素的位置和顺序。如果需要保存元素存入或访问的先后顺序那就需要采用LinkedHashMap了。 LinkedHashMap结构 LinkedHashMap继承自HashMap它的所有操作和HashMap类似底层结构也和HashMap一样只不过为了维护元素的存入/访问顺序增加了一个双向链表。 LinkedHashMap结构图 LinkedHashMap由数组、单向线性链表、红黑树、双向线性链表组成。如上图灰色区域为数组蓝色节点和蓝色箭头为单向链表的引用关系绿色节点和绿色箭头为红黑树的引用关系节点中的数字依次表示元素的存入/访问顺序由橙色的双向箭头表示双向链表的引用关系。 注在JDK1.7及之前HashMap中没有红黑树LinkedHashMap中也不存在红黑树。另在JDK1.6及之前HashMap中的链表为单向环形链表LinkedHashMap中中的单向链表和双向链表都是环形链表。在JDK1.8LinkedHashMap中可能会存在红黑树同时单向链表和双向链表都是线性的。本文是基于JDK1.8来分析的。 LinkedHashMap源码分析 基本属性 transient LinkedHashMap.EntryK,V head; // 双向链表头节点
transient LinkedHashMap.EntryK,V tail; // 双向链表尾节点
final boolean accessOrder; // 是否按照访问顺序排序复制代码head和tail分别记录了双向链表的头节点和尾节点遍历时通过head或tail就可以按照存入/访问的顺序来取数据。 accessOrder用以表示LinkedHashMap是否按照访问顺序来排序为true的话表示按照访问顺序排序为false表示按照存入顺序排序默认为false。 构造函数 // 无参构造
public LinkedHashMap() {super();accessOrder false;
}
// 给定初始容量
public LinkedHashMap(int initialCapacity) {super(initialCapacity);accessOrder false;
}
// 给定初始容量和加载因子
public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor);accessOrder false;
}
// 给定初始容量、加载因子、是否按访问先后排序
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder accessOrder;
}复制代码构造函数都是调用父类HashMap的构造函数。前3个都默认accessOrder为falseLinkedHashMap内部按照存入顺序排序。最后一个构造函数可以指定accessOrder的值。 增 LinkedHashMap添加数据要调用了父类的HashMap的put方法在HashMap的源码中put方法存入元素后调用了afterNodeAccess和afterNodeInsertion方法这两个方法在HashMap中都是空方法LinkedHashMap实现了这两个方法 void afterNodeAccess(NodeK,V e) { LinkedHashMap.EntryK,V last;// 如果按照访问顺序排序并且添加的元素e不是双向链表的尾节点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;}
}复制代码afterNodeAccess方法的逻辑就是将当前节点e移动到双向链表的尾部。每次LinkedHashMap中有元素被访问时就会按照访问先后来排序先访问的在双向链表中靠前越后访问的越接近尾部。当然只有当accessOrder为true时才会执行这个操作。 void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.EntryK,V first;if (evict (first head) ! null removeEldestEntry(first)) {K key first.key;removeNode(hash(key), key, null, false, true);}
}复制代码afterNodeInsertion方法意思是evict为true时删除双向链表的头节点。 通过afterNodeAccess和afterNodeInsertion这两个方法如果当LinkedHashMap的容量达到一定量时需要保存它的size不变那么每次添加一个元素到双向链表的尾部就要删除一个双向链表头部的元素这相当于实现了LruCache的策略。 删 删除元素同样也是调用了HashMap的remove方法在remove方法中调用了afterNodeRemoval方法。 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;
}复制代码afterNodeRemoval方法就是将e节点从双向链表中删除更改e前后节点引用关系使之重新连成完整的双向链表。 改 LinkedHashMap更改元素的value值仍是调用put方法涉及到的逻辑可以看上面的afterNodeAccess和afterNodeInsertion这两个方法。 查 LinkedHashMap自己实现了get方法。 public V get(Object key) {NodeK,V e;if ((e getNode(hash(key), key)) null)return null;if (accessOrder)afterNodeAccess(e);return e.value;
}复制代码逻辑非常简单直接调用HashMap的getNode方法如果需要按照访问先后排序调用afterNodeAccess更新双向链表排序。 总结 LinkedHashMap继承了HashMap的所有特性唯一的区别就是LinkedHashMap是一个有序的映射集合而HashMap则是无序的。LinkedHashMap实现排序的原理就是再内部增加了一个双向链表来记录元素的存入/访问顺序。LinkedHashMap内部是记录的是存入还是访问顺序取决于关键属性accessOrder默认是按存入顺序记录。
