hashmap--为什么HashMap的桶数量是2的幂次方

hahsmap默认桶的大小是16.

 

初始化hashmap的时候看构造方法，会发现传入的初始化initialCapacity桶大小会被做一次转成2的幂的操作。

 

hashmap扩容 resize的时候也会乘2

 

为什么桶的大小要是2的幂？

为的是均匀散列

 

 

在jdk1.7 里面 索引的计算公式为    index =（capacity - 1） & hash(key)

 

假设 capacity 为  2  二进制表示为 10   .。  capacity-1 为1  二进制表示为  1

假设 capacity 为  4  二进制表示为 100   .。  capacity-1 为3  二进制表示为  11

假设 capacity 为  8  二进制表示为 1000   .。  capacity-1 为7  二进制表示为  111

 

2^n - 1得出的结果转换为二进制必然是 1111...111这样的，和hashcode 做 按位与操作 的时候，都是由hahscode来决定散列，不会形成缺口。

 

通过计算如果 capacity为8，通过计算发现散列会均匀分布。

 

 

如果 capacity为9，数据会极端分布，只会是0或者8.数据只会放在这两个桶里面。其他桶不会有数据。

 

 

------------------------------------------------------------------------------------------------

jdk1.7  里面桶里面的数据结构是链表

jdk1.8 桶里面的数据结构可能是链表，可能是红黑树（平衡二叉树）。

 

一旦桶里面的链表数量过多，查找是很慢的。