④. hashMap的二倍扩容
- ①. 扩容核心,为何2倍扩容,为何默认初始化容量16？——新增一倍的空间,将原空间一半的数据移动到新空间,重新达到离散平衡、保证效率
二倍扩容说明:
二倍扩容、2的次幂——16初始化容量,实则都是为了完美整合寻址散列算法。
我们发现一个有趣的二进制计算技巧
n % m —> 当m的值是二的次幂的时候,它可以由 n & (m-1)替代,后者的效率也是更高。
比如:10 % 4 = 2 ==> 10 & 3 = 2
所以,如果默认初始化是16,那么数组最大下标用二进制表示就是1111。
那么当根据key获取到h值之后,h & 1111运算,获取到一个下标值,实则只跟h值的低四位有关。
关键点就在这里！当二倍扩容时！最大数组下标由二进制1111变成11111,四位变五位
那么h值二进制的第五位,它不是0,就是1！
如果是0,则下标值不变,因为0 & 1 为 0；如果是1,则新下标值=原下标值+原容量大小值
这就是二倍扩容、二的次幂默认初始化大小(16)、寻址算法、扩容实现的核心所在！
⑤. 这有1000个非重复的键值对要存储,我需要怎么初始化我的HashMap？
①. 然而,1000个数你用1024的空间来存储,你还怎么实现空间换时间？富余的空间太少,哈希冲突肯定很多,影响使用效率。再说,HashMap默认负载因子0.75,它也不会让你1024空间存够1000,在存储的数据size到达768的时候,这个HashMap已经执行自动扩容了！为了不让它自动扩容,所以我们初始化为2048！当然你可以初始化为1023——2048之间的任何容量值,结果都是2048
解释:
1.如果我们确切的知道我们有多少键值对需要要存储(其它的动态数据结构使用亦是如此),那么我们在初始化HashMap的时候就应该指定它的容量,以防止HashMap自动扩容,影响使用效率。
2.有的同学说应该给它初始化容量为1000,有的同学说应该给他初始化为1024。实则都不对！
3.HashMap底层是这样实现的初始化的,当你给HashMap初始化为一个n的容量时,程序会用算法自动计算出一个不小于n的一个二的次幂值(原因前面已经说明),所以这里你就算给他指定1000容量,实则初始化后分配的容量也是1024。
如上代码,实则是将cap这个数的二进制数从第一个1开始,把后面的二进制位全部变成1,然后+1操作,实则是取不小于n的一个最近的2的次幂
