【Java基础】HashMap 原理
文章目录
- 1、HashMap 设置值的原理
- 2、HashMap 获取值原理
- 3、HashMap Hash优化
- 4、HashMap 寻址优化
- 5、HashMap 是如何解决Hash冲突的?
- 5.1 get数据的时候,如果定位到指定位置的元素是一个链表,怎么办呢?
- 5.2 红黑树
- 6、数组扩容
- 6.1 数组长度为16,计算index
- 6.2 数组长度为32, 计算index
- 6.3 扩容总结:
1、HashMap 设置值的原理
- 根据key计算HashCode,
- 再使用HashCode对 数组长度取模,结果一定是存放到数组中 的某一个位置。
- 得到指定位置索引之后,就往指定位置设置数据即可。
2、HashMap 获取值原理
- 根据key计算hashCode,
- 再使用hashCode对 数据长度取模,得到一个数组索引,
- 然后再根据索引从数组中获取指定数据即可。
3、HashMap Hash优化
// JDK 1.8以后的HashMap里面的一段源码static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
答案:hash数组一般不会太大,使用 key 的hashCode 和 key的hashCode 右移16位 进行异或运算的目的就是让 高低16位都参与运算,减少hash冲突
4、HashMap 寻址优化
hash & (n - 1)
当n为2的n次方的时候, hash & (n - 1) = hash % n
答案:hash & (n - 1) -> 效果是跟hash对n取模,效果是一样的,但是与运算的性能要比hash对n取模要高很多,数学问题,数组的长度会一直是2的n次方,只要他保持数组长度是2的n次方
5、HashMap 是如何解决Hash冲突的?
使用链表法解决。
在数据的指定位置,挂一个链表,这个链表里放多个元素,让多个 key-value 放在数据的同一个位置
5.1 get数据的时候,如果定位到指定位置的元素是一个链表,怎么办呢?
get 的时候,如果定位到数组发现这个位置挂了一个链表哦,此时就会遍历 链表,从链表里面选择到自己需要的那个 kye-value 就可以了。
5.2 红黑树
为了解决hash冲突的问题,就会在 数据的指定为值挂一个链表,如果链表的长度达到了一定的长度之后,就会将链表转换成红黑树,通过遍历一颗红黑树找到一个元素,此时时间复杂度是 O(logn), 性能比链表要高一些。
如果链表过长,遍历的性能不高,因此当链表长度超过一定限制的时候,就会将链表转换成红黑树,提升搜索性能。
6、数组扩容
6.1 数组长度为16,计算index
n - 1 0000 0000 0000 0000 0000 0000 0000 1111
hash1 1111 1111 1111 1111 0000 1111 0000 0101
& 0000 0000 0000 0000 0000 0000 0000 0101 = 5(index = 5的位置)n - 1 0000 0000 0000 0000 0000 0000 0000 1111
hash2 1111 1111 1111 1111 0000 1111 0001 0101
& 0000 0000 0000 0000 0000 0000 0000 0101 = 5(index = 5的位置)
6.2 数组长度为32, 计算index
n-1 0000 0000 0000 0000 0000 0000 0001 1111
hash1 1111 1111 1111 1111 0000 1111 0000 0101
&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5(index = 5的位置)n-1 0000 0000 0000 0000 0000 0000 0001 1111
hash2 1111 1111 1111 1111 0000 1111 0001 0101
&结果 0000 0000 0000 0000 0000 0000 0001 0101 = 21(index = 21的位置)
6.3 扩容总结:
数据扩容 -> 2倍扩容 -> 重新对map中的每一个元素进行寻址->通过判断二进制结果是否多出来了一个bit为,判断index的位置是否变化;
如果数组的长度扩容之后 = 32,重新对每个hash值进行寻址,也就是用每个hash值跟新数组的length - 1进行与操作
- 判断二级制结果是否多出来一个bit的1
- 如果没有多,那么还是原来的index
- 如果多了出来,那么新的index = oldIndex + oldCap
- 通过这个方法避免了rehash的时候,用每个hash对数据的长度进行取模,取模的性能不高,位运算的性能比较高。
相关文章:
【Java基础】HashMap 原理
文章目录 1、HashMap 设置值的原理2、HashMap 获取值原理3、HashMap Hash优化4、HashMap 寻址优化5、HashMap 是如何解决Hash冲突的?5.1 get数据的时候,如果定位到指定位置的元素是一个链表,怎么办呢?5.2 红黑树 6、数组扩容6.1 数…...
vue3的大致使用
<template><div class"login_wrap"><div class"form_wrap"> <!-- 账号输入--> <el-form ref"formRef" :model"user" class"demo-dynamic" > <!--prop要跟属性名称对应-->…...
什么是计算机网络?计算机网络基础知识
1.网络的组成部分:由主机,路由器,交换机等组成 2.网络结构:网络的网络 3.信息交换方式:电路交换和分组交换 4.网络分层:分清职责,物理层,链路层,网络层,运…...
【机器学习 | 假设检验系列】假设检验系列—卡方检验(详细案例,数学公式原理推导),最常被忽视得假设检验确定不来看看?
🤵♂️ 个人主页: AI_magician 📡主页地址: 作者简介:CSDN内容合伙人,全栈领域优质创作者。 👨💻景愿:旨在于能和更多的热爱计算机的伙伴一起成长!!&…...
RealBasicVSR高清处理视频
autodl做了镜像:高清RealBasicVSR 首先在剪映将视频剪好导出,最多是720像素的,不然后面超分的时候会爆显存。剪映视频也最好是双数帧数结尾的,不然超分的时候单数图片会报错->RuntimeError: non-empty 3D or 4D input tensor …...
晚期食管癌肿瘤治疗线程分类
文章目录 1、肿瘤治疗的线数1.1 基础概念1.2 线程定义1.3 如何计算治疗线数 2 食管癌治疗指南2.1 食管癌诊疗指南2.1 CSCO 本文前半部分主要来源于参考文件1,其余部分来源于官方指南。无原创内容,全部为摘要。 1、肿瘤治疗的线数 1.1 基础概念 抗肿瘤药…...
高效营销系统集成:百度营销的API无代码解决方案,提升电商与广告效率
百度营销API连接:构建无代码开发的高效集成体系 在数字营销的高速发展时代,企业追求的是快速响应市场的能力以及提高用户运营的效率。百度营销API连接正是为此而生,它通过无代码开发的方式,实现了电商平台、营销系统和CRM的一站式…...
网络基础(十一):VRRP原理与配置
目录 前言: 1、VRRP的基本概述 2、VRRP的基本原理 2.1VRRP的基本结构 2.2设备类型 2.3状态机 2.4VRRP路由器的抢占功能 2.5VRRP路由器的优先级 2.6VRRP工作原理 2.7主备路由器的工作内容 3、VRRP的基本配置 3.1配置主路由器和备用路由器 3.2配置PC1与P…...
设计模式——状态模式
引言 状态模式是一种行为设计模式, 让你能在一个对象的内部状态变化时改变其行为, 使其看上去就像改变了自身所属的类一样。 问题 状态模式与有限状态机 的概念紧密相关。 其主要思想是程序在任意时刻仅可处于几种有限的状态中。 在任何一个特定状态中…...
2020-XNUCA babyv8
做的第一道存在指针压缩机制的V8题,通过小越界写修改length构造大越界读写,然后利用arraybuffer的backing store构造任意地址写,利用wasm rwx段地址的特点以及堆空间的分布,搜索到rwx段的具体地址,然后利用任意地址写将…...
货物数据处理pandas版
1求和 from openpyxl import load_workbook import pandas as pddef print_hi(name):# Use a breakpoint in the code line below to debug your script.print(fHi, {name}) # Press CtrlF8 to toggle the breakpoint.# Press the green button in the gutter to run the scr…...
MC-30A (32.768 kHz用于汽车应用的晶体单元)
MC-30A 32.768 kHz用于汽车应用的晶体,车规晶振中的热销型号之一。该款石英晶体谐振器,可以在-40 to 85 C的温度内稳定工作,能满足起动振动的要求。同时满足AEC-Q200无源元件质量标准认证,满足汽车仪表系统的所有要求。 频率范围…...
TrustZone之其他设备及可信基础系统架构
一、其他设备 最后,我们将查看系统中的其他设备,如下图所示: 我们的示例TrustZone启用的系统包括一些尚未涵盖的设备,但我们需要这些设备来构建一个实际的系统。 • 一次性可编程存储器(OTP)或保险丝 这些是一旦写入就无法更改的存储器。与每个芯片上都包含相同…...
自由编程学习资源:free-programming-books
最近,我发现了一个在GitHub上备受欢迎的项目,它为程序员和编程爱好者提供了丰富、免费且高质量的学习资料,这就是"free-programming-books"。目前,这个项目在GitHub上已经有305k的star,显示出它在开发者社区…...
饥荒Mod 开发(十三):木牌传送
饥荒Mod 开发(十二):一键制作 饥荒Mod 开发(十四):制作屏幕弹窗 一键传送源码 饥荒的地图很大,跑地图太耗费时间和饥饿值,如果大部分时间都在跑图真的是很无聊,所以需要有一个能够传送的功能,不仅可以快速…...
Qt/C++音视频开发60-坐标拾取/按下鼠标获取矩形区域/转换到视频源真实坐标
一、前言 通过在通道画面上拾取鼠标按下的坐标,然后鼠标移动,直到松开,根据松开的坐标和按下的坐标,绘制一个矩形区域,作为热点或者需要电子放大的区域,拿到这个坐标区域,用途非常多࿰…...
Java实现订单超时未支付自动取消的8种方法总结
Java实现订单超时未支付自动取消的8种方法总结 定时轮询 数据库定时轮询方式,实现思路比较简单。启动一个定时任务,每隔一定时间扫描订单表,查询到超时订单就取消。优点:实现简单。缺点:轮询时间间隔不好确定&#x…...
android动态权限申请并展示权限使用说明
# ExplainPermissions 动态权限申请并展示权限使用说明 随着工信部对APP的一系列整治,现在用户对于APP在使用时动态申请的权限是比较敏感的,为了更好的用户体验,我们可以在权限动态申请的时候一并向用户展示所需要申请权限的使用说明。这样用…...
论文阅读《DPS-Net: Deep Polarimetric Stereo Depth Estimation》
论文地址:https://openaccess.thecvf.com/content/ICCV2023/html/Tian_DPS-Net_Deep_Polarimetric_Stereo_Depth_Estimation_ICCV_2023_paper.html 概述 立体匹配模型难以处理无纹理场景的匹配,现有的方法通常假设物体表面是光滑的,或者光照是…...
docker文档转译1
写在最前面 本文主要是转译docker官方文档。主题是Docker overview,这里是链接 Docker概述 Docker是一个用于开发、发布和运行应用程序的开放平台。Docker使你能够将应用程序与基础设施分离,从而可以快速交付软件。你可以使用相同的方法像管理应用程序…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用
在工业制造领域,无损检测(NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统,以非接触式光学麦克风技术为核心,打破传统检测瓶颈,为半导体、航空航天、汽车制造等行业提供了高灵敏…...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...
