深入解析LinkedHashMap

2024-04-03 16:32
文章标签 深入 解析 linkedhashmap

本文主要是介绍深入解析LinkedHashMap,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述
LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。

public void test(){Map<String,String> map=new LinkedHashMap<>();map.put("a","1");map.put("b","2");map.put("c","3");Set<Map.Entry<String, String>> entries = map.entrySet();for (Map.Entry<String, String> entry : entries) {System.out.println(entry);}
}

在这里插入图片描述

可以看到,通过遍历Entry发现LinkedHashMap是有序的。在上面的案例中我们展示了LinkedHashMap默认的顺序维持方式(维持插入的顺序),通过重载的构造函数,我们可以将LinkedHashMap设置为维持访问的顺序:

public void test(){Map<String,String> map=new LinkedHashMap<>(16,0.75f,true);map.put("a","1");map.put("b","2");map.put("c","3");//获取b后,b节点就会移动到链表的尾部map.get("b");Set<Map.Entry<String, String>> entries = map.entrySet();for (Map.Entry<String, String> entry : entries) {System.out.println(entry);}
}

在这里插入图片描述

LinkedHashMap维持插入顺序的原理

想要知道LinkedHashMap是如何维持插入顺序的,就需要从其内部类入手解决:

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);}
}

可以看到,LinkedHashMap中Entry内部类继承与HashMap.Node内部类,LinkedHashMap.Entry类在HashMap.Node的基础上增加了两个指针:before、after。没错,LinkedHashMap就是采用双向链表来维持插入顺序的。LinkedHashMap也提供了两个字段来保存双向链表的头尾的引用。

/*** The head (eldest) of the doubly linked list.*/
transient LinkedHashMap.Entry<K,V> head;
/*** The tail (youngest) of the doubly linked list.*/
transient LinkedHashMap.Entry<K,V> tail;

在这里插入图片描述

如上图,我们依次插入A、B、C、D、E五个Entry,而每次插入时,我们都按照插入顺序维持一个双向链表。我们从head指针开始,顺着after指针走(也就是图中的红色箭头),就可以还原我们的插入顺序。

LinkedHashMap源码解析

在了解完LinkedHashMap基本原理后,我们就来看看它的源码,我们先从它的构造器入手。

构造函数

public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;
}

其中initialCapacity和loadFactor在 《JDK8HashMap源码深度解析》一文中详细介绍过了,这里不再赘述。需要注意的是accessOrder参数,它决定了LinkedHashMap的顺序维持策略,当accessOrder=true时,采用访问顺序维持模式,而accessOrder=false时采用插入顺序维持模式。

public LinkedHashMap() {super();accessOrder = false;
}

可以看到LinkedHashMap无参构造器,将accessOrder属性设置为了false。

put方法

根据前面的描述知道了LinkedHashMap在插入Entry时会不断维持一个双向链表,那么我们有必要对put方法进行一些分析,需要注意的是LinkedHashMap并没实现自己的put方法,而是继承至HashMap的put方法。下面是HashMap中的put方法的源码:

   public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}/*** 计算key的hash值,该hash算法调用了Obejct的hashcode* 返回的是key.hashCode()&(key.hashCode()>>>16),其中>>>代表无符号右移**/static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;//将Map内部的table数组赋给局部变量tab,如果table为空或者大小为0,则使用resize进行扩容if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;/*** n-1&hash的效果就是 hash%n (因为HashMap中封装的数组的长度都是2的幂(默认16))* 如果数组对应位置没有元素(没有发生Hash冲突),则新建一个Node元素,放入该数组位置*/if ((p = tab[i = (n - 1) & hash]) == null)// 重点******************************************tab[i] = newNode(hash, key, value, null);// 重点******************************************/*** 发生Hash冲突后的处理*/else {Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//如果此时解决Hash冲突的数据结构为链表,则遍历到链表尾部for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {//向链表中添加新元素p.next = newNode(hash, key, value, null);//如果新元素未加入之前,链表长度大于等于7了则需要将链表转换为红黑树了,换句话说加入新元素后链表长度大于等于8了,就转成红黑树。if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);//将链表转换为红黑树//跳出循环break;}//判断key是否相等//这里的条件判断显示出HashMap允许一个key==null的键值对存储if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//如果找到了一个相同的key,则根据onlyIfAbsent判断是否需要替换旧的value。//onlyIfAbsent为true时代表不替换原先元素。if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}//被修改的次数,fast-fail机制++modCount;//如果HashMap中存储的节点数量是否到达了扩容的阈值if (++size > threshold)//进行扩容resize();afterNodeInsertion(evict);return null;}

可能有人就糊涂了,既然是使用的父类的put方法,那么LinkedHashMap是如何维持双向链表的呢?实际上真正的玄机在第29行中,tab[i] = newNode(hash, key, value, null);掉用的是LinkedHashMap的newNode方法,就是在这个方法中实现了维持插入顺序的功能(不得不感叹设计的精妙)。

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {//创建Entry节点LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);//将新增节点放在链表尾部linkNodeLast(p);return p;
}
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {LinkedHashMap.Entry<K,V> last = tail;//将tail指针指向该元素(tail指针永远指向链表的尾部节点)tail = p;//原先的尾部节点若为空,则代表当前Map中没有存储数据,则将head指针也指向新增节点pif (last == null)head = p;else {//将before指针指向原先的队尾p.before = last;//将原先队尾的next指针指向新增元素last.after = p;}
}

get方法

前面我们提到了accessOrder属性,如果accessOrder=true就会使得LinkedHashMap维持访问顺序,一说到访问那就肯定是get方法了,我们就来看看它是如何维持访问顺序的。LinkedHashMap实现了自己的get方法:

public V get(Object key) {Node<K,V> e;if ((e = getNode(hash(key), key)) == null)return null;if (accessOrder)//如果accessOrder为true则将访问的元素移到双向链表的尾部afterNodeAccess(e);return e.value;
}
void afterNodeAccess(Node<K,V> e) { // move node to lastLinkedHashMap.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;// 因为马上要到链表尾部去了,所以要将当前元素的after指针置为空p.after = null;if (b == null)//如果前一个节点为空,那么将头指针指向下一个节点head = a;else//前一个节点不为空,那么将前一个节点的after指针指向下一个节点b.after = a;if (a != null)//如果下一个节点不为空,则将下一个节点的before指针设为前一个节点a.before = b;else//如果没有下一个节点,则将last指向前一个节点,实际上这一步正常情况下不会发生,因为前面已经验证了当前元素不是尾节点last = b;if (last == null)head = p;else {//将当前元素插入链表尾部p.before = last;last.after = p;}//此时当前元素已经移到了链表尾部,将tail指针指向当前元素tail = p;//modeCount用于迭代器的快速失败机制(fail-fast)++modCount;}
}

LinkedHashMap用途浅析

​ 我们在使用缓存的时候,需要采用特定的缓存淘汰机制,而LRU(Least Recently Used 最近最少使用)淘汰机制也是最常使用的。它会淘汰最久没有使用过的缓存,而借助LinkedHashMap可以非常容易的实现这一策略:

import java.util.LinkedHashMap;
import java.util.Map;public class LRUCache<K, V> extends LinkedHashMap<K, V> {private int maxEntries;public LRUCache(int maxEntries) {super(16, 0.75f, true);this.maxEntries = maxEntries;}@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > maxEntries;}
}

为什么重写父类的removeEldestEntry就能实现LRU策略呢?这仍然需要分析LinkedHashMap的源码,在该类中put方法(HashMap中的方法)会调用putVal()方法(HashMap的方法),而在putVal()方法的尾部会调用afterNodeInsertion()方法(LinkedHashMap中的方法),afterNodeInsertion方法就是淘汰策略的实现代码:

在这里插入图片描述

/**
* 可能移除最少使用的元素
**/
void afterNodeInsertion(boolean evict) { LinkedHashMap.Entry<K,V> first;//如果removeEldestEntry(first)返回true就会触发淘汰机制,淘汰的最久没有使用过的元素if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;//删除双向链表的头节点removeNode(hash(key), key, null, false, true);}
}

这篇关于深入解析LinkedHashMap的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/873418

相关文章

使用Python绘制3D堆叠条形图全解析

《使用Python绘制3D堆叠条形图全解析》在数据可视化的工具箱里,3D图表总能带来眼前一亮的效果,本文就来和大家聊聊如何使用Python实现绘制3D堆叠条形图,感兴趣的小伙伴可以了解下... 目录为什么选择 3D 堆叠条形图代码实现:从数据到 3D 世界的搭建核心代码逐行解析细节优化应用场景:3D 堆叠图

深度解析Python装饰器常见用法与进阶技巧

《深度解析Python装饰器常见用法与进阶技巧》Python装饰器(Decorator)是提升代码可读性与复用性的强大工具,本文将深入解析Python装饰器的原理,常见用法,进阶技巧与最佳实践,希望可... 目录装饰器的基本原理函数装饰器的常见用法带参数的装饰器类装饰器与方法装饰器装饰器的嵌套与组合进阶技巧

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决

深度解析Spring Boot拦截器Interceptor与过滤器Filter的区别与实战指南

《深度解析SpringBoot拦截器Interceptor与过滤器Filter的区别与实战指南》本文深度解析SpringBoot中拦截器与过滤器的区别,涵盖执行顺序、依赖关系、异常处理等核心差异,并... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)深度解析:区别、实现

深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

《深度解析SpringAOP@Aspect原理、实战与最佳实践教程》文章系统讲解了SpringAOP核心概念、实现方式及原理,涵盖横切关注点分离、代理机制(JDK/CGLIB)、切入点类型、性能... 目录1. @ASPect 核心概念1.1 AOP 编程范式1.2 @Aspect 关键特性2. 完整代码实

解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题

《解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题》:本文主要介绍解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4... 目录未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘打开pom.XM

IDEA Maven提示:未解析的依赖项的问题及解决

《IDEAMaven提示:未解析的依赖项的问题及解决》:本文主要介绍IDEAMaven提示:未解析的依赖项的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录IDEA Maven提示:未解析的依编程赖项例如总结IDEA Maven提示:未解析的依赖项例如

SpringBoot开发中十大常见陷阱深度解析与避坑指南

《SpringBoot开发中十大常见陷阱深度解析与避坑指南》在SpringBoot的开发过程中,即使是经验丰富的开发者也难免会遇到各种棘手的问题,本文将针对SpringBoot开发中十大常见的“坑... 目录引言一、配置总出错?是不是同时用了.properties和.yml?二、换个位置配置就失效?搞清楚加

Python循环结构全面解析

《Python循环结构全面解析》循环中的代码会执行特定的次数,或者是执行到特定条件成立时结束循环,或者是针对某一集合中的所有项目都执行一次,这篇文章给大家介绍Python循环结构解析,感兴趣的朋友跟随... 目录for-in循环while循环循环控制语句break语句continue语句else子句嵌套的循