HashMap扩容机制解读

何时扩容：

当 hashmap 中的元素数量超过数组大小 * loadFactor 时，Java数组扩容。loadFactor的默认值是_ LOAD_ 当hashmap中的元素个数超过16 * 0.75 = 12(阈值或边界值)时，将数组的大小扩展为2 * 16 = 32，然后重新计算每个元素在hashmap中的位置数组。这是一个非常消耗性能的操作，所以我们最好能够提前预测和设置元素的数量。

注意：

当hashmap中一个链表的对象个数达到8个时，如果数组长度没有达到64，那么hashmap会先展开。如果达到64，就会变成红黑树，Node类型从Node变成TreeNode。当然，如果去掉映射关系，下一次执行reset()方法时，会判断树中的节点数小于6，也会将树转换为链表

什么是扩容

扩展会伴随着新的hash分配，会遍历hash表中的所有元素，非常耗时。在编写程序的过程中，我们应该尽量避免resize()

每次扩充一倍，与原来的(n-1)&hash结果相比，只多了一位，所以节点要么在原来的位置，要么会被分配到“原来的位置+旧容量”的位置

原始数组长度：16 n = n - 1 ---> 15
(n - 1) & 散列
		 	 0000 0000 0000 0000 0000 0000 0001 0000 16
			 0000 0000 0000 0000 0000 0000 0000 1111 15 n - 1
hash1 (key1):1111 1111 1111 1111 0000 1111 0000 0101    
-------------------------------------------------- --------------
			 0000 0000 0000 0000 0000 0000 0000 1111 索引 5
			 
			 0000 0000 0000 0000 0000 0000 0000 1111 15 n - 1
hash2 (key2):1111 1111 1111 1111 0000 1111 0000 0101   
-------------------------------------------------- --------------
			 0000 0000 0000 0000 0000 0000 0000 1111 索引 5
================================================== ==============
数组长度扩展——> 16 * 32 n - 1 ---> 31
(n - 1) & 散列
			 0000 0000 0000 0000 0000 0000 0010 0000 32
			 0000 0000 0000 0000 0000 0000 0001 1111 31 n - 1
hash1(key1): 1111 1111 1111 1111 0000 1111 0000 0101   
-------------------------------------------------- --------------		 
			 0000 0000 0000 0000 0000 0000 0000 0101 索引 5
			 
			 0000 0000 0000 0000 0000 0000 0001 1111 31 n - 1
hash2 (key2):1111 1111 1111 1111 0000 1111 0000 0101   			
-------------------------------------------------- --------------			
			 0000 0000 0000 0000 0000 0000 0001 0101 指数 5 + 16

所以，元素重新计算hash后，因为N变成了两倍，n-1的标签范围比高位多1位，所以新的索引会变成这样

原来的位置=原来的位置+oldCap

注：5 为假设计算出的原始指标值，以验证功能描述。扩容后节点要么在原位置，要么分配到“原位置+旧容量”位置

因此，我们在展开hash map时，不需要重新计算hash值。我们只需要看原始哈希值的新位是1还是0，

(0表示索引没有变化，1表示原始索引+旧容量)

因为这种巧妙的rehash方法，不仅节省了重新计算hash值的时间，而且新的1位是0或1

这是随机的。在reszie的过程中，保证rehash后每个bucket上的节点数必须小于等于原bucket上的节点数，从而保证rehash后不会出现更严重的hash冲突，并将之前的冲突节点均匀地分散到新的bucket中。

初始化映射说明：

HashMap 的扩展机制是在满足扩展条件时进行扩展。HashMap 的扩展条件是当HashMap 中的元素个数超过阈值时，会自动扩展。因此，如果我们不设置初始容量，随着元素数量的增加，HashMap 可能会扩展数倍。HashMap 中的扩展机制决定了每次都需要重新构建哈希表，极大地影响了性能。

关于设置HashMap的初始化容量：

可以认为，当我们知道HashMap中的元素个数时，将默认容量设置为initialCapacity/0.75F+1.0F从性能上来说是一个比较好的选择，但也会牺牲一些内存。

Jdk 并没有直接将用户传入的数作为默认容量，而是会进行一些计算，最终得到一个 2 的幂。

例子：

initalCapacity =(要存储的元素数/负载因子)+ 1

默认情况下，负载因子为 0.75。如果暂时不能确定大小，建议设置为16

如果开始时没有指定初始化因子。当需要放置1024个元素时，随着元素数量的增加，需要扩容7倍并重建哈希表，严重影响性能。