热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

Java面试HashMap、HashSet源码解析

本章所有源代码基于JDK1.8版本HashMap和HashSet是JavaCollectionFramework的两个重要成员,其中HashMap是Map接口的常用实现类,Hash

本章所有源代码基于JDK1.8版本

HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,HashSet 是 Set 接口的常用实现类。虽然 HashMap 和 HashSet 实现的接口规范不同,但它们底层的 Hash 存储机制完全一样,甚至 HashSet 本身就采用 HashMap 来实现的,这一点我们通过查看HashSet的源代码就能看得到。

通过阅读源代码分析存储逻辑

HashMap

在日常的编程过程中,如果我们想要使用HashMap类,通常写法如下:

HashMap params = new HashMap();
params.put("phone","1234567890");
params.put("dtype","json");

可以由此看出,HashMap中将一个key-value作为一个整体进行处理,系统根据key的Hash值计算key-value的存储位置,这样可以保证快速存、取Map的key-value值。
下面我们查看一下HashMap中put方法的源码实现:

//put方法的入口,直接调用putVal进行处理
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**hash key计算得到的Hash值
* key key
* value key对应的value
* onlyIfAbsent 如果该参数为true,则不能修改已经存在的值
* 返回 key的hash值对应的位置之前的value,如果没有,直接返回空
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
//如果长度为0,或者HashMap为空,则重新计算长度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果key为null,则hash值为0,i值为0,则获取整个Node数组位置0处的值,是否为null
//为null代表当前位置0处,用于存放hash值为0位置没有任何元素,则将现有key-value放入这个位置,作为链表第一个对象
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
//如果key不为空,且在队列中这个key已经存在,得到当前位置node值。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果hash值对应位置是一个链表数据,则将当前数据放在链表的最前,则将现有值放入链表中,
//返回新增对象,此值如果已存在,则返回链表中这个值对应的key-value
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
//否则循环判断,将node放入节点中
for (int binCount = 0; ; ++binCount) {
//如果当前位置只有一个元素,则修改当前位置为链表结构,将key-value放到链表最前
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果hash值相同,且key值相同,不进行处理,跳出处理程序
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//下移一位,继续判断
p = e;
}
}
//如果在上述的判断中,一个是hash值找到的位置上已经有元素,且key值相同,
//或者找到位置已经是链表数据,获取到key对应的key-value节点,则进行如下判断
if (e != null) { // existing mapping for key
V oldValue = e.value;//获取当前位置原有值
//如果允许覆盖修改,或者当前位置原有的值为null,则直接修改当前位置的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;//返回原有值
}
}
++modCount;
if (++size > threshold)//如果HashMap大小已经超过长度*加载因子,则重新计算长度
resize();
afterNodeInsertion(evict);
return null;
}

我们 用一张图片来演示一下存储过程

《Java面试 HashMap、HashSet源码解析》 HashMap值存储介绍

  • 当put键值对[null, V]时,计算null的hash值得知在数组中位置为0
    • 如果位置0处没有任何对象,则直接将[null, V]存放在位置0处
    • 如果位置0处已有对象,则直接使用新的值V修改原有对象的值
  • 当put键值对[S, V]时,我们假设key值Ss的hash值相同,则在数组中对应的位置相同
    我们比较已有值的key同新put的key进行比较,不相等,则将新的值插入到原有数据之前,形成链表结构
  • 当put键值对[m, V]时,如果计算key的hash值,得到数组中对应位置上没有元素,则直接将[m, V]放到位置上。
  • 当put键值对[K, V]时,原有位置已有元素,且key值相同,则直接使用新的值V覆盖原有值
    上述代码中有两个变量很重要,分别为sizethreshold
  • size 已有对象数量
  • threshold 当前HashMap所能容纳对象的极限数量,值为当前HashMap容量*负载因子,如果容量就回触发重新设置HashMap大小的算法

HashMap提供三个构造方法,分别为

  1. public HashMap() 生成长度默认16,负载因子默认为0.75的HashMap
  2. public HashMap(int initialCapacity) 生成长度为initialCapacity,负载因子默认为0.75的HashMap
  3. public HashMap(int initialCapacity, float loadFactor) 生成长度为initialCapacity,负载因子为loadFactor的HashMap

构造方法源码为

public HashMap(int initialCapacity, float loadFactor) {
//如果设置的长度小于0,抛出异常
if (initialCapacity <0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果长度大于可设置的最大长度`2的30次方,1073741824`,则长度为最大长度
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//如果负载因子小于等于0,或者无法转换为float类型,抛出异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}

HashMap中的每一个key-value都是一个对象,包含四个属性,hash值,key,value,下一个元素

HashMap元素的获取

程序中,获取元素,可以调用HashMap的get(Object key)方法,逻辑为根据给定的key,得到key的hash值,然后使用hash值计算得到在数组中的位置。

  • 如果当前位置没有元素,直接返回null
  • 如果当前位置有元素,且key值相同,直接返回当前位置元素
  • 如果当前位置为链表结构,则使用顺序循环遍历链表的方法从中查询出key值相同的对象返回

HashMap总结

HashMap底层将key-value作为一个整体来进行处理,起整体就是一个Node对象。本质上就是Node的数组,存储值时使用key的hash值寻址存储,读取时根据key的hash值寻址读取。因此,HashMap可以快速存取key-value,其实就是因为采用了key的hash值定位寻址的方式。
初始化HashMap时,需要指定负载因子,负载因子值得就是HashMap中数值存储的密度,密度越大,占用内存越大,根据hash值进行寻址花费的时间也就越多,而存储和读取都需要使用寻址,因此会降低运行效率。如果负载因子设置过小,会使得密度降低,造成内存空间浪费。一般来说,我们无需修改HashMap的负载因子。
从源代码中我们也可以看出,如果数组中已有对象个数超过最大承受极限,也就是数组长度*负载因子,则需要重新计算数组长度,这个过程会进行数组内已有所有元素的重新计算位置和拷贝,造成不必要的系统开销。因此如果我们可以提前知道HashMap中元素的最大数量,可以根据需要设置到合适大小,避免重新计算。

HashSet

通过阅读HashSet的源代码,发现HashSet类的内部就是使用HashMap。HashSet的构造函数为:

public HashSet() {
map = new HashMap<>();
}

因此在HashSet内部也是使用Hash值计算的方式决定集合元素的存放位置
这点可以从HashSet 和 HashMap 之间有很多相似之处,对于 HashSet 而言,系统采用 Hash决定集合元素的存储位置,这样可以保证能快速存、取集合元素;


推荐阅读
  • 本文详细介绍了Java编程语言中的核心概念和常见面试问题,包括集合类、数据结构、线程处理、Java虚拟机(JVM)、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题,帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • 本文详细探讨了Java中的24种设计模式及其应用,并介绍了七大面向对象设计原则。通过创建型、结构型和行为型模式的分类,帮助开发者更好地理解和应用这些模式,提升代码质量和可维护性。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 深入解析JVM垃圾收集器
    本文基于《深入理解Java虚拟机:JVM高级特性与最佳实践》第二版,详细探讨了JVM中不同类型的垃圾收集器及其工作原理。通过介绍各种垃圾收集器的特性和应用场景,帮助读者更好地理解和优化JVM内存管理。 ... [详细]
  • 本文介绍了如何使用JQuery实现省市二级联动和表单验证。首先,通过change事件监听用户选择的省份,并动态加载对应的城市列表。其次,详细讲解了使用Validation插件进行表单验证的方法,包括内置规则、自定义规则及实时验证功能。 ... [详细]
  • 深入解析Spring Cloud Ribbon负载均衡机制
    本文详细介绍了Spring Cloud中的Ribbon组件如何实现服务调用的负载均衡。通过分析其工作原理、源码结构及配置方式,帮助读者理解Ribbon在分布式系统中的重要作用。 ... [详细]
  • 前言--页数多了以后需要指定到某一页(只做了功能,样式没有细调)html ... [详细]
  • 网络攻防实战:从HTTP到HTTPS的演变
    本文通过一系列日记记录了从发现漏洞到逐步加强安全措施的过程,探讨了如何应对网络攻击并最终实现全面的安全防护。 ... [详细]
  • 2023年京东Android面试真题解析与经验分享
    本文由一位拥有6年Android开发经验的工程师撰写,详细解析了京东面试中常见的技术问题。涵盖引用传递、Handler机制、ListView优化、多线程控制及ANR处理等核心知识点。 ... [详细]
  • 从 .NET 转 Java 的自学之路:IO 流基础篇
    本文详细介绍了 Java 中的 IO 流,包括字节流和字符流的基本概念及其操作方式。探讨了如何处理不同类型的文件数据,并结合编码机制确保字符数据的正确读写。同时,文中还涵盖了装饰设计模式的应用,以及多种常见的 IO 操作实例。 ... [详细]
  • 本文详细介绍了 Java 中 org.apache.xmlbeans.SchemaType 类的 getBaseEnumType() 方法,提供了多个代码示例,并解释了其在不同场景下的使用方法。 ... [详细]
  • libsodium 1.0.15 发布:引入重大不兼容更新
    最新发布的 libsodium 1.0.15 版本带来了若干不兼容的变更,其中包括默认密码散列算法的更改和其他重要调整。 ... [详细]
  • Scala 实现 UTF-8 编码属性文件读取与克隆
    本文介绍如何使用 Scala 以 UTF-8 编码方式读取属性文件,并实现属性文件的克隆功能。通过这种方式,可以确保配置文件在多线程环境下的一致性和高效性。 ... [详细]
  • 最近团队在部署DLP,作为一个技术人员对于黑盒看不到的地方还是充满了好奇心。多次咨询乙方人员DLP的算法原理是什么,他们都以商业秘密为由避而不谈,不得已只能自己查资料学习,于是有了下面的浅见。身为甲方,虽然不需要开发DLP产品,但是也有必要弄明白DLP基本的原理。俗话说工欲善其事必先利其器,只有在懂这个工具的原理之后才能更加灵活地使用这个工具,即使出现意外情况也能快速排错,越接近底层,越接近真相。根据DLP的实际用途,本文将DLP检测分为2部分,泄露关键字检测和近似重复文档检测。 ... [详细]
author-avatar
Era_zhou
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有