一. 前言
先看一个例子, 我们想在页面展示一周内的消费变化情况, 用 echarts 面积图进行展示. 如下:
我们在后台将数据构造完成
- HashMap<String, Integer> map = new HashMap<>();
- map.put("星期一", 40);
- map.put("星期二", 43);
- map.put("星期三", 35);
- map.put("星期四", 55);
- map.put("星期五", 45);
- map.put("星期六", 35);
- map.put("星期日", 30);
然而页面上一展示, 发现并非如此, 我们打印出来看, 发现顺序并非我们所想, 先 put 进去的先 get 出来
- for (Map.Entry<String, Integer> entry : map.entrySet()){
- System.out.println("key:" + entry.getKey() + ", value:" + entry.getValue());
- }
- /**
- * 结果如下:
- * key: 星期二, value: 40
- * key: 星期六, value: 35
- * key: 星期三, value: 50
- * key: 星期四, value: 55
- * key: 星期五, value: 45
- * key: 星期日, value: 65
- * key: 星期一, value: 30
- */
那么如何保证预期展示结果如我们所想呢, 这个时候就需要用到 LinkedHashMap 实体.
二. 初识 LinkedHashMap
首先我们把上述代码用 LinkedHashMap 进行重构
- LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
- map.put("星期一", 40);
- map.put("星期二", 43);
- map.put("星期三", 35);
- map.put("星期四", 55);
- map.put("星期五", 45);
- map.put("星期六", 35);
- map.put("星期日", 30);
- for (Map.Entry<String, Integer> entry : map.entrySet()){
- System.out.println("key:" + entry.getKey() + ", value:" + entry.getValue());
- }
这个时候, 结果正如我们所预期
key: 星期一, value: 40
key: 星期二, value: 43
key: 星期三, value: 35
key: 星期四, value: 55
key: 星期五, value: 45
key: 星期六, value: 35
key: 星期日, value: 30
LinkedHashMap 继承了 HashMap 类, 是 HashMap 的子类, LinkedHashMap 的大多数方法的实现直接使用了父类 HashMap 的方法, 关于 HashMap 在前面的章节已经讲过了,《HashMap 原理(一) 概念和底层架构》,《HashMap 原理(二) 扩容机制及存取原理》.
LinkedHashMap 可以说是 HashMap 和 LinkedList 的集合体, 既使用了 HashMap 的数据结构, 又借用了 LinkedList 双向链表的结构(关于 LinkedList 可参考 Java 集合 LinkedList 的原理及使用), 那么这样的结构如何实现的呢, 我们看一下 LinkedHashMap 的类结构
我们看到 LinkedHashMap 中定义了一个 Entry 静态内部类, 定义了 5 个构造器, 一些成员变量, 如 head,tail,accessOrder, 并继承了 HashMap 的方法, 同时实现了一些迭代器方法. 我们先看一下 Entry 类
- static class Entry<K,V> extends HashMap.Node<K,V> {
- Entry<K,V> before, after;
- Entry(int hash, K key, V value, Node<K,V> next) {
- super(hash, key, value, next);
- }
- }
我们看到这个静态内部类很简单, 继承了 HashMap 的 Node 内部类, 我们知道 Node 类是 HashMap 的底层数据结构, 实现了数组 + 链表 / 红黑树的结构, 而 Entry 类保留了 HashMap 的数据结构, 同时通过 before,after 实现了双向链表结构(HashMap 中 Node 类只有 next 属性, 并不具备双向链表结构). 那么 before,after 和 next 到底什么关系呢.
看上面的结构图, 定义了头结点 head, 当我们调用迭代器进行遍历时, 通过 head 开始遍历, 通过 before 属性可以不断找到下一个, 直到 tail 尾结点, 从而实现顺序性. 而在同一个 hash(在上图中表现了同一行)链表内部 after 和 next 效果是一样的. 不同点在于 before 和 after 可以连接不同 hash 之间的链表.
前面我们发现数据结构已经完全支持其顺序性了, 接下来我们再看一下构造方法, 看一下比起 HashMap 的构造方法是否有不同.
- // 构造方法 1, 构造一个指定初始容量和负载因子的, 按照插入顺序的 LinkedList
- public LinkedHashMap(int initialCapacity, float loadFactor) {
- super(initialCapacity, loadFactor);
- accessOrder = false;
- }
- // 构造方法 2, 构造一个指定初始容量的 LinkedHashMap, 取得键值对的顺序是插入顺序
- public LinkedHashMap(int initialCapacity) {
- super(initialCapacity);
- accessOrder = false;
- }
- // 构造方法 3, 用默认的初始化容量和负载因子创建一个 LinkedHashMap, 取得键值对的顺序是插入顺序
- public LinkedHashMap() {
- super();
- accessOrder = false;
- }
- // 构造方法 4, 通过传入的 map 创建一个 LinkedHashMap, 容量为默认容量 (16) 和(map.zise()/DEFAULT_LOAD_FACTORY)+1 的较大者, 装载因子为默认值
- public LinkedHashMap(Map<? extends K, ? extends V> m) {
- super(m);
- accessOrder = false;
- }
- // 构造方法 5, 根据指定容量, 装载因子和键值对保持顺序创建一个 LinkedHashMap
- public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
- super(initialCapacity, loadFactor);
- this.accessOrder = accessOrder;
- }
我们发现除了多了一个变量 accessOrder 之外, 并无不同, 此变量到底起了什么作用?
- /**
- * The iteration ordering method for this linked hash map: <tt>true</tt>
- * for access-order, <tt>false</tt> for insertion-order.
- *
- * @serial
- */
- final boolean accessOrder;
通过注释发现该变量为 true 时 access-order, 即按访问顺序遍历, 如果为 false, 则表示按插入顺序遍历. 默认为 false, 在哪些地方使用到该变量了, 同时怎么理解? 我们可以看下面的方法介绍
二. put 方法
前面我们提到 LinkedHashMap 的 put 方法沿用了父类 HashMap 的 put 方法, 但我们也提到了像 LinkedHashMap 的 Entry 类就是继承了 HashMap 的 Node 类, 同样的, HashMap 的 put 方法中调用的其他方法在 LinkedHashMap 中已经被重写. 我们先看一下 HashMap 的 put 方法, 这个在《HashMap 原理(二) 扩容机制及存取原理》中已经有说明, 我们主要关注于其中的不同点
- /**
- * Implements Map.put and related methods
- *
- * @param hash hash for key
- * @param key the key
- * @param value the value to put
- * @param onlyIfAbsent if true, don't change existing value
- * @param evict if false, the table is in creation mode.
- * @return previous value, or null if none
- */
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
- Node<K,V>[] tab; Node<K,V> p; int n, i;
- /**
- * 如果当前 HashMap 的 table 数组还未定义或者还未初始化其长度, 则先通过 resize()进行扩容,
- * 返回扩容后的数组长度 n
- */
- if ((tab = table) == null || (n = tab.length) == 0)
- n = (tab = resize()).length;
- // 通过数组长度与 hash 值做按位与 & 运算得到对应数组下标, 若该位置没有元素, 则 new Node 直接将新元素插入
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null);
- // 否则该位置已经有元素了, 我们就需要进行一些其他操作
- else {
- Node<K,V> e; K k;
- // 如果插入的 key 和原来的 key 相同, 则替换一下就完事了
- if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
- e = p;
- /**
- * 否则 key 不同的情况下, 判断当前 Node 是否是 TreeNode, 如果是则执行 putTreeVal 将新的元素插入
- * 到红黑树上.
- */
- else if (p instanceof TreeNode)
- e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
- // 如果不是 TreeNode, 则进行链表遍历
- else {
- for (int binCount = 0; ; ++binCount) {
- /**
- * 在链表最后一个节点之后并没有找到相同的元素, 则进行下面的操作, 直接 new Node 插入,
- * 但条件判断有可能转化为红黑树
- */
- if ((e = p.next) == null) {
- // 直接 new 了一个 Node
- p.next = newNode(hash, key, value, null);
- /**
- * TREEIFY_THRESHOLD=8, 因为 binCount 从 0 开始, 也即是链表长度超过 8(包含)时,
- * 转为红黑树.
- */
- if (binCount>= TREEIFY_THRESHOLD - 1) // -1 for 1st
- treeifyBin(tab, hash);
- break;
- }
- /**
- * 如果在链表的最后一个节点之前找到 key 值相同的(和上面的判断不冲突, 上面是直接通过数组
- * 下标判断 key 值是否相同), 则替换
- */
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- break;
- p = e;
- }
- }
- if (e != null) { // existing mapping for key
- V oldValue = e.value;
- //onlyIfAbsent 为 true 时: 当某个位置已经存在元素时不去覆盖
- if (!onlyIfAbsent || oldValue == null)
- e.value = value;
- afterNodeAccess(e);
- return oldValue;
- }
- }
- ++modCount;
- // 最后判断临界值, 是否扩容.
- if (++size> threshold)
- resize();
- afterNodeInsertion(evict);
- return null;
- }
1. newNode 方法
首先: LinkedHashMap 重写了 newNode()方法, 通过此方法保证了插入的顺序性.
- /**
- * 使用 LinkedHashMap 中内部类 Entry
- */
- Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
- LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
- linkNodeLast(p);
- return p;
- }
- /**
- * 将新创建的节点 p 作为尾结点 tail,
- * 当然如果存储的第一个节点, 那么它即是 head 节点, 也是 tail 节点, 此时节点 p 的 before 和 after 都为 null
- * 否则, 建立与上一次尾结点的链表关系, 将当前尾节点 p 的前一个节点 (before) 设置为上一次的尾结点 last,
- * 将上一次尾节点 last 的后一个节点 (after) 设置为当前尾结点 p
- * 通过此方法实现了双向链表功能, 完成 before,after,head,tail 的值设置
- */
- private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
- LinkedHashMap.Entry<K,V> last = tail;
- tail = p;
- if (last == null)
- head = p;
- else {
- p.before = last;
- last.after = p;
- }
- }
2. afterNodeAccess 方法
其次: 关于 afterNodeAccess()方法, 在 HashMap 中没给具体实现, 而在 LinkedHashMap 重写了, 目的是保证操作过的 Node 节点永远在最后, 从而保证读取的顺序性, 在调用 put 方法和 get 方法时都会用到.
- /**
- * 当 accessOrder 为 true 并且传入的节点不是最后一个时, 将传入的 node 移动到最后一个
- */
- void afterNodeAccess(Node<K,V> e) {
- // 在执行方法前的上一次的尾结点
- LinkedHashMap.Entry<K,V> last;
- // 当 accessOrder 为 true 并且传入的节点并不是上一次的尾结点时, 执行下面的方法
- if (accessOrder && (last = tail) != e) {
- LinkedHashMap.Entry<K,V> p =
- (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
- //p: 当前节点
- //b: 当前节点的前一个节点
- //a: 当前节点的后一个节点;
- // 将 p.after 设置为 null, 断开了与后一个节点的关系, 但还未确定其位置
- p.after = null;
- /**
- * 因为将当前节点 p 拿掉了, 那么节点 b 和节点 a 之间断开了, 我们先站在节点 b 的角度建立与节点 a
- * 的关联, 如果节点 b 为 null, 表示当前节点 p 是头结点, 节点 p 拿掉后, p 的下一个节点 a 就是头节点了;
- * 否则将节点 b 的后一个节点设置为节点 a
- */
- if (b == null)
- head = a;
- else
- b.after = a;
- /**
- * 因为将当前节点 p 拿掉了, 那么节点 a 和节点 b 之间断开了, 我们站在节点 a 的角度建立与节点 b
- * 的关联, 如果节点 a 为 null, 表示当前节点 p 为尾结点, 节点 p 拿掉后, p 的前一个节点 b 为尾结点,
- * 但是此时我们并没有直接将节点 p 赋值给 tail, 而是给了一个局部变量 last(即当前的最后一个节点), 因为
- * 直接赋值给 tail 与该方法最终的目标并不一致; 如果节点 a 不为 null 将节点 a 的前一个节点设置为节点 b
- *
- * (因为前面已经判断了(last = tail) != e, 说明传入的节点并不是尾结点, 既然不是尾结点, 那么
- * e.after 必然不为 null, 那为什么这里又判断了 a == null 的情况?
- * 以我的理解, java 可通过反射机制破坏封装, 因此如果都是反射创建出的 Entry 实体, 可能不会满足前面
- * 的判断条件)
- */
- if (a != null)
- a.before = b;
- else
- last = b;
- /**
- * 正常情况下 last 应该也不为空, 为什么要判断, 原因和前面一样
- * 前面设置了 p.after 为 null, 此处再将其 before 值设置为上一次的尾结点 last, 同时将上一次的尾结点
- * last 设置为本次 p
- */
- if (last == null)
- head = p;
- else {
- p.before = last;
- last.after = p;
- }
- // 最后节点 p 设置为尾结点, 完事
- tail = p;
- ++modCount;
- }
- }
我们前面说到的 linkNodeLast(Entry e)方法和现在的 afterNodeAccess(Node e)都是将传入的 Node 节点放到最后, 那么它们的使用场景如何呢?
在前面讲解 HashMap 时, 提到了 HashMap 的 put 流程, 如果在对应的 hash 位置上还没有元素, 那么直接 new Node()放到数组 table 中, 这个时候对应到 LinkedHashMap 中, 调用了 newNode()方法, 就会用到 linkNodeLast(), 将新 node 放到最后, 而如果对应的 hash 位置上有元素, 进行元素值的覆盖时, 就会调用 afterNodeAccess(), 将原本可能不是最后的 node 节点拿到了最后. 如
- LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
- map.put("1 月", 20);
- // 此时就会调用到 linkNodeLast()方法, 也会调用 afterNodeAccess()方法, 但会被阻挡在
- //if (accessOrder && (last = tail) != e) 之外
- map.put("2 月", 30);
- map.put("3 月", 65);
- map.put("4 月", 43);
- // 这时不会调用 linkNodeLast(), 会调用 afterNodeAccess()方法将 key 为 "1 月" 的元素放到最后
- map.put("1 月", 35);
- // 这时不会调用 linkNodeLast(), 会调用 afterNodeAccess()方法将 key 为 "2 月" 的元素放到最后
- map.get("2 月");
- // 调用打印方法
- for (Map.Entry<String, Integer> entry : map.entrySet()){
- System.out.println("key:" + entry.getKey() + ", value:" + entry.getValue());
- }
结果如下:
key: 3 月, value: 65
key: 4 月, value: 43
key: 1 月, value: 35
key: 2 月, value: 30
而如果是执行下面这段代码, 将 accessOrder 改为 false
- LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, false);
- map.put("1 月", 20);
- // 此时就会调用到 linkNodeLast()方法, 也会调用 afterNodeAccess()方法, 但会被阻挡在
- //if (accessOrder && (last = tail) != e) 之外
- map.put("2 月", 30);
- map.put("3 月", 65);
- map.put("4 月", 43);
- // 这时不会调用 linkNodeLast(), 会调用 afterNodeAccess()方法将 key 为 "1 月" 的元素放到最后
- map.put("1 月", 35);
- map.get("2 月");
- // 调用打印方法
- for (Map.Entry<String, Integer> entry : map.entrySet()){
- System.out.println("key:" + entry.getKey() + ", value:" + entry.getValue());
- }
结果如下:
key: 1 月, value: 35
key: 2 月, value: 30
key: 3 月, value: 65
key: 4 月, value: 43
大家看到区别了吗, accessOrder 为 false 时, 你访问的顺序就是按照你第一次插入的顺序; 而 accessOrder 为 true 时, 你任何一次的操作, 包括 put,get 操作, 都会改变 map 中已有的存储顺序.
3. afterNodeInsertion 方法
我们看到在 LinkedHashMap 中还重写了 afterNodeInsertion(boolean evict)方法, 它的目的是移除链表中最老的节点对象, 也就是当前在头部的节点对象, 但实际上在 JDK8 中不会执行, 因为 removeEldestEntry 方法始终返回 false. 看源码:
- void afterNodeInsertion(boolean evict) { // possibly remove eldest
- LinkedHashMap.Entry<K,V> first;
- if (evict && (first = head) != null && removeEldestEntry(first)) {
- K key = first.key;
- removeNode(hash(key), key, null, false, true);
- }
- }
- protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
- return false;
- }
三. get 方法
LinkedHashMap 的 get 方法与 HashMap 中 get 方法的不同点也在于多了 afterNodeAccess()方法
- public V get(Object key) {
- Node<K,V> e;
- if ((e = getNode(hash(key), key)) == null)
- return null;
- if (accessOrder)
- afterNodeAccess(e);
- return e.value;
- }
在这里就不再多讲了, getNode()方法在 HashMap 章节已经讲过, 而前面刚把 afterNodeAccess 讲了.
四. remove 方法
remove 方法也直接使用了 HashMap 中的 remove, 在 HashMap 章节并没有讲解, 因为 remove 的原理很简单, 通过传递的参数 key 计算出 hash, 据此可找到对应的 Node 节点, 接下来如果该 Node 节点是直接在数组中的 Node, 则将 table 数组该位置的元素设置为 node.next; 如果是链表中的, 则遍历链表, 直到找到对应的 node 节点, 然后建立该节点的上一个节点的 next 设置为该节点的 next.
LinkedHashMap 重写了其中的 afterNodeRemoval(Node e), 该方法在 HashMap 中没有具体实现, 通过此方法在删除节点的时候调整了双链表的结构.
- void afterNodeRemoval(Node<K,V> e) {
- LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
- // 将待删除节点的 before 和 after 都设置为 null
- p.before = p.after = null;
- /**
- * 如果节点 b 为 null, 表示待删除节点 p 为头部节点, 该节点拿掉后, 该节点的下一个节点 a 就为头部节点 head
- * 否则设置待删除节点的上一个节点 b 的 after 属性为节点 a
- */
- if (b == null)
- head = a;
- else
- b.after = a;
- /**
- * 如果节点 a 为 null, 表示待删除节点 p 为尾部节点, 该节点拿掉后, 该节点的上一个节点 a 就为尾部节点 tail
- * 否则设置待删除节点的下一个节点 a 的 before 属性为节点 b
- */
- if (a == null)
- tail = b;
- else
- a.before = b;
- }
五. 总结
LinkedHashMap 使用的也较为频繁, 它基于 HashMap, 用于 HashMap 的特点, 又增加了双链表的结构, 从而保证了顺序性, 本文主要从源码的角度分析其如何保证顺序性, accessOrder 的解释, 以及常用方法的阐释, 若有不对之处, 请批评指正, 望共同进步, 谢谢!
来源: https://www.cnblogs.com/LiaHon/p/11180869.html