栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

HashMap的默认容量为何为16?为何是2的整数倍?

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

HashMap的默认容量为何为16?为何是2的整数倍?

对于HashMap的table而言,数据分布需要均匀(最好每项都只有一个元素,这样就可以直接通过数据下标直接找到),不能太松,浪费空间。不能太紧,查询变慢。计算hash值后,怎么才能保证table元素分布均匀呢?我们会想到取模,但是由于取模的消耗较大,

HashMap是这样处理的:调用indexFor()方法

static int indexFor(int h, int length) { 
	return h & (length-1);
}

返回的是key的hashcode跟哈希表容量-1做与运算。运算的结果便是哈希表中数组的下标。

分析:
h:不可控
length-1:可控

准备:与运算:1&1=1;   1&0=0;   0&0=0。

1. 奇数的最后一个二进制位是1,偶数的最后一个二进制位是0。
2. 当length-1为奇数时,无论h是什么数值,结果的二进制最后一位可能是1,也可能是0,则结果可能是正数,也可能是负数。
3. 当length-1为偶数时,无论h是什么数值,结果的二进制位必是0,则结果是必然是偶数。

当length为偶数时,便保证了h&(length-1)结果的最后一个二进制位是0,也可能是1,即结果可能是偶数也可能是奇数。这样便可以保证散列的均匀性!

当length为奇数时,h&(length-1)结果必然是偶数,这样任何hash值都只会被散列到数组的偶数下标上,浪费了一半的数组空间(内存空间)。

所以length取2的整数此幂,是为了使不同hash值发生碰撞的概率较小,使元素在HashMap中均匀散列分布位置。

所以默认的length为16,即2^4。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/659035.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号