HashMap的默认初始长度是多少?为什么?

简介: HashMap的默认初始长度是多少?为什么?

1. 默认长度是多少?


HashMap的默认初始长度是16,自动拓展和手动初始化时,长度必须是2的幂,即2^n (每次扩容都是以2的整数次幂扩容


2.为什么是16呢?


选择16是为了服务于从Key映射到index的Hash算法,在性能和内存的使用上取平衡,实现一个尽量均匀分布的Hash函数,选取16,是通过位运算的方法进行求取的。


3.详细讲解一下hash过程


Hash函数:index=Hash(Value)

位运算求HashMap函数,位运算:index=Hash数据(Key)&(length-1),进行的是二进制的与(&)运算

例如index=101111100100 1011 (Hash数据)&1111(默认长度16的二进制)=1011,结果取决于Value的最后四位,

1111是(Length-1)默认的Length是16,Length-1是15的二进制

使用位运算,效果上和取模(index=Hash数据(Key)%Length)相当,同时提高了性能


4.使用比16小的数看看会有什么问题?


设HashMap的长度是9,则

index=11100011010101(Hash数据)&1000(Length-1)=0000

设HashMap的长度是10,则

index=11100011010101(Hash数据)&1001(Length-1)=0001

设HashMap的长度是16,则

index=11100011010101(Hash数据)&1111(Length-1)=0101


5.分析


长度为9时,-000,的结果出现概率非常大,出现其他结果的概率很小

长度为10时,出现-00-,的结果概率很大,出现其他结果的概率较小

长度为16时,可能会出现各种结果出现,因为(Length-1=15)  15的二进制1111,可以出现所有结果,在Length为16的前提下,只要输入的Hash数据本身分布均匀,Hash算法的结果就是均匀的。



相关文章
|
8月前
|
机器学习/深度学习 算法 数据处理
盘点四种计算数组中元素值为1的个数的方法
盘点四种计算数组中元素值为1的个数的方法
144 0
|
8月前
|
存储 缓存 算法
HashMap 默认加载因子非得是0.75
HashMap 默认加载因子非得是0.75
41 0
jdk8 Stream流中将集合转成map,重复key处理,统计最大值,获取某个属性集合等10种最常用方法
jdk8 Stream流中将集合转成map,重复key处理,统计最大值,获取某个属性集合等10种最常用方法
204 5
|
JavaScript Python
从列表中或数组中随机抽取固定数量的元素组成新的数组或列表
从列表中或数组中随机抽取固定数量的元素组成新的数组或列表
83 0
|
存储 Java
合理设置 HashMap 初始值大小
合理设置 HashMap 初始值大小
195 0
|
算法 PHP 数据安全/隐私保护
为什么PHP的MD5可以将任意长度的数据映射为固定长度的哈希值?底层原理是什么?
为什么PHP的MD5可以将任意长度的数据映射为固定长度的哈希值?底层原理是什么?
278 0
|
算法 Go
算法练习第十题——寻找重复数(不修改数组)
给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。
|
Java
ArrayList的初始容量是多少?
ArrayList的初始容量是多少? 很多人给出的答案是10 最近无意中又看了下ArrayList源码,发现江山已不再啊,很多时候面试自我感觉还不错,总被淘汰呢,也有这方面的原因,自不知了 源码出自JDK8版本,追溯了一下,JDK7高版本时代就开始变了
359 0
HashMap初始容量
在已知HashMap中将要存放的KV个数的时候,设置一个合理的初始化容量可以有效的提高性能。
232 0
HashMap初始容量
|
Java
Java数组元素的默认初始化值
Java数组元素的默认初始化值
108 0