首页 > 技术文章 > HashMap(JDK1.8)的容量为什么是2的n次方

liuwhut 2020-07-08 16:32 原文

1.提高计算效率

我们知道HashMap底层是数组+链表+红黑树,确定元素在数组的哪个位置上需要用到hash值,计算公式如下:
hash % length等价于(length - 1) & hash
length:数组的长度即HashMap的容量
hash:key的hash值
这个等价的前提是length为2^n
&比%快,所以为了效率,将length设为2^n

2.提高扩容的效率

当数组上某个位置是一个链表时,不需要像JDK1.7一样重新计算hash,只需要看原来的hash值新增的那个bit是1还是0就好了,如果是0索引没变,如果是1索引变成“原索引+原容量”

ps:扩容为原来的2倍还有一个特点就是,扩容后元素要么在原位置,要么在原位置移动2次幂的位置
比如有两个元素ABA的hashCode = 100,B的hashCode = 115。有个HashMap原来的容量是16,现在扩容为32.
那么在扩容前:A在数组中的索引为100%16=4,B在数组中的索引为115%16=3
扩容后:A在数组中的索引为100%32=4,B在数组中的索引为115%32=19
可以看到A在扩容前后索引没变,B扩容后索引变为了19,也就是原索引+原容量

推荐阅读