HashMap 中的哈希值计算问题
2024-10-20 03:17:09
date: 2020-08-21 16:48:00
updated: 2020-08-21 16:52:00
HashMap 中的哈希值计算问题
1. hash 计算
JDK1.8
HashMap源码
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
右移16位相当于将高16位移入到低16位,再与原hashcode做异或计算(位相同为0,不同为1)可以将高低位二进制特征混合起来 => 高16位没有发生变化,但是低16位改变了
拿到的hash值会参与hashmap中数组槽位的计算,计算公式:(n - 1) & hash,假设数组初始槽位16个,那么槽位计算如下:
高区的16位很有可能会被数组槽位数的二进制码锁屏蔽,如果我们不做刚才移位异或运算,那么在计算槽位时将丢失高区特征
虽然丢失了高区特征,不同hashcode也可以计算出不同的槽位来,但是如果两个hashcode很接近时,高区的特征差异可能会导致一次哈希碰撞。
2. 使用异或运算的原因
异或运算能更好的保留各部分的特征,如果采用 & 运算计算出来的值会向0靠拢,采用 | 运算计算出来的值会向1靠拢
3. 为什么槽位数必须使用2^n / 为什么要 &length-1
为了让哈希后的结果更加均匀,减少hash碰撞
4. 扩容后Hash值计算
length * 2,即新增的bit位是1,在 (n - 1) & hash 时,只需要判断新增加的这一个bit位,如果是0的话,说明索引不变,如果变成1了,索引变成 原索引+扩容前的容量大小
最新文章
- iOS可视化动态绘制连通图
- 【javaweb学习】XML和约束模式
- iOS播放铃声及震动,适用于扫描、新消息等
- AX3空Invoice明细问题
- ansible 的组件inventory
- codeforces 258div2 B	 Sort the Array
- python解惑之 __file__ 与argv[0]
- PHP得出附件扩展名
- xml程序 个人练习1
- Scala + Play + Sbt + Protractor
- Docker镜像压缩
- Loadrunner分布式测试
- Mac实用操作技巧(三)
- 新一代的昆明网络seo优化技巧
- Dynamics CRM 请求服务时报access is denied错误
- TCP浅谈为什么3次握手
- Tensorflow 大规模数据集训练方法
- dialog 关闭 清除
- Android Studio在华为真机上运行无法输出Debug日志解决
- 利用sshtunnel实现跳板机的效果[嵌套ssh实现]
热门文章
- C#开发PACS医学影像三维重建(一):使用VTK重建3D影像
- RESTful API 编写规范
- WPF DataGrid 复合表头 (实现表头合并,自定义表头)
- (转载)CPU基础知识
- JS实现动态显示时间(最简单方法)
- 008 01 Android 零基础入门 01 Java基础语法 02 Java常量与变量 02 Java 中的关键字
- CString类常用方法----Left(),Mid(),Right()
- SPI通信基础学习
- CPU 执行程序的秘密,藏在了这 15 张图里
- Code Forces 1030E