您的位置 首页 java

HashMap数组长度为什么是2的n次方

hashmap 是基于哈希表的数据结构实现的集合。底层 是由一个Node数组构成的,在j dk1.8之后采用数组+(链表或红黑树)的方式实现。

 transient Node<K,V>[] table  

node数组的长度在初始化或者扩容( resize) 时会被指定,无论怎么变, 数组长度始终都是2的n次方。

为什么要是2的n次方?

key在table中的定位是由(length – 1) & hash确定的,length为数组的长度。因为length是2的n次方,所以length-1的 二进制 肯定是11111….11的形式,此时length-1和hash进行&运算时不会有空间的浪费,且位运算效率很高。假设length不是2的次幂,比如length为15,则 length-1为14,二进制为1110,和hash进行&操作,最后一位都为0,增加了碰撞,使得一些空间被浪费。

总结就是这样做可以 减少哈希冲突,均匀分布元素 ,从代码上来说就是 按位“与”的时候,每一位都能&1。

如何保证是2的n次方的?

1)初始化指定容量时,通过tableSizeFor方法返回一个目标容量的2次幂的值(如果目标容量值不是2的n次方,就会返回一个大于该目标值的最小二次幂,如cap为10则返回16)。

2)扩容即resize()得到的新数组长度也是2的n次方。实际数组初始化也是首次put值时通过resize方法完成的。

扩容得到的新数组的长度newCap有三处赋值,可以看到都是2的n次幂。对应图中:1是通过位运算扩容为原长度的2倍;2是 hash map初始化时指定的;3是默认值16。

这里源码中还有个小细节的处理,就是hash()对key的处理并不是只取hashcode。可以说每一个细节都在尽可能的优化,存在必有其原因。

文章来源:智云一二三科技

文章标题:HashMap数组长度为什么是2的n次方

文章地址:https://www.zhihuclub.com/198241.shtml

关于作者: 智云科技

热门文章

发表回复

您的电子邮箱地址不会被公开。

网站地图