当前位置: 首页 > news >正文

HashMap源码阅读解惑

HashMap的hash函数(1.8)

首先1.7的是四次扰动,1.8做了优化。

        简单的说就是对key做hashCode操作,然后将得到的32为散列值向右位移16位,再与hashCode做异或计算。实质上是把一个数的低16位与他的高16位做异或运算。

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

首先 h = key.hashCode()是key对象的一个hashCode,每个不同的对象其哈希值都不相同,其实底层是对象的内存地址的32位的散列值,h >>> 16的意思是将hashcode右移16位,然后高位补0,然后再与(h = key.hashCode()) 异或运算得到最终的h值。

        为什么是异或运算呢?

    当然我们知道目的是为了让h的低16位更有散列性,但为什么是异或运算就更有散列性呢?而不是与运算或者或运算呢?这里我自己证明一下为什么异或就能够得到更好散列性。

先来看一下下面的这组运算

【与运算 1&0=0, 0&0=0, 0&1=0 都等于0 1&1=1 3次0,1次1】

【或运算 1&0=1, 1&1=1, 0&1=1 都等于1 0&0=0 3次1,1次0】

【异或运算 0&0=0, 1&1=0,而另外0&1=1, 1&0=1 2次1,2次0】

 上面是将0110和0101分别进行与、或、异或三种运算得到不同的结果,我们主要来看计算的过程:

        与运算:其中1&1=1,其他三种情况1&0=0, 0&0=0, 0&1=0 都等于0,可以看到与运算的结果更多趋向于0,这种散列效果就不好了,运算结果会比较集中在小的值

        或运算:其中0&0=0,其他三种情况 1&0=1, 1&1=1, 0&1=1 都等于1,可以看到或运算的结果更多趋向于1,散列效果也不好,运算结果会比较集中在大的值

        异或运算:其中0&0=0, 1&1=0,而另外0&1=1, 1&0=1 ,可以看到异或运算结果等于1和0的概率是一样的,这种运算结果出来当然就比较分散均匀了

        总的来说,与运算的结果趋向于得到小的值,或运算的结果趋向于得到大的值,异或运算的结果大小值比较均匀分散,这就是我们想要的结果,这也解释了为什么要用异或运算,因为通过异或运算得到的h值会更加分散,进而 h & (length-1)得到的index也会更加分散,哈希冲突也就更少。

为什么使用 hash & (length - 1) 作为数组的寻址算法?

        首先我们如果把数据存在一个数组中,我们会使用数组中的值hash % length取模操作,为每个值寻找存在数组中的位置,但是这种取模的操作性能不是很好,比起位运算差远了,后来发现当数组的容是2的n次方的时候hash & (length - 1) == hash % length,所以就使用hash & (length - 1) 来替代取模运算,这样操作效率高,而且数据均匀分布,hash碰撞少。

使用hash & (length - 1) 作为寻址算法也是jdk1.8的优化。

寻址算法的优化:使用与运算替代取模,提升性能。

那为什么要用数组值的hash值的高16与它的低16做异或呢?

        首先我们的寻址算法优化了,是使用hash & (length - 1) ,假设我们不适用新的优化后的hash算法,我们就直接使用数组中的值的hashcode,不使用高16与低16做异或,因为n-1的值通常是很小的,n-1通常高16为都是0,那么这个hash的高16为和n-1做与运算,hash的高16位就不起作用了,就相当于与之与两个都是低16位的值做与预算,而我们的目的就是为了hash更加散列,很少甚至不起hash冲突。所以如果使用hash值的高16与低16做异或,让他的低16为同时保持了高低16为的特征,尽量避免了hash冲突。

HashMap的容量为什么建议是2的幂次方?

关键就在于把当前数据存放到哪一个桶中,这个算法就是取模运算。

假设:

length:HashMap的容量

hash:当前key的哈希值

取模运算为 hash % length

        但是,在计算机中,直接取模运算的效率不如位运算(&),什么是位运算?就是对于二进制数据的按位运算,1和1才得1,其他都得0,比如:1011 & 1100 = 1000

        sun公司的大牛们发现,当容量为2的n次方时,hash & (length - 1) == hash % length ,于是就在源码中做了优化,通过 hash & (length - 1) 来替代取模运算,而前提就是容量必须为2的n次方。这样做的好处在于:

1. 提高操作运算效率(位运算效率 > 取模运算效率)

2. 减少碰撞,数据均匀分布,提高HashMap查询效率

为什么可以减少碰撞?举个例子,现在两个hash分别是2和3,:

比如 length 为 9 的情况:3&(9-1)=0 2&(9-1)=0 ,都在0上,碰撞了;

比如 length 为 8 的情况:3&(8-1)=3 2&(8-1)=2 ,不同位置上,不碰撞;

为什么不采用AVL树或B树,B+树?

红黑树和AVL树都是最常用的平衡二叉搜索树。

但是,两者之间有些许不同:

        AVL树更加严格平衡,因此可以提供更快的査找效果。因此,对于查找密集型任务使用AVL树没毛病。 但是对于插入密集型任务,红黑树要好一些。

通常,AVL树的旋转比红黑树的旋转更难实现和调试。

红黑树更通用,再添加删除来说表现较好,AVL虽能提升一些速度但是代价太大了。

而不用B/B+树的原因:

        B和B+树主要用于数据存储在磁盘上的场景,比如数据库索引就是用B+树实现的。这两种数据结构的特点就是树比较矮胖,每个结点存放一个磁盘大小的数据,这样一次可以把一个磁盘的数据读入内存,减少磁盘转动的耗时,提高效率。而红黑树多用于内存中排序,也就是内部排序。

为什么树化阈值是8?为什么树退化为链表的阈值是6?

        根据泊松分布。当我们计算的哈希冲突到了8次,概率就非常小了,可以看到当链表长度为8时候的概率为千万分之6,概率极低。所以取该值作为树化阈值。

相关文章:

HashMap源码阅读解惑

HashMap的hash函数(1.8) 首先1.7的是四次扰动,1.8做了优化。 简单的说就是对key做hashCode操作,然后将得到的32为散列值向右位移16位,再与hashCode做异或计算。实质上是把一个数的低16位与他的高16位做异或运算。 st…...

如何解决前端传递数据给后端时精度丢失问题

解决精度丢失 有时候我们在进行修改操作时,发现修改既不报错也不生效。我们进行排查后发现服务器端将数据返回给前端时没有出错,但是前端js将数据进行处理时却出错了,因为id是Long类型的,而js在处理后端返回给前端的Long类型数据…...

使用Maven创建父子工程

📚目录 创建父工程创建子模块创建子模块示例创建认证模块(auth) 结束 创建父工程 选择空项目: 设置:项目名称,组件名称,版本号等 创建完成后的工程 因为我们需要设置这个工程为父工程所以不需要src下的所有文件 在pom…...

Vue+elementUI 导出word打印

import JSZipUtils from "jszip-utils"; import JSZip from "pizzip"; import Docxtemplater from "docxtemplater"; npm安装以上依赖 首先维护个word模板 导出方法 //导出wordskipOutWord(row) {var printData rowconst data JSON.parse(JS…...

数学建模-点评笔记 9月3日

1.摘要:关键方法和结论(精炼的语言)要说明,方法的合理性和意义也可以说明。 评委先通过摘要筛选(第一轮) 2.时间序列找异常值除了3西格玛还有针对时间序列更合适寻找的方法 3.模型的优缺点要写的详细一点…...

使用Spring来管理对象关系映射(ORM)

简介 对象关系映射(Object-Relational Mapping,简称ORM)是一种技术,用于在面向对象程序和关系型数据库之间进行数据的映射。Spring框架提供了强大的支持来简化和优化ORM开发过程。本文将介绍如何使用Spring来管理对象关系映射。 …...

【消息中间件】详解三大MQ:RabbitMQ、RocketMQ、Kafka

作者简介 前言 博主之前写过一个完整的MQ系列,包含RabbitMQ、RocketMQ、Kafka,从安装使用到底层机制、原理。专栏地址: https://blog.csdn.net/joker_zjn/category_12142400.html?spm1001.2014.3001.5482 本文是该系列的清单综述&#xf…...

算法:删除有序数组中的重复项---双指针[3]

1、题目: 对给定的有序数组 nums 删除重复元素,在删除重复元素之后,每个元素只出现一次,并返回新的长度,上述操作必须通过原地修改数组的方法,使用 O(1) 的空间复杂度完成。 2、分析特点: 题目…...

AR产业变革中的“关键先生”和“关键力量”

今年6月的WWDC大会上,苹果发布了头显产品Vision Pro,苹果CEO库克形容它: 开启了空间计算时代。 AR产业曾红极一时,但因为一些技术硬伤又减弱了声量,整个产业在起伏中前行。必须承认,这次苹果发布Vision P…...

通过 Blob 对二进制流文件下载实现文件保存下载

原理&#xff1a;前端将二进制文件做转换实现下载: 请求后端接口->接收后端返回的二进制流(通过二进制流&#xff08;Blob&#xff09;下载,把后端返回的二进制文件放在 Blob 里面)->再通过file-saver插件保存 页面上使用&#xff1a; <span click"downloadFil…...

微信小程序使用lime-echart踩坑记录

一、使用echarts包 微信小程序项目使用的是uni-app&#xff0c;插件是lime-echart&#xff0c;版本一开始安装的是lime-echart-0.7.9&#xff1b;在项目分包之后&#xff0c;为了避免主包过大&#xff0c;就将这个插件也一并搬到了分包中&#xff0c;在微信开发者工具中表现出…...

Unity 编辑器资源导入处理函数 OnPostprocessTexture :深入解析与实用案例

Unity 编辑器资源导入处理函数 OnPostprocessTexture 用法 点击封面跳转下载页面 简介 在Unity中&#xff0c;我们可以使用编辑器资源导入处理函数&#xff08;OnPostprocessTexture&#xff09;来自定义处理纹理资源的导入过程。这个函数是继承自AssetPostprocessor类的&…...

stable diffusion实践操作-宽高设置以及高清修复

系列文章目录 stable diffusion实践操作 文章目录 系列文章目录前言一、SD宽高怎么设置&#xff1f;1.1 宽高历史 二、高清修复1. 文生图中的高清修复1.按钮Hires.fix2.不同放大算法对比1.第一类2.第二类3.第三类4.第四类5.第五类6.第六类7.第七类8.第八类9.第九类10.第十类11…...

利用微调的deberta-v3-large来预测情感分类

前言&#xff1a; 昨天我们讲述了怎么利用emotion数据集进行deberta-v3-large大模型的微调&#xff0c;那今天我们就来输入一些数据来测试一下&#xff0c;看看模型的准确率&#xff0c;为了方便起见&#xff0c;我直接用测试集的前十条数据 代码&#xff1a; from transfor…...

opencv旋转图像

0 、使用旋转矩阵旋转 import cv2img cv2.imread(img.jpg, 1) (h, w) img.shape[:2] # 获取图像的宽和高# 定义旋转中心坐标 center (w / 2, h / 2)# 定义旋转角度 angle 90# 定义缩放比例 scale 1# 获得旋转矩阵 M cv2.getRotationMatrix2D(center, angle, scale)# 进行…...

容器资料: Docker和Singularity

容器资料 Docker和Singularity Docker比较适合测试: 环境适配,每种环境对应一个容器。Docker需要host宿主机上运行Docker服务(root权限),隔离性很高&#xff0c;但会牺牲性能&#xff0c;对GPU环境支持不好(需要安装NVIDIAN公司的插件才能把GPU暴露给container) Sigularity可…...

如何确认linux的包管理器是yum还是apt,确认之后安装其他程序的时候就需要注意安装命令

打开终端 输入apt&#xff0c;下图中提示未找到命令&#xff0c;则基本上包管理工具就是用yum的 输入yum&#xff0c;我们看到有打印信息&#xff0c;则说明包管理工具是yum的&#xff0c;离线安装命令使用rpm...

数据分享|R语言分析上海空气质量指数数据:kmean聚类、层次聚类、时间序列分析:arima模型、指数平滑法...

全文链接&#xff1a;http://tecdat.cn/?p30131 最近我们被客户要求撰写关于上海空气质量指数的研究报告。本文向大家介绍R语言对上海PM2.5等空气质量数据&#xff08;查看文末了解数据免费获取方式&#xff09;间的相关分析和预测分析&#xff0c;主要内容包括其使用实例&…...

MySQL 8.0.34安装教程

一、下载MySQL 1.官网下载 MySQL官网下载地址&#xff1a; MySQL :: MySQL Downloads &#xff0c;选择下载社区版&#xff08;平时项目开发足够了&#xff09; 2.点击下载MySQL Installer for Windows 3.选择版本8.0.34&#xff0c;并根据自己需求&#xff0c;选择下载全社区安…...

用通俗易懂的方式讲解大模型分布式训练并行技术:概述

近年来&#xff0c;随着Transformer、MOE架构的提出&#xff0c;使得深度学习模型轻松突破上万亿规模参数&#xff0c;传统的单机单卡模式已经无法满足超大模型进行训练的要求。因此&#xff0c;我们需要基于单机多卡、甚至是多机多卡进行分布式大模型的训练。 而利用AI集群&a…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...