【HashMap源码学习】
HashMap的底层结构
HashMap是基于分离链表法解决散列冲突的动态散列表。
1、在jdk7中,使用的是“数组 + 链表”,发生散列冲突的时候键值对会用头插法添加到单链表中;
2、在jdk8中,使用的是“数组 + 链表 + 红黑树”,发生散列冲突的时候会使用尾插法添加到单链表中。如果链表的长度大于8且散列表容量大于64的时候,会将链表树化为红黑树。在扩容再散列时,如果红黑树的长度低于6则会还原为链表。
1)HashMap的数组长度保证是2的整数次幂,且默认数组容量是16,默认装载因子是0.75,扩容阈值是12,树化阈值是8(当一个桶中的元素个数大于等于8时进行树化),还原阈值是6(当一个桶中的元素个数小于等于6时把树转化为链表)。2)hashmap的 key 和 value 都支持null,key为null的键值对会直接映射到数组下表为0的桶中(因为null的hash值是0,取余映射到数组下标后也是table[0]的桶)。3)首次加入数据如果数组为空,则扩容,默认数组容量是16;数组容量到达阈值(12-24...)会扩容至原来容量2倍;链表长度大于8且数组容量小于64时,同样会扩容至原来容量2倍,数组容量到64时则会树化。
源码分析
1、putVal 存放数据
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {HashMap.Node<K, V>[] tab;HashMap.Node<K, V> p;int n, i;if ((tab = table) == null || (n = tab.length) == 0)// 如果数组为null或长度为0,则进行扩容:首次扩容数组长度为16,阈值为12n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)// 如果数组 tab[i]位置上是null,则将加入的 key-value 放入此数组节点tab[i] = newNode(hash, key, value, null);else {// 数组 tab[i]位置上有值,即 pHashMap.Node<K, V> e;K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))// tab[i]上元素的hash值和key值 和 新加入元素的hash值 key值都相同; 则 p保存到e中用于后续修改value值e = p;else if (p instanceof TreeNode) // 红黑树节点情况e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);else { // 单链表情况,尾插for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) { // p的下一节点是空的,则尾插新元素p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1)// 链表上大于8个元素了,树化(数组长度大于64后,才开始树化,否则仅扩容16-32-64)treeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))// 新加入的元素 和 单链表上元素 hash、key值都相同break;p = e; // 前有e = p.next,即 p指向p的下一个节点}}if (e != null) { // e不为空,则新加入的元素 hash、key 都重复了,则新值替换旧值V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;// 访问节点回调(用于 LinkedHashMap,默认为空实现)afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)// hashmap的元素个数大于阈值(12-24....)时,则进行扩容, 扩容后长度是原来长度的两倍resize();afterNodeInsertion(evict);return null;}
2、扩容
final Node<K,V>[] resize() {// 定义 旧数组 变量Node<K,V>[] oldTab = table;// 如果数组为 null 则旧容量置为0// 如数组不为 null 则旧容量为置为 数组的长度(划重点:数组的长度)int oldCap = (oldTab == null) ? 0 : oldTab.length;// 定义 旧扩容阈值 变量int oldThr = threshold;// 定义 新容量 新扩容阈值 变量为 0int newCap, newThr = 0;// 1、第一步// 如果旧容量 > 0(表示不是第一次添加元素,数组里面有元素)if (oldCap > 0) {// 极端情况:// 如果旧容量 >= 最大容量,则此时无法扩容,将扩容阈值设置为整数最大值,直接返回旧容量// static final int MAXIMUM_CAPACITY = 1 << 30;if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 普通情况:// oldCap << 1 旧容量扩容为原来的两倍// (新容量 < 最大容量) 且 (旧容量 >= 默认容量)else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// 扩容阈值扩大为原来的两倍newThr = oldThr << 1; // double threshold}// 使用非无参构造方法创建的map,第一次插入元素会走到这里else if (oldThr > 0)// 初始化容量 置为 扩容阈值newCap = oldThr;// 调用无参构造方法创建的map,第一次插入元素会走到这里else {// static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16// 新容量 默认为 16newCap = DEFAULT_INITIAL_CAPACITY;// 新扩容阈值 = 默认装载因子 * 默认初始化容量newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 带初始容量和负载因子的构造方法走这里if (newThr == 0) {// 使用容量乘以负载因子计算扩容阈值float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}// 最终计算的扩容阈值threshold = newThr;// 2、第二步// 使用新容量 创建新数组Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;// 如果旧数组不等于 null,则将旧数组上的键值对 再散列到新数组上if (oldTab != null) {// 遍历旧数组上的每个桶for (int j = 0; j < oldCap; ++j) {Node<K,V> e;// 如果此下标处的桶不为nullif ((e = oldTab[j]) != null) {// 传递给 e 后,置为空oldTab[j] = null;// 如果这个桶中只有一个元素if (e.next == null)// 则计算它在新桶中的位置并把它搬移到新桶中(也就是 直接再散列)newTab[e.hash & (newCap - 1)] = e;// 如果是红黑树else if (e instanceof TreeNode)// 以红黑树的方式再散列((TreeNode<K,V>)e).split(this, newTab, j, oldCap);// 以链表的形式再散列else { // preserve orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;// 如果元素的哈希值与旧数组长度的按位与运算结果为0,将元素添加到低位链表中。// 如果低位链表为空,将该元素作为链表的头节点,否则将该元素添加到低位链表的尾部。if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}// 如果元素的哈希值与旧数组长度的按位与运算结果不为0,将元素添加到高位链表中。// 如果高位链表为空,将该元素作为链表的头节点,否则将该元素添加到高位链表的尾部。else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}
相关文章:
【HashMap源码学习】
HashMap的底层结构 HashMap是基于分离链表法解决散列冲突的动态散列表。 1、在jdk7中,使用的是“数组 链表”,发生散列冲突的时候键值对会用头插法添加到单链表中; 2、在jdk8中,使用的是“数组 链表 红黑树”,发…...
Git关联本地仓库和远程仓库
Step 1 添加远程仓库: git remote add <远程仓库别名><远程仓库地址> Step 2 git push -u <远程仓库名><分支名> 查看远程仓库: git remote -v 拉取远程仓库内容: 拉取服务器仓库过程中,如果本地和服务器有文件冲突,则会拉取失…...
【Django】在vscode中新建Django应用并新增路由
文章目录 打开一个终端输入新建app命令在app下的views.py内写一个视图app路由引入该视图项目路由引入app路由项目(settings.py)引入app(AntappConfig配置类)运行项目 打开一个终端 输入新建app命令 python manage.py startapp antapp在app下的views.py内…...
DT浏览器首页征集收录海内外网址
DT浏览器首页征集收录海内外网址,要求页面整洁,内容丰富,知识性和可读性强,符合大众价值观,不含恶意代码...
便携解码耳放
想象一下,你正在拥挤的地铁上,耳机里传来的音乐却仿佛带你置身于音乐厅,每一个音符都清晰、动人。这不是科幻小说,而是便携解码耳放(DAC/AMP)带给你的真实体验。无论你是在旅行、通勤还是在咖啡馆里工作&am…...
响应式编程框架Reactor之 Flux 和 Mono 的介绍和区别
Flux和Mono在Reactor框架中都是响应式编程模型的重要概念,它们在处理异步数据流时发挥着重要作用,两者之间也存在一些差异。 Mono的介绍 基本概念: Mono是Reactor中的一个类,它表示一个异步的单个值或零个值的结果。Mono可以看作是一个特殊的Publisher,用于产生数据流,…...
2.3 openCv 对矩阵执行掩码操作
在矩阵上进行掩模操作相当简单。其基本思想是根据一个掩模矩阵(也称为核)来重新计算图像中每个像素的值。这个掩模矩阵包含的值决定了邻近像素(以及当前像素本身)对新的像素值产生多少影响。从数学角度来看,我们使用指定的值来做一个加权平均。 具体而言,掩模操作通常涉…...
贪心算法(三) ---cmp_to_key, 力扣452,力扣179
目录 cmp_to_key 比较函数 键函数 cmp_to_key 的作用 使用 cmp_to_key 代码解释 力扣452 ---射气球 题目 分析 代码 力扣179 ---最大数 题目 分析 代码 cmp_to_key 在Python中,cmp_to_key 是一个函数,它将一个比较函数转换成一个键函数…...
学生信息管理系统详细设计文档
一、设计概述 学生信息管理系统是一个用于管理学生信息的软件系统,旨在提高学校对学生信息的管理效率。本系统主要包括学生信息管理、课程信息管理、成绩信息管理、班级信息管理等功能模块。详细设计阶段的目标是确定各个模块的实现算法,并精确地表达这…...
leetcode10 -- 正则表达式匹配
题目描述: 给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 . 和 * 的正则表达式匹配。 . 匹配任意单个字符* 匹配零个或多个前面的那一个元素 所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。 示例 1࿱…...
Binius-based zkVM:为Polygon AggLayer开发、FPGA加速的zkVM
1. 引言 近日,ZK硬件加速巨头Irreducible和Polygon团队宣布联合开发生产级的Binius-based zkVM,用于助力Polygon AggLayer,实现具有低开销、硬件加速的binary proofs。 Irreducible(曾用名为Ulvetanna)团队 Benjamin …...
基于 HTML+ECharts 实现的大数据可视化平台模板(含源码)
构建大数据可视化平台模板:基于 HTML 和 ECharts 的实现 大数据的可视化对于企业决策、市场分析和业务洞察至关重要。通过直观的数据展示,团队可以快速理解复杂的数据模式,发现潜在的业务机会。本文将详细介绍如何利用 HTML 和 ECharts 实现一…...
特征工程在机器学习中的重要性
特征工程在机器学习中的重要性 特征工程在机器学习中占据着至关重要的地位,它是连接原始数据与机器学习模型之间的桥梁。通过特征工程,我们可以将原始数据转换为机器学习算法能够有效利用的形式,从而提高模型的性能和准确性。以下是特征工程…...
【css】flex布局父元素宽度或高度无法被子元素撑开-bug记录
简言 flex布局父元素宽度或高度无法被子元素撑开问题。 解决方案: 手动计算子元素内容所占宽高,手动赋值给父元素即可。 flex布局宽高度问题 flex布局现在是特别常见得布局方式。 在此记录一个注意点:flex布局在不换行得情况下,…...
Music Tag Editor Pro for Mac:强大的音频标签管理工具
Music Tag Editor Pro for Mac是一款专为Mac系统设计的音频标签管理工具,其简易直观的操作界面和强大的功能深受用户喜爱。 这款软件的核心功能在于它能够批量编辑各类音频文件的标签。无论是修改元数据、重命名文件,还是转换音乐标签的文本编码&#x…...
2024秋招算法
文章目录 参考资料一 数组1.1 二分查找1.2 移除元素1.3 长度最小的子数组1.4 螺旋矩阵1.5 在排序数组中查找元素的第一个和最后一个位置 二 链表2.1 移除链表元素2.2 设计链表2.3 反转链表2.4 两两交换链表中的节点2.5 删除链表的倒数第N个节点2.6 链表相交2.7 环形链表II 三 哈…...
El-Table 表格的表头字段切换
最近写了一个小功能,比较有意思,特此博客记录。 提出需求:需要表头字段变化,但是我在官网上的表格相关上查找,没有发现便捷方法。 于是我有两个想法:1.做三个不同的表格。2.做一个表格使用不同的表头字段。…...
分布式事务 详解
1.简介 2.本地事务失效问题 可以使用AOP starter aspectJ 代理 这样就可以拿到它的上下文的代理对象,当然是有这样的需求才这么做 如果你的事务只是想默认的传播行为,共用上面的事务,就可以不用这个啦 详情请去了解 Raft 算法 还有 pa…...
【git】太大了失败: fatal: fetch-pack: invalid index-pack output
#‘’ Git仓库过大致使clone失败的解决方法 上述大神的方法,亲测有效 中途失败: 太大了 fetch-pack: unexpected disconnect while reading sideband packet fatal: early EOF fatal: fetch-pack: invalid index-pack output关闭压缩 git config --global core.…...
在 ArchLinux 上编译运行 axmol 引擎
本文将在 Windows 10 上安装 Arch WSL 中编译 axmol 请确保 WSL2 已正确安装 1. 在微软应用商店安装 ArchLinux 2. 打开 Arch,按照提示输入用户名和密码,尽量简单 3. 配置清华源,速度快的起飞,否则,各种包会安装失败…...
云计算的三种服务模式
云计算的三种主要服务模式分别是基础设施即服务(IaaS)、平台即服务(PaaS)和软件即服务(SaaS)。每种服务模式都提供不同级别的抽象和管理,满足不同的需求和用例。以下是对这三种服务模式的详细介…...
Pytorch使用教学1-Tensor的创建
0 导读 在我们不知道什么是深度学习计算框架时,我们可以把PyTorch看做是Python的第三方库,在PyTorch中定义了适用于深度学习的张量Tensor,以及张量的各类计算。就相当于NumPy中定义的Array和对应的科学计算方法,正是这些基本数据…...
R语言统计分析——数据管理4
参考资料:R语言实战【第2版】 1、数学函数 abs(x):绝对值 sqrt(x):平方根 ceiling(x):不小于x的最小整数 floor(x):不大于x的最大整数 trunc(x):向0的方向截取x中的整数部分 round(x,digitsn)&#…...
用uniapp 及socket.io做一个简单聊天app 2
在这里只有群聊,二个好友聊天,可以认为是建了一个二人的群聊。 const express require(express); const http require(http); const socketIo require(socket.io); const cors require(cors); // 引入 cors 中间件const app express(); const serv…...
Si24R03:高度集成的低功耗SOC芯片中文资料
Si24R03是一款高度集成的低功耗SOC芯片,具有低功耗、Low Pin Count、宽电压工作范围,集成了13/14/15/16位精度的 ADC、LVD、UART、SPI、I2C、TIMER、WUP、IWDG、RTC、无线收发器等丰富的外设。 合封说明:Si24R03为CSM32RV003和Si24R1的合封芯…...
K8s-控制器
一 为什么使用控制器 pod控制器 作用:1.pod类型资源删除,不会重建 2.控制器可以帮助用户监控,并保证节点上运行定义好的pod副本数 3.pod超过或低于用户期望,控制器会创建、删除pod副本数量 控制器类型&am…...
Meta 发布 LLAMA 3.1;特斯拉无人出租车推迟至 10 月;谷歌将向 Waymo 再投 50 亿美元
先瞧一下 Chat 和 Agent 的差异。 Chat(聊天):纯粹的 Chat,宛如一个主要由“大脑与嘴”组成的智能体,着重于信息处置和语言沟通。诸如 ChatGPT 这般的系统,其能够领会用户的询问,给出有益且连贯…...
C 语言基础概念总结
C 语言基础概念总结 一、数据类型 目录 C 语言基础概念总结 一、数据类型 基本数据类型 构造数据类型 二、变量与常量 三、运算符与表达式 算术运算符 关系运算符 逻辑运算符 赋值运算符 自增自减运算符 四、控制流语句 顺序结构 选择结构 循环结构 五、函数 …...
Django教程(000):初识Django
Django 是一个高级 Python Web 框架,旨在快速开发、简洁、实用。Django 提供了众多内置功能,使得开发者可以专注于编写应用程序的业务逻辑,而不需要过多关注底层细节。以下是 Django 的详细介绍: 1. Django 简介 Django 是一个开放源代码的 Web 框架,由 Python 编写,最…...
SQLynx数据库管理工具
背景:业主对网络安全要求比较高,不提供VPN等远程工具,也不能开放3306端口到互联网。那怎么样运维数据库就是个难题?找到了SQLynx这个可以网页访问的数据库管理工具,给大家分享一下。 1.介绍 SQLynx原名SQL Studio&…...
Java基础06:变量,常量,作用域(狂神说Java)
一.变量 有了static,即类变量,就可以不用new了可以直接调用,类变量之后再细讲 二.常量 三.变量的命名规范...
inflight 守恒建模
去上海博物馆参观古埃及文物展,人太多,体验很差,我可以当讲解员的,但没人听,都只为拍照发圈。 平心而论,老家殷墟可与之一战,建议将殷墟交给国家运营,而不是一个地级市文旅。 无心…...
HarmonyOS NEXT星河版零基础入门到实战
文章目录 一、HarmonyOS NEXT介绍学习内容1、鸿蒙APP开发2、能力套件开发3、全场景开发适合人群 持续更新中✒️总结 一、HarmonyOS NEXT介绍 放弃安卓框架之后,HarmonyOS NEXT成为真正独立于安卓、iOS的操作系统,堪称是一场史无前例的脱胎换骨。在其众多…...
测试开发面试题---JVM
JAVA的内存区域 程序计数器:线程私有的,保存当前线程的字节码文件。JAVA虚拟机栈:包含局部变量信息,用于方法的调用和执行。本地方法栈:与JAVA虚拟机栈类似,但只服务于本地方法。堆:所有线程共…...
python库 - jsonpath
JSONPath 是一种用于从 JSON 数据中提取数据的查询语言,类似于 XML 中的 XPath。它允许通过路径表达式来导航和查询 JSON 结构中的数据。JSONPath 在处理 API 响应、配置文件和复杂数据结构时非常有用。 以下是一些常用的 JSONPath 表达式及其功能: $&…...
[RK3588][Android12] Android->OTA包超过4个G导致打包失败
测试平台 Platform: RK3588 OS: Android12 问题说明: 有的客户需要往系统中内置大量apk,这样就导致最终打包的OTA包超过4个G,从而导致打包OTA的时候报错:Zipfile size would require ZIP64 extensions 解决方法: 可能…...
(雷达数据处理中的)跟踪算法(3) – 可用于目标跟踪实践的数据集介绍解析
说明 本博文作为跟踪算法系列博文的第3篇,对可用于目标跟踪的一份数据集进行了介绍,本文介绍的这份数据集将用于后续博文的目标跟踪实践。读者在阅读本博文前,建议先看看本系列的第一篇博文[1]:(雷达数据处理中的)跟踪…...
【C语言报错已解决】Use of Uninitialized Variable
🎬 鸽芷咕:个人主页 🔥 个人专栏: 《C干货基地》《粉丝福利》 ⛺️生活的理想,就是为了理想的生活! 引言: 在编程中,未初始化的变量是一个常见的问题,它可能导致程序的行为变得不可预测。未初…...
3 Go语言的变量声明
本专栏将从基础开始,循序渐进,由浅入深讲解Go语言,希望大家都能够从中有所收获,也请大家多多支持。 查看相关资料与知识库 专栏地址:Go专栏 如果文章知识点有错误的地方,请指正!大家一起学习,…...
PyMySQL库的使用方法
过程和步骤: 安装 PyMySQL 首先,需要使用 pip 安装 PyMySQL 库: pip install pymysql连接数据库 使用 PyMySQL.connect() 方法可以建立到 MySQL 数据库的连接: import pymysql# 配置数据库连接参数 config {host: localhost…...
iOS 创建一个私有的 CocoaPods 库
创建一个私有的 CocoaPods 库(pod)涉及几个步骤,包括设置私有的 Git 仓库、创建 Podspec 文件、发布到私有仓库等等。以下是详细步骤: 设置私有 Git 仓库 首先,在 GitHub、GitLab 或 Bitbucket 上创建一个新的私有仓库…...
Linux_实现UDP网络通信
目录 1、实现服务器的逻辑 1.1 socket 1.2 bind 1.3 recvfrom 1.4 sendto 1.5 服务器代码 2、实现客户端的逻辑 2.1 客户端代码 3、实现通信 结语 前言: 在Linux下,实现传输层协议为UDP的套接字进行网络通信,网络层协议为IPv4&am…...
C# 代理模式
栏目总目录 概念 代理模式是一种结构型设计模式,它为其他对象提供一种代理以控制对这个对象的访问。在代理模式中,我们创建一个具有现有对象(称为“真实对象”或“被代理对象”)相同功能的代理对象。代理对象可以在客户端和目标对…...
【1】Python机器学习之基础概念
1、什么是机器学习 最早的机器学习应用——垃圾邮件分辨 传统的计算机解决问题思路: 编写规则,定义“垃圾邮件”,让计算机执行对于很多问题,规则很难定义规则不断变化 机器学习在图像识别领域的重要应用: 人脸识别…...
HashMap源码解析
目录 一:put方法流程 二:get方法 三:扩容机制 一:put方法流程 public V put(K key, V value) {return putVal(hash(key), key, value, false, true); }final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {No…...
[Javascript】前端面试基础3【每日学习并更新10】
Web开发中会话跟踪的方法有那些 cookiesessionurl重写隐藏inputip地址 JS基本数据类型 String:用于表示文本数据。Number:用于表示数值,包括整数和浮点数。BigInt:用于表示任意精度的整数。Boolean:用于表示逻辑值…...
C++自定义字典树结构
代码 #include <iostream> using namespace std;class TrieNode { public:char data;TrieNode* children[26];bool isTerminal;TrieNode(char ch){data ch;for (int i 0; i < 26; i){children[i] NULL;}isTerminal false;} }; class Trie { public:TrieNode* ro…...
dockerfile部署wordpress
1.将容器直接提交成镜像 [rootlocalhost ~]# docker commit 8ecc7f6b9c12 nginx:1.1 sha256:9a2bb94ba6d8d952527df616febf3fbc8f842b3b9e28b7011b50c743cd7b233b [rootlocalhost ~]# docker images REPOSITORY TAG IMAGE ID CREATED SIZE nginx …...
CSS(二)——CSS 背景
CSS 背景 CSS 背景属性用于定义HTML元素的背景。 CSS 背景属性 Property描述background简写属性,作用是将背景属性设置在一个声明中。background-attachment背景图像是否固定或者随着页面的其余部分滚动。background-color设置元素的背景颜色。background-image把…...
开机出现grub无法进入系统_电脑开机出现grub解决方法
最近有小伙伴问我电脑开机出现grub无法进入系统怎么回事?电脑开机出grub的情况有很多,电脑上安装了Linux和Win10双系统,但是由于格式化删除了Linux之后,结果win10开机了之后,直接显示grub>,无法…...