HashMap 的长度为什么是2的幂次方

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。Hash 值的范围值-2147483648到2147483647，前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。

用之前还要先做对数组的长度取模运算。得到的余数才能用来要存放的位置，也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash ”。（n代表数组长度）。

因为在使用是2的幂的数字的时候，Length-1的值是所有二进制位全为1。这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。这是为了实现均匀分布。这也就解释了 HashMap 的长度为什么是2的幂次方。

这个算法应该如何设计呢？

我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“ 取余(%)操作中如果除数是2的幂次，则等价于与其除数减一的与(&)操作。 ”即 hash%length==hash&(length-1) 的前提是 length 是2的 n 次方。并且 采用二进制位操作 &，相对于%能够提高运算效率。

HashMap的长度为什么默认为16?

16是2的幂，8也是，32也是。偏偏选了16的原因如下。

我觉得就是一个经验值，定义16没有很特别的原因，只要是2次幂，其实用 8 和 32 都差不多。

用16只是因为作者认为16这个初始容量是能符合常用而已。

Hashmap中的链表大小超过八个时会自动转化为红黑树，当删除小于六时重新变为链表，为啥呢？

根据泊松分布，在负载因子默认为0.75的时候，单个hash槽内元素个数为8的概率小于百万分之一。所以将7作为一个分水岭。等于7的时候不转换。大于等于8的时候才转换。小于等于6的时候就化为链表。