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

HashMap 源码中的巧妙小技巧

根据容量计算大于容量的最小的哈希表的大小(table的length),这里的length需要满足length=2^n,也就是我们需要根据容量算出最小的n的值

static final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
int n = cap - 1;这里是为了确定在二进制表示的情况下,最高位的1的位置,这里分两种情况来讲
1.cap!=2^n,cap不是2的n次方
这种情况其实减1之后,最高位的1的位置不变例如随便找两个数
69
00000000 00000000 00000000 01000101
69-1
00000000 00000000 00000000 01000100
16196
00000000 00000000 00100000 01000100
16196-1
00000000 00000000 00100000 01000011
4210496
00000000 00100000 00100000 01000000
4210496-1
00000000 00100000 00100000 00111111这几个数字减 1 以后,最高位的1的位置不变2.cap=2^n,cap是2的n次方
这种情况其实减1之后,最高位的1的位置会向右移动一位16
00000000 00000000 00000000 00010000
16-1
00000000 00000000 00000000 00001111
4096
00000000 00000000 00010000 00000000
4096-1
00000000 00000000 00001111 11111111这几个数字减1之后,最高位的1的位置会向右移动一位n |= n >>> 1; 这一步是让从最高位的1开始,往右的前2位变为1
例如:
n = 100000
n >>> 1 就是 10000
n |= n >>> 1 的意思就是 n = n | n >>> 1 = 100000 | 10000 = 110000n |= n >>> 2; 这一步是让从最高位的1开始,往右的前4位变为1
n = 110000
n >>> 2 就是 1100
n |= n >>> 2 的意思就是 n = n | n >>> 2 = 110000 | 1100 = 111100n |= n >>> 4; 这一步是让从最高位的1开始,往右的前8位变为1
n = 111100
n >>> 4 就是 11
n |= n >>> 4 的意思就是 n = n | n >>> 4 = 111100 | 11 = 111111这里再举一个比较大的例子n=10000000000000000000000000000000
n >>> 1 就是 1000000000000000000000000000000
n |= n >>> 1 就是 n = n | n >>> 1 = 10000000000000000000000000000000| 1000000000000000000000000000000= 11000000000000000000000000000000n = 11000000000000000000000000000000
n >>> 2 就是 110000000000000000000000000000
n |= n >>> 2 就是 n = n | n >>> 2 = 11000000000000000000000000000000 | 110000000000000000000000000000 = 11110000000000000000000000000000n = 11110000000000000000000000000000
n >>> 4 就是 1111000000000000000000000000
n |= n >>> 4 就是 n = n | n >>> 4 = 11110000000000000000000000000000 | 1111000000000000000000000000 = 11111111000000000000000000000000n = 11111111000000000000000000000000
n >>> 8 就是 111111110000000000000000
n |= n >>> 8 就是 n = n | n >>> 8 = 11111111000000000000000000000000 | 111111110000000000000000 = 11111111111111110000000000000000n = 11111111111111110000000000000000
n >>> 16 就是 1111111111111111
n |= n >>> 16 就是 n = n | n >>> 16 = 11111111111111110000000000000000 | 1111111111111111 = 11111111111111111111111111111111return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
这里表示如果正常的话返回的值应该是 n + 1
根据我们的经验,如果一个数的二进制表示所有的1都在最右边,那么这个数加 1 以后就是 2^n

计算一个key值的hash值,这里的key的类型是 Object。计算出来的hash值用来参与计算当前键值对在hash表中的位置 

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
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))))

以上是put方法的部分代码,我们可以摘取出其中的关键代码

int n , i;
(n = tab.length) == 0 这里执行完,那么 n = tab.length(p = tab[i = (n - 1) & hash]) == null 这里执行完,那么 i = (n - 1) & hash
hash的值就是通过上面的hash()方法计算出的值tab[i] = newNode(hash, key, value, null);
这里可以看出 i 是用来寻找新节点的位置的,看来节点在table中的位置为:
(tab.length - 1) & hash
根据 tableSizeFor() 的实现可以看出,tab.length为2^k , tab.length - 1的值用二进制表示 
低位都为1二进制,高位都是0
那么 (tab.length - 1) & hash 就相当于只取hash的二进制表示的最低的那几位。
如果两个不同的hash值,如果高位不同,低位相同那么算出来的值是相同的,就会增加hash冲突的概率,导致性能受影响。接下来讨论hash()方法的这段代码的巧妙之处
(h = key.hashCode()) ^ (h >>> 16)
h = key.hashCode() 是key的hashCode值
h >>> 16 表示 h 向右移动16位,原来高位的16位移到低位了(h = key.hashCode()) ^ (h >>> 16) 就相当于将 h 的高16位和低16位进行异或运算,
这样h的二进制表示如果高位不同,低位相同,那么最终结果的低位是不同的,
前面put方法分析了寻找键值对在table中的位置时只取hash值的低位来决定键值对的位置,
这样就可以减少hash碰撞的概率

相关文章:

HashMap 源码中的巧妙小技巧

根据容量计算大于容量的最小的哈希表的大小(table的length)&#xff0c;这里的length需要满足length2^n&#xff0c;也就是我们需要根据容量算出最小的n的值 static final int tableSizeFor(int cap) {int n cap - 1;n | n >>> 1;n | n >>> 2;n | n >&g…...

极具吸引力的小程序 UI 风格

极具吸引力的小程序 UI 风格...

数据库 | 试卷五试卷六试卷七

1. 主码不相同&#xff01;相同的话就不能唯一标识非主属性了 2.从关系规范化理论的角度讲&#xff0c;一个只满足 1NF 的关系可能存在的四方面问题 是&#xff1a; 数据冗余度大&#xff0c;插入异常&#xff0c;修改异常&#xff0c;删除异常 3.数据模型的三大要素是什么&…...

网页五子棋对战项目测试(selenium+Junit5)

目录 网页五子棋对战项目介绍 网页五子棋对战测试的思维导图​ 网页五子棋对战的UI自动化测试 测试一&#xff1a;测试注册界面 测试二&#xff1a;测试登陆界面 测试三&#xff1a;测试游戏大厅界面 测试四&#xff1a;测试游戏房间界面以及观战房间界面 测试五&#…...

stable diffusion 局部重绘 reference-only api 接口调试

webUI api payload 插件生成的接口参数不准确&#xff0c;reference-only 的image不是对象&#xff0c;就是不同字符串字段&#xff0c;直接传&#xff0c;不是套image。 综上&#xff0c;那个插件参数不确定&#xff0c;应直接看插件的源码&#xff0c;看它接受什么参数 错误…...

浪潮信息内存故障预警技术再升级 服务器稳定性再获提升

浪潮信息近日对其内存故障智能预警修复技术进行了全面升级&#xff0c;再次取得技术突破。此次升级后&#xff0c;公司服务器的宕机率实现了80%锐降&#xff0c;再次彰显了浪潮信息在服务器技术领域的卓越能力。 浪潮信息全新升级服务器内存故障智能预警修复技术MUPR (Memory …...

JWT整合Gateway实现鉴权(RSA与公私密钥工具类)

一.业务流程 1.使用RSA生成公钥和私钥。私钥保存在授权中心&#xff0c;公钥保存在网关(gateway)和各个信任微服务中。 2.用户请求登录。 3.授权中心进行校验&#xff0c;通过后使用私钥对JWT进行签名加密。并将JWT返回给用户 4.用户携带JWT访问 5.gateway直接通过公钥解密JWT进…...

vue实现全屏screenfull-封装组件

1. 安装依赖 npm install --save screenfull 2. 引用 import screenfull from "screenfull" 3.封装fullScreen/index: <template><div><el-tooltip v-if"!content" effect"dark" :content"fullscreenTips" placement&…...

【LinkedList与链表】

目录 1&#xff0c;ArrayList的缺陷 2&#xff0c;链表 2.1 链表的概念及结构 2.2 链表的实现 2.2.1 无头单向非循环链表实现 3&#xff0c;LinkedList的模拟实现 3.1 无头双向链表实现 4&#xff0c;LinkedList的使用 4.1 什么是LinkedList 4.2 LinkedList的使用 5…...

为数据安全护航,袋鼠云在数据分类分级上的探索实践

在大数据时代&#xff0c;数据具有多源异构的特性&#xff0c;且价值各异&#xff0c;企业需依据数据的重要性、价值指数等予以区分&#xff0c;以利采取不同的数据保护举措&#xff0c;避免数据泄露。故而&#xff0c;数据分类分级管理属于数据安全保护中极为重要的环节之一。…...

Spring 循环依赖详解

Spring 循环依赖详解 1. 引言 在Spring框架中&#xff0c;依赖注入&#xff08;Dependency Injection, DI&#xff09;是其核心功能之一&#xff0c;它通过配置来管理对象的创建和它们之间的依赖关系。然而&#xff0c;在复杂的应用程序中&#xff0c;开发人员有时会遇到循环…...

项目经理真的不能太“拧巴”

前期的项目经理经常是“拧巴”的&#xff0c;就是心里纠结、思路混乱、行动迟缓。对于每天需要面对各种挑战、协调各方资源、确保项目顺利进行的项目经理来说&#xff0c;这种“拧巴”不仅会让自己陷入内耗中&#xff0c;还会让项目出大问题。 项目计划总是改来改去&#xff0…...

企业如何选择合适的CRM工具?除Salesforce之外的10大主流选择

对比salesforce&#xff0c;其他10款优秀CRM&#xff1a;纷享销客CRM、Zoho CRM、腾讯企点、销售易、企业微信 (WeCom)、Odoo CR、OroCRM、金蝶、用友CRM、EspoCRM 虽然Salesforce以其全面的功能和强大的市场占有率在海外收获了许多客户&#xff0c;但Salesforce在国内市场的接…...

每年1-1.2万人毕业,男女比例约3:1,测绘工程的就业率如何

测绘工程&#xff0c;一个让人闻风丧胆的理科专业&#xff0c;虎扑评分4.2&#xff1a; 干过测绘的&#xff0c;苦不苦只有大家心里知道&#xff0c;带大家来感受一下&#xff0c;兄弟们的精神状态都十分美妙&#xff1a; 测绘专业到底是什么情况&#xff1f; PS.测绘分为本科…...

JimuReport 积木报表 v1.7.6 版本发布,免费的低代码报表

项目介绍 一款免费的数据可视化报表工具&#xff0c;含报表和大屏设计&#xff0c;像搭建积木一样在线设计报表&#xff01;功能涵盖&#xff0c;数据报表、打印设计、图表报表、大屏设计等&#xff01; Web 版报表设计器&#xff0c;类似于excel操作风格&#xff0c;通过拖拽完…...

“灵活就业者“超两亿人 游戏开发者如何破局?

随着“灵活就业”者数量突破两亿&#xff0c;我相信“寒气”已经传递到每一位普通人&#xff01;对于游戏行业的“灵活就业”者&#xff0c;应当如何破局&#xff1f; 首先应该恭喜大家&#xff0c;选择了一个相对“稳健”的行业&#xff0c;无论大环境如何&#xff0c;游戏/软…...

MySQL事务与存储引擎

一、事务的概念 是一种机制、一个操作序列&#xff0c;包含了一组数据库操作命令&#xff0c;并且把所有的命令作为一个整体一起向系统提交或撤销操作请求&#xff0c;即这一组数据库命令要么都执行&#xff0c;要么都不执行是一个不可分割的工作逻辑单元&#xff0c;在数据库…...

总是给数据库表字段设置默认值的好处

1、NOT NULL DEFAULT 的好处 在设计数据库表结构时&#xff0c;将字段设置为不能为空并设置默认值有以下几种好处&#xff1a; 1.1、数据完整性 通过设置字段不能为空&#xff0c;可以确保每条记录都包含必要的数据&#xff0c;从而保证了数据的完整性。例如&#xff0c;在用…...

11.2 Go 常用包介绍

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…...

Sqlite3数据库基本使用

一、基本概念 数据&#xff1a;能够输入计算机并能被计算机程序识别和处理的信息集合 数据库&#xff1a;长期存储在计算机内、有组织的、可共享的大量数据的集合 DBMS&#xff1a;位于用户与操作系统之间的一层数据管理软件&#xff0c;用于操纵和管理数据库 二、安装 在线…...

飞行器设计避坑指南:盘点那些影响气动效率的‘隐形杀手’(从摩擦阻力到干扰阻力)

飞行器设计避坑指南&#xff1a;盘点那些影响气动效率的‘隐形杀手’ 记得第一次参加大学生飞行器设计竞赛时&#xff0c;我们的团队花了整整三个月打造了一架翼展两米的固定翼无人机。试飞当天&#xff0c;看着它摇摇晃晃地起飞&#xff0c;却在爬升阶段突然失速坠毁&#xff…...

HSTracker:精准追踪炉石传说对战数据的macOS智能辅助工具

HSTracker&#xff1a;精准追踪炉石传说对战数据的macOS智能辅助工具 【免费下载链接】HSTracker A deck tracker and deck manager for Hearthstone on macOS 项目地址: https://gitcode.com/gh_mirrors/hs/HSTracker HSTracker是一款专为macOS平台设计的开源炉石传说辅…...

ComfyUI实战:如何加载基于Flux.1微调的LoRA模型并优化推理流程

最近在项目里用 ComfyUI 部署基于 Flux.1 微调的 LoRA 模型&#xff0c;踩了不少坑。从模型加载失败到推理时显存爆炸&#xff0c;问题层出不穷。经过一番折腾&#xff0c;总算梳理出一套比较稳定的流程&#xff0c;这里把实战经验记录下来&#xff0c;希望能帮到有同样需求的同…...

W-TRS-5.5D7红外测温:电炖锅智能测温的革新力量

在追求健康饮食与智能烹饪的时代&#xff0c;电炖锅的温控技术革新至关重要。领麦微W-TRS-5.5D7红外测温传感器的出现&#xff0c;为电炖锅带来非接触检测锅温与食物温度的新突破&#xff0c;结合智能菜谱功能&#xff0c;开启电炖锅智能烹饪新纪元。非接触检测锅温&#xff1a…...

智能高效的离线OCR解决方案:Umi-OCR从基础到进阶的全方位应用指南

智能高效的离线OCR解决方案&#xff1a;Umi-OCR从基础到进阶的全方位应用指南 【免费下载链接】Umi-OCR Umi-OCR: 这是一个免费、开源、可批量处理的离线OCR软件&#xff0c;适用于Windows系统&#xff0c;支持截图OCR、批量OCR、二维码识别等功能。 项目地址: https://gitco…...

ESP32 IDF环境下DHT11温湿度读取避坑指南:从时序图到数据拼接的完整解析

ESP32 IDF环境下DHT11温湿度读取避坑指南&#xff1a;从时序图到数据拼接的完整解析 在物联网设备开发中&#xff0c;温湿度传感器是最基础也最常用的环境感知元件之一。DHT11作为一款低成本、单总线数字输出的温湿度传感器&#xff0c;被广泛应用于各类嵌入式项目中。然而&…...

避坑指南:Unity物体闪烁效果Material内存泄漏问题排查(附Shader优化方案)

Unity物体闪烁效果的性能陷阱与工业级解决方案 在游戏开发中&#xff0c;物体闪烁效果是一种常见的视觉反馈手段&#xff0c;用于提示玩家可交互对象、危险区域或特殊状态。然而&#xff0c;许多开发者在使用传统实现方式时&#xff0c;往往会掉入Material内存泄漏的陷阱&#…...

别再踩坑PX4Flow了!实测优象LC-302光流模块,手把手教你搞定PX4无人机室内悬停

无人机室内悬停实战指南&#xff1a;优象LC-302光流模块深度评测与PX4调参技巧 当无人机从开阔的室外飞入复杂的室内环境&#xff0c;GPS信号的突然消失往往让飞手们手忙脚乱。这时&#xff0c;一套可靠的光流定位系统就成了"空中救生绳"。本文将带您深入评测市面上主…...

AI编程助手太烧钱?试试这个‘外挂’:心灵宝石MCP服务在Cursor中的安装与长期使用心得

深度解析Cursor IDE中的MCP服务&#xff1a;心灵宝石的高效部署与实战技巧 作为一名全栈开发者&#xff0c;我几乎每天都要与代码编辑器打交道。从早期的Sublime Text到VS Code&#xff0c;再到如今集成了AI能力的Cursor&#xff0c;工具链的进化让开发效率不断提升。但随之而来…...

嵌入式软件架构设计与实践指南

## 1. 嵌入式软件架构设计概述### 1.1 嵌入式系统发展现状 现代嵌入式系统硬件性能已实现质的飞跃&#xff0c;以Marvell PXA3xx系列处理器为例&#xff0c;其主频可达800MHz&#xff0c;集成USB、WIFI、2D图形加速和32位DDR内存控制器。软件层面&#xff0c;Symbian、Linux、W…...