hashmap

为什么都要扩展为原来的2倍

这是因为，将数组容量扩展为原来的两倍，可以在保证空间利用率的同时，最大限度地减少哈希冲突的发生。具体地说，如果将数组容量扩展为原来的 k 倍，虽然可以进一步降低哈希冲突的概率，但也会造成空间浪费；而如果将数组容量扩展为原来的 1.5 倍，虽然可以减少空间浪费，但也会增加哈希冲突的概率。因此，将数组容量扩展为原来的两倍，可以在空间利用率和哈希冲突之间取得一个较好的平衡。hash % length == hash & (length - 1)这个关系只有在length等于二的幂次方时成立，位运算能比%高效得多

扩容因子为什么是 0.75

而HashMap中加载因子为0.75，是考虑到了性能和容量的平衡。

由加载因子的定义，可以知道它的取值范围是(0, 1]。

• 如果加载因子过小，那么扩容门槛低，扩容频繁，这虽然能使元素存储得更稀疏，有效避免了哈希冲突发生，同时操作性能较高，但是会占用更多的空间。
• 如果加载因子过大，那么扩容门槛高，扩容不频繁，虽然占用的空间降低了，但是这会导致元素存储密集，发生哈希冲突的概率大大提高，从而导致存储元素的数据结构更加复杂（用于解决哈希冲突），最终导致操作性能降低。
• 还有一个因素是为了提升扩容效率。因为HashMap的容量（size属性，构造函数中的initialCapacity变量）有一个要求：它一定是2的幂。所以加载因子选择了0.75就可以保证它与容量的乘积为整数。

在负载因子0.75（HashMap默认）的情况下，单个hash槽内元素个数为8的概率小于百万分之一，将7作为一个分水岭，等于7时不做转换，大于等于8才转红黑树，小于等于6才转链表。链表中元素个数为8时的概率已经非常小，再多的就更少了，所以原作者在选择链表元素个数时选择了8，是根据概率统计而选择的。