HashMap
目录
HashMap是什么?
为什么要使用HashMap?
HashMap存储元素原理(put⽅法)
扰动函数
前置知识
异或运算
&运算
为什么使用扰动函数
实验验证扰动函数
常见问题
HashMap的默认长度是多少?
HashMap是先扩容在插入数据还是先插数据在扩容
HashMap链表转红黑树 和 红黑树退化为链表的条件分别是什么
HashMap链表转红黑树
HashMap红黑树退化成链表
HashMap和Hashtable的区别
HashMap的搜索的时间复杂度是多少?
HashMap是什么?
- JDk1.7:HashMap 数据结构为 数组+链表(JDk1.7)。
- JDK1.8中增加了红黑树,其中:链表的节点存储的是一个 Entry 对象,每个Entry 对象存储四个属性(hash,key,value,next) 。
为什么要使用HashMap?
对于要求查询次数特别多,查询效率比较高同时插入和删除的次数比较少的情况下,通常会选择ArrayList,因为它的底层是通过数组实现的。对于插入和删除次数比较多同时在查询次数不多的情况下,通常会选择LinkedList,因为它的底层是通过链表实现的。
但现在同时要求插入,删除,查询效率都很高的情况下我们该如何选择容器呢?
那么就有一种新的容器叫HashMap,他里面既有数组结构,也有链表结构,所以可以弥补相互的缺点。而且HashMap主要用法是get()和put() 。
HashMap存储元素原理(put⽅法)
扰动函数
在HashMap存放元素时候有这样一段代码来处理哈希值,这是java 8的散列值扰动函数,用于优化散列效果;
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
前置知识
异或运算
异或运算是一种布尔运算,通常表示为符号“^”,它的结果为两个操作数相应位上的数值相异或得到的值。如果两个相应位的值相同,则结果为0,否则结果为1。具体来说,如果输入的两个二进制数的某一位相同,则该位上的异或结果为0,否则为1。
&运算
&运算是位运算符之一,用来执行按位与操作。它对两个操作数的每一位执行逻辑“与”操作,即如果两个操作数的对应位都是1,则结果为1,否则为0。&运算符通常用于处理二进制数据,例如在编程语言中进行位操作。
为什么使用扰动函数
理论上来说字符串的hashCode是一个int类型值,那可以直接作为数组下标了,且不会出现碰撞。但是这个hashCode的取值范围是[-2147483648, 2147483647],有将近40亿的长度,谁也不能把数组初始化的这么大,内存也是放不下的。
我们默认初始化的Map大小是16个长度 DEFAULT_INITIAL_CAPACITY = 1 << 4,所以获取的Hash值并不能直接作为下标使用,需要与数组长度进行取模运算得到一个下标值,也就是我们上面做的散列列子。
那么,hashMap源码这里不只是直接获取哈希值,还进行了一次扰动计算,(h = key.hashCode()) ^ (h >>> 16)。把哈希值右移16位,也就正好是自己长度的一半,之后与原哈希值做异或运算,这样就混合了原哈希值中的高位和低位,增大了随机性。计算方式如下图;
说白了,使用扰动函数就是为了增加随机性,让数据元素更加均衡的散列,减少碰撞。
从上面的分析可以看出,扰动函数使用了哈希值的高半区和低半区做异或,混合原始哈希码的高位和低位,以此来加大低位区的随机性。
但看不到实验数据的话,这终究是一段理论,具体这段哈希值真的被增加了随机性没有,并不知道。所以这里我们要做一个实验,这个实验是这样做;
选取10万个单词词库
定义128位长度的数组格子
分别计算在扰动和不扰动下,10万单词的下标分配到128个格子的数量
统计各个格子数量,生成波动曲线。如果扰动函数下的波动曲线相对更平稳,那么证明扰动函数有效果。
实验验证扰动函数
扰动函数对比方法
public class Disturb {public static int disturbHashIdx(String key, int size) {return (size - 1) & (key.hashCode() ^ (key.hashCode() >>> 16));}public static int hashIdx(String key, int size) {return (size - 1) & key.hashCode();}}
- disturbHashIdx 扰动函数下,下标值计算
- hashIdx 非扰动函数下,下标值计算
单元测试
// 10万单词已经初始化到words中
@Test
public void test_disturb() {Map<Integer, Integer> map = new HashMap<>(16);for (String word : words) {// 使用扰动函数int idx = Disturb.disturbHashIdx(word, 128);// 不使用扰动函数// int idx = Disturb.hashIdx(word, 128);if (map.containsKey(idx)) {Integer integer = map.get(idx);map.put(idx, ++integer);} else {map.put(idx, 1);}}System.out.println(map.values());
}
以上分别统计两种函数下的下标值分配,最终将统计结果放到excel中生成图表。
扰动函数散列图表
以上的两张图,分别是没有使用扰动函数和使用扰动函数的,下标分配。实验数据;
- 10万个不重复的单词
- 128个格子,相当于128长度的数组
未使用扰动函数
使用扰动函数
- 从这两种的对比图可以看出来,在使用了扰动函数后,数据分配的更加均匀了。
- 数据分配均匀,也就是散列的效果更好,减少了hash的碰撞,让数据存放和获取的效率更佳。
常见问题
HashMap的默认长度是多少?
严格意义说,HashMap的默认长度是0,但是长度为0的时候,第一次插入数据的时候若判断当前长度为0则直接扩容到16.leng
HashMap是先扩容在插入数据还是先插数据在扩容
- 若判断长度=0时则是先扩容再插入数据
- 若长度不为0则是先插入数据再扩容
HashMap链表转红黑树 和 红黑树退化为链表的条件分别是什么
先展示一下HashMap里的三个常量
HashMap链表转红黑树
- 链表的节点数量(包括新增节点)大于等于树化阈值
- HashMap的容量(Node数组的长度)大于等于最小树化容量值。
(延伸题) 若链表节点数超过树化阈值,但是HashMap的容量小于树化容量会如何?
会进行一次扩容,使其大于或等于最小束花容量值,随后在进行树化
HashMap红黑树退化成链表
当红黑树中的元素个数小于等于6时,该红黑树会被转换为链表。这是因为,当元素数量较少时,红黑树的性能反而会不如链表。
HashMap和Hashtable的区别
HashMap | Hashtable | |
父类 | 继承AbstractMap,AbstractMap又实现了 Map 接口 | Hashtable 继承了 Dictionary 并实现Map接口 |
默认值不同 | 默认的初始数组长度是 16, 默认的加载因子是 0.75, 每次扩容变成之前数组的 2 倍长度 | 默认的初始数组长度是 11, 默认的加载因子是 0.75, 每次扩容是之前数组的 2 倍长度加 1 |
空值 | 只能有一个key为空 允许value为空。 | key,value 都不允许为空。 |
获取数组下标的方式 | | |
底层数据结构不同 | 数组+链表+红黑树 | 数组+链表 |
线程安全问题 | false | true |
HashMap的搜索的时间复杂度是多少?
若不hash冲突则是:O(1)
链表则是:O(n)
红黑树是:O(logn)
相关文章:

HashMap
目录 HashMap是什么? 为什么要使用HashMap? HashMap存储元素原理(put⽅法) 扰动函数 前置知识 异或运算 &运算 为什么使用扰动函数 实验验证扰动函数 常见问题 HashMap的默认长度是多少? HashMap是先扩…...

数据结构初阶 —— 树(堆)
目录 一,堆 堆的概念 向下调整法(数组) 向上调整法(数组) 堆的创建(建堆) 堆的实现 一,堆 堆的概念 如有个关键码的集合K{,,,...…...

一文看懂低代码,5分钟从入门到原理全搞定
全球低代码市场已经走过了近20年,中国低代码市场近5年经历了百花齐放的广泛探索阶段,更旺盛的市场需求逐步在被激发。现在,让我们按下暂停键,看看这些产品给我们呈现了低代码市场一幅怎样的百景图。 低代码平台简介 广义上的低代…...

MetaERP系统主要干什么的,华为自研ERP的路子是否可以效仿?
近日,华为成功研发出自主可控的MetaERP系统,并完成了对旧有ERP系统的替换。该系统采用全栈自主可控技术,基于华为欧拉操作系统、GaussDB等根技术,采用云原生架构、元数据多租架构、实时智能技术等,提高业务效率&#x…...

自动驾驶——离散LQR的黎卡提方程Riccati公式推导与LQR工程化
1.LQR Question Background 之前写过连续系统的黎卡提方程Riccati推导,但是考虑到实际工程落地使用的是离散系统,于是又进行了离散黎卡提方程Riccati的公式推导。 2.Proof of Riccati Equation Formula for Discrete Systems 工程化落地,就…...

28.Mybatis的入门
目录 一、Mybatis的入门。 (1)Mybatis的简介。 (2)Mybatis的快速入门。 (2.1)快速入门。 (2.2)UserMapper.xml文件。 (2.3)sqlMapConfig.xml文件。 …...
Android Jetpack 从使用到源码深耕【ViewModel从实践到原理 】(三)
上文,我们通过简单的ViewModel使用源码入手,对其源码进行阅读,原理进行了简单总结,简单来说,ViewModel是通过Activity的onRetainNonConfigurationInstance 与 getLastNonConfigurationInstance的自动调用,实现了 ViewModel数据的存储和恢复,数据存储在ViewModelStore的m…...
什么性格的人适合报考环境科学类专业?高考选专业
环境科学类专业包括有:环境科学与工程,环境工程,环境科学,环境生态工程,环保设备工程,资源环境科学,水质科学与技术。 环境对于未来是一个极其重要的方向,需要学生具备一定的科学素…...
Python中的异常处理机制可以帮助程序员在程序运行过程中遇到错误时进行处理
Python中的异常处理机制可以帮助程序员在程序运行过程中遇到错误时进行处理,防止程序崩溃或出现不可预测的错误。 Python中的异常处理使用try-except语句。try语句块包含可能会出现异常的代码,而except语句块则定义了出现异常时应该执行的操作。下面是一…...

TCP之报文格式解析
TCP网络协议是较常用的,也基本上都会接触,那么来简单了解下它吧。TCP 是一种面向连接的、可靠的传输协议,它能够将数据分成一些小块,并通过 Internet 进行传输。在 TCP 中,数据被分割成一些称为 TCP 报文段(…...
qemu-基础篇(二)——裸机 arm 程序环境搭建
文章目录 测试代码makefile运行 qemu调试 qemuGDB 常用命令 裸机篇系列文章主要用于熟悉 arm 汇编及处理器结构 测试代码 _start:ldr r0, 0X020C4068 /* CCGR0 */ldr r1, 0XFFFFFFFF str r1, [r0]ldr r0, 0X020C406C /* CCGR1 */str r1, [r0]ldr r0, 0X020C4070 …...
JSP+SQL基于JSP的学生信息管理系统(源代码+论文+答辩PPT)
随着学校规模的不断扩大,学生数量急剧增加,有关学生的各种信息也成倍增长。面对如此庞大的信息量,开发学生信息管理系统来提高学生管理工作的效率就成为必然。通过该系统,可以做到信息的规范管理、科学统计和快速查询,…...

docker上部署程序后无法连接数据库的问题
咱就是说,这个问题差点给我劝退docker。下面说下环境情况。 装了个javaweb程序容器,装了个数据库容器,javaweb容器就是链接不上数据库。 咱也是跟着菜鸟教程的容器互联步骤简历网络链接: 并且启动时增加--networkxxx 都加入到了…...

Ucore lab4
实验目的 了解内核线程创建/执行的管理过程了解内核线程的切换和基本调度过程 实验内容 练习一:分配并初始化一个进程控制块 1.内核线程及管理 内核线程是一种特殊的进程,内核线程与用户进程的区别有两个:内核线程只运行在内核态&#x…...

AI失业潮来袭,某些部门裁员过半
历史的车轮滚滚向前,每次生产力的大幅跃进,都会造成一批失业潮。想当年,纺纱机的出现让无数手工作坊的织布师傅失业。如今,在AI技术的催化下,同样的事正在互联网行业的各个领域重演。 疯狂的裁员浪潮 “AI15秒做的&am…...

git 撤销add/commit,以及更换源命令
前言:主要是为了自己方便记录,省的每次都查找一下这些命令 1、当我们只是想撤回commit,保留add .的时候,可以用下方代码 git reset --soft HEAD^ 2、当我们想撤回commit以及add .的时候,可以用下方代码 git reset…...
3dMax需要什么样的硬件环境才能更好的工作?
3dMax官方给出了系统要求的列表 ,可用于帮助确保系统中的硬件能够与他们的软件一起工作。但是,这个“系统要求”列表只涵盖了运行软件所需硬件的最基本知识,而不是实际提供最佳性能的硬件。由于这些列表的不一致程度,我们花时间进行测试以确定运行 3dMax 的最佳硬件。基于…...

python-使用Qchart总结4-绘制多层柱状图
1、上代码 import sysfrom PyQt5.QtChart import QChart, QChartView, QBarCategoryAxis, QValueAxis, QBarSeries, QBarSet from PyQt5.QtGui import QPainter, QColor from PyQt5.QtWidgets import QMainWindow, QApplicationfrom untitled import Ui_MainWindow #从生成好的…...
Java学习笔记-02
目录 流程控制语句 分支语句 循环语句 Random随机数 数组 方法 流程控制语句 分为顺序语句(从上到下,依次执行),分支语句(if,else...)和循环语句(for,while,do...while) 分支语句 分为if与switch两大类 单分…...

中通快递财报预测:中通快递2023年收入和利润将大幅下降
来源:猛兽财经 作者:猛兽财经 市场对中通快递2023年的预测 卖方虽然预测中通快递(ZTO)在2023年的表现会很不错,但他们也预计中通快递今年的财务业绩将不会像去年那样好。 根据S&P Capital IQ的数据,卖…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...

elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
【SpringBoot自动化部署】
SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一,能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时,需要添加Git仓库地址和凭证,设置构建触发器(如GitHub…...
【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!
【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...