文档章节

HashMap中确定数组位置为什么要用hash进行扰动

o
 osc_g8254g7s
发布于 2019/08/19 22:22
字数 500
阅读 6
收藏 0
jdk

精选30+云产品,助力企业轻松上云!>>>

HashMap数据存储的过程先根据key获得hash值,通过 (n - 1) & hash 判断当前元素存放的位置(这里的 n 指的是数组的长度),如果当前位置存在元素的话,就判断该元素与要存入的元素的 hash 值以及 key 是否相同,如果相同的话,直接覆盖,不相同就通过拉链法解决冲突。

其中,jdk1.8中扰动函数hash的源码:

static final int hash(Object key) {
    int h;
    // key.hashCode():返回散列值也就是hashcode
    // ^ :按位异或
    // >>>:无符号右移,忽略符号位,空位都以0补齐
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

其中看到在获得hash值时将key的hashCode异或上其无符号右移16位,Hashmap这么做原因:

防止一些实现比较差的 hashCode() 方法,使用扰动函数之后可以减少碰撞,进一步降低hash冲突的几率

打个比方, 当我们的数组长度n为16的时候,哈希码(字符串“abcabcabcabcabc”的key对应的哈希码)对(16-1)与操作,对于多个key生成的hashCode,只要哈希码的后4位为0,不论不论高位怎么变化,最终的结果均为0。 如下图所示:

1954974080(HashCode) 111 0100 1000 0110 1000 1001 1000 0000
2^4-1=15(length-1) 000 0000 0000 0000 0000 0000 0000 1111
&运算 000 0000 0000 0000 0000 0000 0000 0000

而加上高16位异或低16位的“扰动函数”后,结果如下:

原HashCode 1954974080 111 0100 1000 0110 1000 1001 1000 0000
(>>>16)无符号右移16位 29830 000 0000 0000 0000 0111 0100 1000 0110
^(异或)运算 1955003654 111 0100 1000 0110 1111 1101 0000 0110
2^4-1=15(length-1) 15 000 0000 0000 0000 0000 0000 0000 1111
&(与)运算 6 000 0000 0000 0000 0000 0000 0000 0110

可以看到: 扰动函数优化前:1954974080 % 16 = 1954974080 & (16 - 1) = 0 扰动函数优化后:1955003654 % 16 = 1955003654 & (16 - 1) = 6 很显然,减少了碰撞的几率。

 

参考:https://zhuanlan.zhihu.com/p/76735726

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Java集合-HashMap扰动函数

上一篇文章HashMap内部结构提到了 HashMap 有一个扰动函数,来判断元素落在数组的位置。下面通过具体的例子说明。 说明 get 方法如何确定key在数组中的位置,先通过 hash(key) 再通过 tab[(n...

gaob2001
2018/10/29
90
0
HashMap的长度为什么要是2的n次方

HashMap为了存取高效,要尽量较少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同,这个实现就在把数据存到哪个链表中的算法; 这个算法实际就是取模,hash%length,计算机中直接求余...

群星纪元
2019/04/06
26
0
Java——HashMap底层源码分析

1.简介 HashMap 根据键的 hashCode 值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的key为 null,允许多条v...

osc_y9wmeuxa
2019/08/10
2
0
Java集合(精选面试题整理)

前言:把这段时间复习的关于集合类的东西整理出来,特别是HashMap相关的一些东西,之前都没有很注意1.7 ->> 1.8的变化问题,但后来发现这其实变化挺大的,而且很多整理的面试资料都没有更新(...

奋斗的蜗牛001
04/17
20
0
hashmap

Java集合必会14问(精选面试题整理) 32018.07.28 10:58:06字数 4556阅读 29103 前言:把这段时间复习的关于集合类的东西整理出来,特别是HashMap相关的一些东西,之前都没有很注意1.7 ->> 1...

Sugar-xu
2019/10/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

eclipse汉化教程(附安装包)

eclipse汉化包安装步骤 一、去官网或者在本站下载Eclipse(不管是什么版,中文设置的方法都是差不多的,所以说我们汉化的教程不管未来更新多少个版本都是一样的) 官方下载地址:www.eclipse.o...

树懒宝宝
11分钟前
8
0
CocosCreator之分层管理的ListView

前言 进入公众号回复listview即可获得demo的git地址。 之前写的一篇文章《Creator之ScrollView那些事》中提到了官方Demo中提供的ListViewCtl,只是实现了纵向滑动,没有实现横向滑动。并且建议...

陈广文
14分钟前
11
0
在CSS Flexbox中,为什么没有“ justify-items”和“ justify-self”属性?

问题: Consider the main axis and cross axis of a flex container: 考虑伸缩容器的主轴和横轴: Source: W3C 资料来源: W3C To align flex items along the main axis there is one pro......

法国红酒甜
16分钟前
11
0
搜索解决方案 - ElasticSearch/Solr/Lucene

搜索解决方案 - ElasticSearch/Solr/Lucene 1. 什么是 ElasticSearch ElasticSearch 是一个基于 Lucene 的搜素服务器 是一个分布式、高扩展、实时的搜素与数据分析引擎 基于 RESTful web 接口...

夙梦o
20分钟前
26
0
设计模式学习笔记(五):工厂方法模式

1 前言 尽管简单工厂模式实现了对象的创建和使用分离,但是仍然存在以下两个问题: 工厂类过于庞大,包含了大量的判断代码,导致维护和测试难度增大 系统扩展不灵活,如果增加了新的产品类型...

氷泠
23分钟前
21
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部