HashMap原理。图文并茂式解读。这些注意点你一定还不了解

2024-08-29 14:32

本文主要是介绍HashMap原理。图文并茂式解读。这些注意点你一定还不了解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

[TOC]

概述

本篇文章我们来聊聊大家日常开发中常用的一个集合类 - HashMap。HashMap 最早出现在 JDK 1.2中,底层基于散列算法实现。HashMap 允许 null 键和 null 值,在计算哈键的哈希值时,null 键哈希值为 0。HashMap 并不保证键值对的顺序,这意味着在进行某些操作后,键值对的顺序可能会发生变化。另外,需要注意的是,HashMap 是非线程安全类,在多线程环境下可能会存在问题。

属性详解

DEFAULTINITIALCAPACITY 默认初始容量MAXIMUM_CAPACITY 最大容量DEFAULTLOADFACTOR 默认负载因子TREEIFY_THRESHOLD 一个桶的树化阈值(超过此值会变成红黑树)UNTREEIFY_THRESHOLD 一个树的链表还原阈值(小于此值在resize的时候会变回链表)MINTREEIFYCAPACITY 哈希表的最小树形化容量(为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD)

table

HashMap中的数组(hash表)。hash表的长度总是在2^n。至于原因吗,后面专门会说的。数组里存储的是Node节点的数据

entrySet

Node 节点构成的 set

size

当前map中存储节点的数据

modCount

hashMap发生结构性变化的次数,节点转红黑树、扩容等操作。

threshold、loadFactor

扩容阙值和装载因子。

源码知识点必备

getGenericInterfaces和getInterfaces区别

getGenericInterfaces获取直接接口getInterfaces获取所有接口

ParameterizedType

是Type的子接口,表示一个有参数的类型。就是我们俗称的泛型。实现这个接口的类必须提供equals方法。

getRawType

返回最外层<>前面那个类型,即Map 的Map。

getActualTypeArguments

获取“泛型实例”中<>里面的“泛型变量”(也叫类型参数)的值,这个值是一个类型。因为可能有多个“泛型变量”(如:Map ),所以返回的是一个Type[]。注意:无论<>中有几层<>嵌套,这个方法仅仅脱去最外层的<>,之后剩下的内容就作为这个方法的返回值,所以其返回值类型是不确定的。

getOwnerType

获得这个类型的所有者的类型,主要对嵌套定义的内部类而言。列如对java.util.Map.Node 调用getOwnerType方法返回的是interface java.util.Map接口

comparableClassFor

HashMap类中有一个comparableClassFor(Object x)方法,当x的类型为X,且X直接实现了Comparable接口(比较类型必须为X类本身)时,返回x的运行时类型;否则返回null。通过这个方法,我们可以搞清楚一些与类型、泛型相关的概念和方法

(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)

hashCode与自己的高16为进行异或 。 这样更分散ps:& : 全部为1则为1,否则为0 偏0| : 有一个为1则为1,否则为0 偏1^ : 相同为0 不同为1 更加均衡。 均匀(分散)

hash表维护

在文章开头我们就解释了HashMap中table就是我们的hash表。直观上我们可以理解成一个开辟空间的数组。HashMap通过hash(key)这个方法获取hash值。然后通过hash值确定key在hash表中的位置((n - 1) & hash)。综合上图我们也会发现问题了。key的个数是无限的。但是我们的hash表是有限的。如何能保证hash(key)不会落在同一个位置呢。答案是不能。换句话说就是我们hash(key)无法保证。也就是hashMap会发生hash碰撞的。hash函数只能尽量避免hash碰撞。上面的(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)就是为了让hash更加分散点。这一点上面也作出了解释。

HashMap 数组长度是2^n ?

上面解释了hashmap中hash函数为什么要^ 。 那么深度源码的小伙伴可能会问,为什么hashmap默认容量是16以及后期每次扩容的时候为什么是翻倍扩容。简而言之。为什么hashMap数组长度永远是2的倍数呢。上面我们知道如何通过hash确定在数组中位置的。(n - 1) & hash关于这个n是数组的长度,hash就是key值通过hash函数计算出来的hash值。& 运算规则是: 全部为1则为1,否则为0假设目前hashMap容量是16 , 我们来看看在扩容前后我们key的在是数组中的索引。扩容前后经过图片鲜明的对比我们发现,扩容前后是不会影响原来数据(高位为0)的索引位置的。这里要注意的是并不是说所有数据不受影响,只要原来从右至左第五位为0的hash会受影响,其他不会。这样大大减少了数组位置调换的操作。性能上也大大的提高了。从这里也可以看出hashmap容量越大,扩容是越复杂,因为容量越大,需要换位置的索引越多。那么如果我们扩容是不是选择扩大2倍 , 我们看看会发生什么样情况。上图中是有16扩展成了24容量。这个时候我们会发现除了(从右至左)第五位以为第四位的数据也发生了变化。这样造成的接口是第四位和第五位的数据都会变化。这样增加了索引位置的数量。所以我们需要在每次扩容为原来的2倍。

神奇的hashmap遍历

做Java的肯定会遇到的一种情况是,为什么我的map遍历的顺序和我添加的顺序不一致呢。有时候我们做列表展示的时候对顺序是有要求的。但是hashmap偏偏和我们想的不一样。今天华仔带你看看为什么会出现这种神奇的遍历。

public final void forEach(Consumer<? super K> action) {Node<K,V>[] tab;if (action == null)throw new NullPointerException();if (size > 0 && (tab = table) != null) {int mc = modCount;for (int i = 0; i < tab.length;   i) {for (Node<K,V> e = tab[i]; e != null; e = e.next)action.accept(e.key);}if (modCount != mc)throw new ConcurrentModificationException();}
}

从上面的代码我们可以看出来hashmap在遍历时候,是先遍历数组然后取到数组中链表(红黑树)按照顺序获取node节点的。也即是说我们先按数组再按链表顺序。而不是按照你添加先后的顺序。而上面我们了解添加的node决定其位置的是key的hash值。所以这就解释了为什么hashmap遍历的时候和我们添加不一致的了。

put 流程跟踪


public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}

其他方法原理是相同的。值得注意的是remove后临界情况会发生红黑树转链表。所以转红黑树的这个阙值的选取有时候会影响性能的高低。下面看看put的实际源码吧。拜读下大佬的代码。

上面的代码可以看出来put实际调用的方法是putVal();int hash : key对应的hash值K key, : keyV value, : valueonlyIfAbsent : 如果存在则忽略,默认false表示新值会覆盖旧值boolean evict: 表示是否在构造table时调用


/**
* 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;
if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);
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 {for (int binCount = 0; ;   binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}
}modCount;
if (  size > threshold)resize();
afterNodeInsertion(evict);
return null;
}

寒暄一句

个人几天时间总结的,有网上前辈的总结,也有加入个人的想法。再次申明:以上图片部分来自网络。

加入战队

加入战队

微信公众号

微信公众号

这篇关于HashMap原理。图文并茂式解读。这些注意点你一定还不了解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

解读GC日志中的各项指标用法

《解读GC日志中的各项指标用法》:本文主要介绍GC日志中的各项指标用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、基础 GC 日志格式(以 G1 为例)1. Minor GC 日志2. Full GC 日志二、关键指标解析1. GC 类型与触发原因2. 堆

Java设计模式---迭代器模式(Iterator)解读

《Java设计模式---迭代器模式(Iterator)解读》:本文主要介绍Java设计模式---迭代器模式(Iterator),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录1、迭代器(Iterator)1.1、结构1.2、常用方法1.3、本质1、解耦集合与遍历逻辑2、统一

从原理到实战深入理解Java 断言assert

《从原理到实战深入理解Java断言assert》本文深入解析Java断言机制,涵盖语法、工作原理、启用方式及与异常的区别,推荐用于开发阶段的条件检查与状态验证,并强调生产环境应使用参数验证工具类替代... 目录深入理解 Java 断言(assert):从原理到实战引言:为什么需要断言?一、断言基础1.1 语

MySQL之InnoDB存储页的独立表空间解读

《MySQL之InnoDB存储页的独立表空间解读》:本文主要介绍MySQL之InnoDB存储页的独立表空间,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、独立表空间【1】表空间大小【2】区【3】组【4】段【5】区的类型【6】XDES Entry区结构【

MySQL中的表连接原理分析

《MySQL中的表连接原理分析》:本文主要介绍MySQL中的表连接原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、表连接原理【1】驱动表和被驱动表【2】内连接【3】外连接【4编程】嵌套循环连接【5】join buffer4、总结1、背景

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

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

Java Stream的distinct去重原理分析

《JavaStream的distinct去重原理分析》Javastream中的distinct方法用于去除流中的重复元素,它返回一个包含过滤后唯一元素的新流,该方法会根据元素的hashcode和eq... 目录一、distinct 的基础用法与核心特性二、distinct 的底层实现原理1. 顺序流中的去重

MySQL主从复制与读写分离的用法解读

《MySQL主从复制与读写分离的用法解读》:本文主要介绍MySQL主从复制与读写分离的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、主从复制mysql主从复制原理实验案例二、读写分离实验案例安装并配置mycat 软件设置mycat读写分离验证mycat读

Python的端到端测试框架SeleniumBase使用解读

《Python的端到端测试框架SeleniumBase使用解读》:本文主要介绍Python的端到端测试框架SeleniumBase使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全... 目录SeleniumBase详细介绍及用法指南什么是 SeleniumBase?SeleniumBase

Spring @Scheduled注解及工作原理

《Spring@Scheduled注解及工作原理》Spring的@Scheduled注解用于标记定时任务,无需额外库,需配置@EnableScheduling,设置fixedRate、fixedDe... 目录1.@Scheduled注解定义2.配置 @Scheduled2.1 开启定时任务支持2.2 创建