HashMap的大小为什么是2的n次方大小呢

提问者:帅平 问题分类:面试刷题
HashMap的大小为什么是2的n次方大小呢
1 个回答
一心居一人
一心居一人
在 JDK1.7 中,HashMap 整个扩容过程就是分别取出数组元素,一般该元素是最后一个放入链表中的元素,然后遍历以该元素为头的单向链表元素,依据每个被遍历元素的 hash 值计算其在新数组中的下标,然后进行交换。这样的扩容方式会将原来哈希冲突的单向链表尾部变成扩容后单向链表的头部。
而在 JDK 1.8 中,HashMap 对扩容操作做了优化。由于扩容数组的长度是 2 倍关系,所以对于假设初始 tableSize = 4 要扩容到 8 来说就是 0100 到 1000 的变化(左移一位就是 2 倍),在扩容中只用判断原来的 hash 值和左移动的一位(newtable 的值)按位与操作是 0 或 1 就行,0 的话索引不变,1 的话索引变成原索引加上扩容前数组。
之所以能通过这种“与运算“来重新分配索引,是因为 hash 值本来就是随机的,而 hash 按位与上 newTable 得到的 0(扩容前的索引位置)和 1(扩容前索引位置加上扩容前数组长度的数值索引处)就是随机的,所以扩容的过程就能把之前哈希冲突的元素再随机分布到不同的索引中去。
发布于:1个月前 (04-23) IP属地:四川省
我来回答