为什么要扩容
当链表个数太多了，遍历可能比较耗时，转化成红黑树，可以使遍历的时间复杂度降低，但转化成红黑树，有空间和转化耗时的成本，我们通过泊松分布公式计算，正常情况下，链表个数出现 8 的概念不到千万分之一，所以说正常情况下，链表都不会转化成红黑树，这样设计的目的，是为了防止非正常情况下，比如 hash 算法出了问题时，导致链表个数轻易大于等于 8时，仍然能够快速遍历。
延伸问题：红黑树什么时候转变成链表
当节点的个数小于等于 6 时，红黑树会自动转化成链表，主要还是考虑红黑树的空间成本问题，当节点个数小于等于 6 时，遍历链表也很快，所以红黑树会重新变成链表。
什么时候扩容
- putMapEntries（）：插入
- putVal（）
- put（）
- treeifyBin（）
merge（）：合并
put 时，发现数组为空，进行初始化扩容，默认扩容大小为 16;
2. put 成功后，发现现有数组大小大于扩容的门阀值时，进行扩容，扩容为老数组大小的 2 倍;
扩容的门阀是 threshold，每次扩容时 threshold 都会被重新计算，门阀值等于数组的大小 * 影响因子（0.75）。
新数组初始化之后，需要将老数组的值拷贝到新数组上，链表和红黑树都有自己拷贝的方法。
HashMap扩容的条件
新建的HashMap容量为DEFAULT_INITIAL_CAPACITY=16，
系数DEFAULT_LOAD_FACTOR=0.75，
当第一次扩容时目前的元素数量>=DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR时，会将HashMap的容量扩大一倍（x2）,一次类推每次加入数据时都会判断当前的元素数与容量的占比。
最大个数为Integer.MAX_VALUE即2147483648。
加载因子默认0.75
HashMap的加载因子默认是 0.75
0.75是指当我存放元素的个数是我们内部数组的长度的0.75倍,我们就要进行数组的扩容
HashMap数组大小默认是多少？为什么它要是2的n次幂？
当数组长度为2的N次方时，不同的key算出的index相同的几率小，数据在数组上分配均匀，hash碰撞的几率小，提升查询效率，从大O(N)提升至O(1)；
扩容的问题,取出来重新插入
扩容是HashMap原本的长度乘以2 , 扩容是生成一个新的数组,然后把旧的数据的值都取出来重新插入一遍,如果不这样的话就会存在问题, 因为 存放数组的index的值是根据 hashCode值&数组长度-1 ; 如果你不重新插入的话那么原来通过算法存放在数组的位置的值就对不上了.
所以扩容也叫重新散列
用位移算法它的性能比加减乘除的性能更高, 还需要处理Entity的 next指针.
扩容是性能非常低下的,所以建议初始化HashMap的时候,如果刚开始就能确定长度的话,就尽量给出合适的长度,但是也不能盲目的给太多长度,会占用空间消耗磁盘. 所以要选择合适的长度.
正常的扩容操作刘畅
正常的扩容操作是这个流程。HashMap的扩容在put操作中会触发扩容，主要是三个方法：
扩容过程
当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值—即当前数组的长度乘以加载因子的值的时候，就要自动扩容。
扩容( resize )就是重新计算容量，向 HashMap 对象里不停的添加元素，而 HashMap 对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然 Java 里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组。
HashMap hashMap=new HashMap(cap);
cap =3， hashMap 的容量为4；
cap =4， hashMap 的容量为4；
cap =5， hashMap 的容量为8；
cap =9， hashMap 的容量为16；
如果 cap 是2的n次方，则容量为 cap ，否则为大于 cap 的第一个2的n次方的数。
综合来说，HashMap一次扩容的过程：
1、取当前table的2倍作为新table的大小
2、根据算出的新table的大小new出一个新的Entry数组来，名为newTable
3、轮询原table的每一个位置，将每个位置上连接的Entry，算出在新table上的位置，并以链表形式连接
4、原table上的所有Entry全部轮询完毕之后，意味着原table上面的所有Entry已经移到了新的table上，HashMap中的table指向newTable
实例
现在hashmap中有三个元素，Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table[1]这里了。
按照方法中的代码
对table[1]中的链表来说，进入while循环，此时e=key(3)，那么next=key(7)，经过计算重新定位e=key(3)在新表中的位置，并把e=key(3)挂在newTable[3]的位置
这样循环下去，将table[1]中的链表循环完成后，于是HashMap就完成了扩容
HashMap怎么设定初始容量大小？
一般如果 new HashMap() 不传值，默认大小是16，负载因子是0.75， 如果自己传入初始大小k，初始
化大小为 大于k的 2的整数次方，例如如果传10，大小为16。（补充说明:实现代码如下）
static final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}123456789
补充说明：下图是详细过程，算法就是让初始二进制右移1，2，4，8，16位，分别与自己位或，
把高位第一个为1的数通过不断右移，把高位为1的后面全变为1，最后再进行+1操作，111111 +
1 = 1000000 = 26
（符合大于50并且是2的整数次幂 ）
HashMap 如何保证容量一直是2的N次方，如果构造函数传的不是2的n次方呢？
- hashMap有一个tableSizeFor方法，会保证集合的容量是2的N次方，大小是比入参值大，并且离入参值最近的2的N次方那个数
- 如入参:0 容量：0
- 入参:1 容量：1
- 入参:2 容量：2
- 入参:3 容量：4
- 入参:4 容量：4
- 入参:5 容量：8
代码
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
- | ，或操作， 0和1，则为1
， 无符号右移（这个其实用 >> 和用 >>> 没什么区别）
- 第6行，自己右移一位和自己做或操作
- 第7行，自己右移两位和自己做或操作
- 第8行，自己右移4位和自己做或操作
- 一直到第10行，都是
- 那么，加起来，一共右移了35位
- 总结下，这个算法要做的事是啥，就是要把2进制的，把你从最高位开始，后面的全变成1，最后返回结果又加1，就变成2的n次方了
- 刚开始为什么要减一呢，就是为了临界值，如果你传的已经是2的n次方了，如果不减一，算出来的就是16了（把8的二进制，后面都变成1，结果又加1，就变成16了），如果减一，那就是7，把7的后面都变成1，再加1，那是8。所以最开始第5行，先减一
- 如果还没看懂看下面的
总结
HashMap的加载因子默认是 0.75
0.75是指当我存放元素的个数是我们内部数组的长度的0.75倍,我们就要进行数组的扩容
综合来说，HashMap一次扩容的过程：
1、取当前table的2倍作为新table的大小
2、根据算出的新table的大小new出一个新的Entry数组来，名为newTable
3、轮询原table的每一个位置，将每个位置上连接的Entry，算出在新table上的位置，并以链表形式连接
4、原table上的所有Entry全部轮询完毕之后，意味着原table上面的所有Entry已经移到了新的table上，HashMap中的table指向newTable
若有收获，就点个赞吧
0 人点赞
