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算法的结果就是均匀的。



相关文章
|
6月前
|
算法 Java 开发者
为啥HashMap的默认容量是16?
为啥HashMap的默认容量是16?
63 0
|
6月前
|
算法
递归淘汰List集合头部数据,获取最终集合的起始坐标
递归淘汰List集合头部数据,获取最终集合的起始坐标
|
6月前
|
存储 缓存 算法
HashMap 默认加载因子非得是0.75
HashMap 默认加载因子非得是0.75
35 0
封装一个函数,可以自定义范围与跳过的数字。 例如在 100(不固定) ~ 1000(不固定) 内查找 5 (不固定)的倍数 和 带有 5 的值
封装一个函数,可以自定义范围与跳过的数字。 例如在 100(不固定) ~ 1000(不固定) 内查找 5 (不固定)的倍数 和 带有 5 的值
56 0
jdk8 Stream流中将集合转成map,重复key处理,统计最大值,获取某个属性集合等10种最常用方法
jdk8 Stream流中将集合转成map,重复key处理,统计最大值,获取某个属性集合等10种最常用方法
177 5
|
6月前
Stream流中将集合转成map,重复key处理,统计最大值,获取某个属性集合等12种最常用方法
Stream流中将集合转成map,重复key处理,统计最大值,获取某个属性集合等12种最常用方法
125 0
|
JavaScript Python
从列表中或数组中随机抽取固定数量的元素组成新的数组或列表
从列表中或数组中随机抽取固定数量的元素组成新的数组或列表
63 0
|
存储 算法 JavaScript
设计并实现一个函数, 功能为给定一个存储为随机整数的数组,从中删除所有值为i的整数
设计并实现一个函数, 功能为给定一个存储为随机整数的数组,从中删除所有值为i的整数
|
算法 PHP 数据安全/隐私保护
为什么PHP的MD5可以将任意长度的数据映射为固定长度的哈希值?底层原理是什么?
为什么PHP的MD5可以将任意长度的数据映射为固定长度的哈希值?底层原理是什么?
269 0
|
算法 Go
算法练习第十题——寻找重复数(不修改数组)
给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。