日常中我们经常用到HashMap并且面试题也有很多针对它的,这次就说说他的长度~
默认为16我们都知道,默认的扩容负载因子是0.75f,每次扩容后容量都保持为2的幂;
如果我们自己设计一个类似于hashmap的数组加链表结构,我们拿到key做hashcode后让他均匀分布到数组上,我们可能会使用hashcode(key) % length;
为什么设计者没用这么简单的方式?
1.hashcode有可能出现负数,我们的下标当然不希望出现负数
2.取模运算速度会略慢于位运算
这时就来说说为什么使用&位运算,以及解决了什么问题:
1.当做&运算时,如果hashcode是负数,那么跟正数的length做&运算后,变为正数
2.速度肯定会比取模运算快
为什么是用2的幂,并且运算时 hashcode(key) & (2^n-1) :
因为2^n在二进制中表示都为1,所以它跟任何数做&运算,结果都还是被&数,如果二进制中出现了0,则可能有的下标永远不会用到;举例:
length=16,下标范围就是0待15,那么就是2^4-1 = 15,二进制为
1111
此时如果hashcode(key) = -12345,二进制为
11111111111111111100111111000111
然后做&运算,15不够位数补0为:
00000000000000000000000001111
则结果为 00000000000000000000000001111& 11111111111111111100111111000111= 00000000000000000000000000111
换算为十进制下标为7
本文由 GY 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为:
2021/11/19 15:27