负载因子是什么
我们知道HashMap中数组长度是16(什么？你说不知道，看下源码你就知道)，假设我们用的是最优秀的hash算法，即保证我每次往HashMap里存键值对的时候，都不会重复，当hashmap里有16个键值对的时候，要找到指定的某一个，只需要1次；
之后继续往里面存值，必然会发生所谓的”hash碰撞”形成链表，当hashmap里有32个键值对时，找到指定的某一个最坏情况要2次；当hashmap里有128个键值对时，找到指定的某一个最坏情况要8次
随着hashmap里的键值对越来越多，在数组数量不变的情况下，查找的效率会越来越低。那怎么解决这个问题呢？只要增加数组的数量就行了，键值对超过16，相应的就要把数组的数量增加(HashMap内部是原来的数组长度乘以2)，这就是网上所谓的扩容，就算你有128个键值对，我们准备了128个坑，还是能保证”一个萝卜一个坑”。
其实扩容并没有那么风光，就像ArrayList一样，扩容是件很麻烦的事情，要创建一个新的数组，然后把原来数组里的键值对”放”到新的数组里，这里的”放”不像ArrayList那样用原来的index，而是根据新表的长度重新计算hashCode，来保证在新表的位置，老麻烦了，所以同一个键值对在旧数组里的索引和新数组中的索引通常是不一致的(火男：”我以前是3号，怎么现在成了127号，给我个完美的解释！”新表：”大清亡了，现在你得听我的”)。另外，我们也可以看出这是典型的以空间换时间的操作。
说了这么多，那负载因子是个什么东西？负载因子其实就是规定什么时候扩容。上面我们说默认hashmap数组大小为16，存的键值对数量超过16则进行扩容，好像没什么毛病。然而HashMap中并不是等数组满了(达到16)才扩容，它会存在一个阈值(threshold)，只要hashmap里的键值对大于等于这个阈值，那么就要进行扩容。阈值的计算公式：
阈值 = 当前数组长度✖负载因子
hashmap中默认负载因子为0.75，默认情况下第一次扩容判断阈值是16 ✖ 0.75 = 12；所以第一次存键值对的时候，在存到第13个键值对时就需要扩容了；或者另外一种理解思路：假设当前存到第12个键值对：12 / 16 = 0.75，13 / 16 = 0.8125(大于0.75需要扩容) 。肯定会有人有疑问，我要这铁棒有何用？不，我要这负载因子有何用?直接规定超过数组长度再扩容不就行了，还省得每次扩容之后还要重新计算新的阈值，Google说取0.75是一个比较好的权衡，当然我们可以自己修改，HashMap初识化时可以指定数组大小和负载因子，你完全可以改成1。
<figure class="highlight plain" style="display: block; margin: 20px 0px; overflow: auto; padding: 0px; font-size: 13px; color: rgb(77, 77, 76); background: rgb(247, 247, 247); line-height: 1.6; border-radius: 1px; font-family: Lato, "PingFang SC", "Microsoft YaHei", sans-serif; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: justify; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">
|
<pre style="overflow: auto; font-family: consolas, Menlo, "PingFang SC", "Microsoft YaHei", monospace; font-size: 13px; margin: 0px; padding: 10px; color: rgb(134, 145, 148); background: rgb(239, 242, 243); line-height: 1.6; border: none; text-align: right;">
1
</pre>
|
<pre style="overflow: auto; font-family: consolas, Menlo, "PingFang SC", "Microsoft YaHei", monospace; font-size: 13px; margin: 0px; padding: 10px; color: rgb(77, 77, 76); background: rgb(247, 247, 247); line-height: 1.6; border: none; width: 399px;">
public HashMap(int initialCapacity, float loadFactor)
</pre>
|
</figure>
我的理解是这负载因子就像人的饭量，有的人吃要7分饱，有的人要10分饱，稳妥起见默认让我们7.5分饱。
小结
在数组大小不变的情况下，存放键值对越多，查找的时间效率会降低，扩容可以解决该问题，而负载因子决定了什么时候扩容，负载因子是已存键值对的数量和总的数组长度的比值。默认情况下负载因子为0.75，我们可在初始化HashMap的时候自己修改。
hash与Rehash
hash和rehash的概念其实上面已经分析过了，每次扩容后，转移旧表键值对到新表之前都要重新rehash，计算键值对在新表的索引。如下图火男这个键值对被存进hashmap到后面扩容，会经过hash和rehash的过程
第一次hash可以理解成’”分类”‘，方便后续取、改等操作可以快速定位到具体的”坑”。那么为什么要进行rehash，按照之前元素在数组中的索引直接赋值，例如火男之前3号坑，现在跑到30号坑。
个人理解是，在未扩容前，可以看到如13号链的长度是3，为了保证我们每次查找的时间复杂度O趋于O(1)，理想的情况是”一个萝卜一个坑”，那么现在”坑”多了，原来”3个萝卜一个坑”的情况现在就能有效的避免了。
