Java之HashMap详解

简介: 本文介绍了Java中HashMap的源码实现(基于JDK 1.8)。HashMap是基于哈希表的Map接口实现,允许空值和空键,不同步且线程不安全。文章详细解析了HashMap的数据结构、主要方法(如初始化、put、get、resize等)的实现,以及树化和反树化的机制。此外,还对比了JDK 7和JDK 8中HashMap的主要差异,并提供了使用HashMap时的一些注意事项。

在项目开发中,HashMap是及其常用的数据结构。今天,我们一起来看看它的源码实现(本文源码来自JDK 1.8)。

HashMap有如下类注释: 从中可知:

  • 基于哈希表的Map接口实现
  • 允许空值和空键
  • HashMap类大致相当于Hashtable,不同之处在于它是不同步的,是线程不安全的
  • HashMap不保证映射的顺序
  • 为基本操作(get和put)提供O(1)的性能
  • 集合视图进行迭代所需的时间,与HashMap实例的容量加size成正比
  • HashMap实例有两个影响其性能的参数:初始容量和负载因子
  • 当哈希表中的条目数超过负载因子和当前容量的乘积时,将对哈希表进行重建,使哈希表的桶数大约增加一倍。

1 数据结构

HashMap是Map接口基于哈希表的一种实现。 哈希表基于数组实现,元素是Entry对象。HashMap中将Entry形成链表(或者红黑树),来解决哈希冲突。 HashMap主要属性如下:

java

代码解读

复制代码

// 默认初始容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量,2^31
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表树化时的阈值,当向entry数量为8的桶put元素时,将引起链表树化
static final int TREEIFY_THRESHOLD = 8;
// 桶取消树化时的阈值
static final int UNTREEIFY_THRESHOLD = 6;

// 哈希表
transient Node<K,V>[] table;
// 哈希表尺寸
transient int size;
// 触发下次扩容时map中的entry数,取值为capacity * load factor,
int threshold;
// 负载因子
final float loadFactor;

// 对HashMap实例的修改次数
transient int modCount;
// Entry视图
transient Set<Map.Entry<K,V>> entrySet;

1.1 负载因子

当哈希冲突严重时,键值对在哈希表中的分布将很不均匀,有些桶中没有元素,而有些桶中有很多元素;此时,查询性能将受到影响。

因此,不能等到HashMap中键值对数量,达到或超过哈希表长度时,才进行扩容。

使用loadFactor(小于1)衡量哈希表的饱和程度。要求size > capacity * load factor时,就进行扩容。通过rehash来减少哈希冲突,以保证HashMap的性能

1.2 分离链表法

嵌套类Node<K,V>,即键值对,是单链表结构。树化时使用嵌套类TreeNode<K,V>

树化只为提高哈希冲突严重时,在桶中查找某个key的效率。 红黑树本质是自平衡的二叉查找树。

使用分离链表法的哈希表:

2 主要方法实现

2.1 初始化

创建HashMap时,可指定初始容量和loadFactor。如果不指定,则使用默认值。

也可用一个Map实例来创建新Map。

2.1.1 哈希表的尺寸

当指定initialCapacity时,会通过计算得到tableSize。HashMap中哈希表长度,要求始终是2的次方数。便于使用&与运算计算余数。

tableSize-1的二进制表示,除最高位外其余全是1;与key的hashCode做与运算,即可得到对哈希表长度的余数。 如,tableSizeFor(12)=16tableSizeFor(32)=32

2.1.2 延迟创建哈希表

在HashMap的构造方法中,并没有立即初始化哈希表,而是在发生第一次put时,才创建哈希表。

2.2 put实现

先看hashCode计算,HashMap中做了优化。 核心逻辑在putVal()中,逻辑如下:

  1. 如果table为null或length为0,则初始化哈希表;
  2. 根据哈希值,使用与运算计算桶下标i;
  3. 如果桶为空,则指直接放入;
  4. 如果桶不为空,则在红黑树或链表中put;
  5. 如果桶中已存在key,则覆盖旧值,返回;
  6. 最后,真的新增了一个entry后,判断是否需要扩容。

注意:

  • 在判断key是否已存在时,要求hash值相同,且要求equals()返回true;
  • 当桶中entry是链表时,使用尾插法
  • HashMap中先执行put,后处理扩容;由于使用size > threshold判断,不会导致无效扩容。如容量为16,负载因子为0.75,threshold=12;当插入第13个key时,才会触发扩容;
  • afterNodeInsertion()定义了插入entry后的额外动作,是一个扩展点。
  • 参数onlyIfAbsent为true时,put操作将只插入新key,不覆盖已存在的key(除非旧value为null)。

2.3 resize实现

主要逻辑如下:

  • 当对HashMap第一次put时,将通过resize()来触发哈希表的初始化。
  • 先将threshold设置为触发下次扩容时的键值对总数。如当前哈希表长度为16,threshold=12;扩容后哈希表长度为32,threshold=24;
  • 遍历每一个桶,将其中的键值对重新rehash。

需要注意,resize时对链表也采用尾插法。

为什么resize能减少哈希冲突程度呢?

比如,在长度为16的哈希表中,在index=2的桶中,有key=2、18、34、82、98共5个key;

在resize后哈希表长度变为32,2、34、98将仍在index=2的桶中,而18、82会被移动到index=2+16的桶中。

从而降低了哈希桶中哈希冲突

2.4 get实现

get方法调用了getNode(),在key不存在时返回null。

getOrDefault()在key不存在时,可以返回给定值。

2.5 size相关方法

实现很简单。

2.6 contains相关方法

containsKey时间复杂度是o(1)。 containsValue是O(n),与size成正比。

2.7 树化和反树化

2.7.1 树化

只有向HashMap真的插入一个键值对时,才可能触发桶的树化。

当某个哈希桶中键值对数量大于等于7时,将尝试对链表树化:binCount即桶中entry的计数 但是,当哈希表长度小于64时,不会树化,而是扩容。

2.7.2 反树化

反树化实现是java.util.HashMap.TreeNode#untreeify。 当哈希桶中键值对数量减少时,都可能触发反树化。如remove、resize等操作。

桶由树退化为链表的条件,是桶中entry数小于等于6时。

3 总结

3.1 与JDK7比较

JDK7中,HashMap的桶不会树化,始终是链表结构。在JDK8中,HashMap引入了红黑树

扩容差异:

  • 在JDK7中,当HashMap的容量达到阈值时,才会触发扩容。
  • 在JDK8中,除了容量达到阈值外,当哈希表长度小于64时,某个桶中的链表长度大于等于7时,也会触发扩容。(树化只是提高了桶中查询效率,而扩容直接削弱了哈希冲突程度,效果更好

链表的插入方式:

  • 在JDK7中,put、resize操作时,对链表使用头插法,在并发扩容时,可能形成环形数据结构,导致死循环;
  • 在JDK8中采用头插法,来避免出现死循环。

3.2 注意事项

  • 在设置HashMap的初始容量时,应考虑map中的键值对预期数及其负载因子,以尽量减少rehash操作的数量。
  • 作为一般规则,默认负载因子(0.75)在时间和空间成本之间提供了一个很好的权衡,最好不要自己指定。


转载来源:https://juejin.cn/post/7420088865464696859

相关文章
|
2月前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
46 1
|
2月前
|
存储 安全 Java
Java Map新玩法:探索HashMap和TreeMap的高级特性,让你的代码更强大!
【10月更文挑战第17天】Java Map新玩法:探索HashMap和TreeMap的高级特性,让你的代码更强大!
66 2
|
2月前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
64 2
|
2月前
|
存储 缓存 安全
HashMap VS TreeMap:谁才是Java Map界的王者?
HashMap VS TreeMap:谁才是Java Map界的王者?
78 2
|
2月前
|
存储 Java 程序员
Java面试加分点!一文读懂HashMap底层实现与扩容机制
本文详细解析了Java中经典的HashMap数据结构,包括其底层实现、扩容机制、put和查找过程、哈希函数以及JDK 1.7与1.8的差异。通过数组、链表和红黑树的组合,HashMap实现了高效的键值对存储与检索。文章还介绍了HashMap在不同版本中的优化,帮助读者更好地理解和应用这一重要工具。
55 5
|
2月前
|
Java
用java搞定时任务,将hashmap里面的值存到文件里面去
本文介绍了如何使用Java的`Timer`和`TimerTask`类创建一个定时任务,将HashMap中的键值对写入到文本文件中,并提供了完整的示例代码。
38 1
用java搞定时任务,将hashmap里面的值存到文件里面去
|
2月前
|
存储 Java API
详细解析HashMap、TreeMap、LinkedHashMap等实现类,帮助您更好地理解和应用Java Map。
【10月更文挑战第19天】深入剖析Java Map:不仅是高效存储键值对的数据结构,更是展现设计艺术的典范。本文从基本概念、设计艺术和使用技巧三个方面,详细解析HashMap、TreeMap、LinkedHashMap等实现类,帮助您更好地理解和应用Java Map。
59 3
|
2月前
|
存储 缓存 安全
在Java的Map家族中,HashMap和TreeMap各具特色
【10月更文挑战第19天】在Java的Map家族中,HashMap和TreeMap各具特色。HashMap基于哈希表实现,提供O(1)时间复杂度的高效操作,适合性能要求高的场景;TreeMap基于红黑树,提供O(log n)时间复杂度的有序操作,适合需要排序和范围查询的场景。两者在不同需求下各有优势,选择时需根据具体应用场景权衡。
33 2
|
2月前
|
存储 安全 Java
Java Map新玩法:深入探讨HashMap和TreeMap的高级特性
【10月更文挑战第19天】Java Map新玩法:深入探讨HashMap和TreeMap的高级特性,包括初始容量与加载因子的优化、高效的遍历方法、线程安全性处理以及TreeMap的自然排序、自定义排序、范围查询等功能,助你提升代码性能与灵活性。
26 2
|
3月前
|
设计模式 Java
结合HashMap与Java 8的Function和Optional消除ifelse判断
`shigen`是一位致力于记录成长、分享认知和留住感动的博客作者。本文通过具体代码示例探讨了如何优化业务代码中的if-else结构。首先展示了一个典型的if-else处理方法,并指出其弊端;然后引入了策略模式和工厂方法等优化方案,最终利用Java 8的Function和Optional特性简化代码。此外,还提到了其他几种消除if-else的方法,如switch-case、枚举行、SpringBoot的IOC等。一起跟随shigen的脚步,让每一天都有所不同!
39 10
结合HashMap与Java 8的Function和Optional消除ifelse判断