在面试中,经常遇到集合相关问题,集合中必定逃不掉HashMap,那简单的都懂,比如hashmap初始长度,大部分人都知道是16,那如果面试官问为什么呢?这个时候看到这篇文章的小伙伴就赚了,带你彻底了解懂hashmap的默认初始长度为什么是16
HashMap的默认初始长度是16,自动拓展和手动初始化时,长度必须是2的幂,即2^n (每次扩容都是以2的整数次幂扩容
选择16是为了服务于从Key映射到index的Hash算法,在性能和内存的使用上取平衡,实现一个尽量均匀分布的Hash函数,选取16,是通过位运算的方法进行求取的。
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)相当,同时提高了性能
设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
长度为9时,-000,的结果出现概率非常大,出现其他结果的概率很小
长度为10时,出现-00-,的结果概率很大,出现其他结果的概率较小
长度为16时,可能会出现各种结果出现,因为(Length-1=15) 15的二进制1111,可以出现所有结果,在Length为16的前提下,只要输入的Hash数据本身分布均匀,Hash算法的结果就是均匀的。