HashMap等集合初始化时应制定初始化大小-LMLPHP

阿里巴巴开发规范中,推荐用户在初始化HashMap时,应指定集合初始值大小。

一、原因

这个不用多想,肯定是效率问题,那为什么会造成效率问题呢?

当我们new一个HashMap没有对其容量进行初始化的时候,系统会默认创建一个16大小的集合。当我们使用的集合太小时,就会造成内存的浪费,而当HashMap的容量超过临界值时,HashMap就会扩容到下一个2的指数幂(2->4,4->8,8->16)。扩容(resize)时,HashMap会重新建立hash表,重新计算没个元素的位置,这是很消耗资源的。

二、合理的设置

当我们使用HashMap(int initialCapacity)来初始化容量的时候,jdk会默认帮我们计算出一个相对合理的值当做初始容量。当HashMap的容量值超过了临界值(threshold)时就会扩容,threshold = HashMap的容量值*0.75,比如初始化容量为8的HashMap当大小达到8*0.75=6时将会扩容到16。当我们设置HashMap的初始化容量是遵循expectedSize(预期大小)/0.75+1,比如expectedSize是6时 6/0.75+1=9,此时jdk处理后会被设置成16,大大降低了HashMap被扩容的几率。

当我们通过HashMap(int initialCapacity)设置初始容量时,HashMap不一定会采取我们设置的初始容量,会根据计算得到一个新的值(2的指数幂),以保证hash的效率。

PS.为什么容量一定要是2的指数幂?

简答:1.节约空间 2.让元素分布均匀

详细:

hashMap源码获取元素的位置:

static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
h:为插入元素的hashCode

length:为map长度

&:与操作

如果length为2的次幂 则length-1 转化为二进制必定是11111……的形式,再与h的二进制与操作效率会非常的快,而且空间不浪费;如果length不是2的次幂,比如length为15,则length-1为14,对应的二进制为1110,再与h与操作,最后一位都为0,而0001,0011,0101,1001,1011,0111,1101这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!这样就会造成空间的浪费。

05-25 20:08