什么是负载因子？哈希表为什么要扩容（rehash）？

简化版

负载因子 = 元素个数 / 桶个数，衡量哈希表的「拥挤程度」。它越大，冲突越多、每个桶越挤、查找越慢。当负载因子超过阈值（Java HashMap 默认 0.75），哈希表就扩容：申请一个更大的桶数组（通常翻倍），把所有元素重新计算下标搬过去（rehash），让元素重新散开、恢复 O(1) 性能。

详细版

负载因子（load factor）：α = 已存元素数 / 桶数组容量。

α 太大 → 桶里元素多，冲突严重，链表变长，查找退化。
α 太小 → 桶大量空着，浪费内存。

0.75 是 Java HashMap 在「时间」和「空间」之间选的默认折中：既不太挤（保证查找快），也不太空（不太浪费）。

扩容（resize / rehash）流程：

元素数超过 容量 × 负载因子（如 16×0.75=12）就触发。
新建一个两倍容量的桶数组。
把旧数组每个元素重新按新容量算下标，搬到新数组。
释放旧数组。

因为容量变了，hash % capacity 的结果变了，所以必须重新分配位置——这就是 “rehash” 的含义。

完整版教学

一、负载因子为什么决定性能

哈希表 O(1) 的前提是「每个桶里元素很少」。负载因子正是「平均每个桶几个元素」的度量。用拉链法时，α = 1 大致意味着平均每桶 1 个元素，查找接近理想；α = 5 就意味着平均每桶 5 个，查找要多比几次。所以控制负载因子 = 控制平均查找长度。开放寻址法更敏感，α 接近 1 时探测代价会爆炸式上升，因此它的阈值要设得更低。

二、0.75 这个值是怎么来的

Java HashMap 默认 0.75，是经验折中：

设成 1.0：空间省，但冲突概率明显上升，查找变慢。
设成 0.5：查找快，但一半桶空着，内存翻倍浪费，且扩容更频繁。
0.75：泊松分布下，桶里元素个数超过 8 的概率极低（约千万分之六），既让链表几乎不会太长，又不太浪费空间。

它是「查询速度」和「内存占用」的平衡点。

三、扩容为什么必须 rehash（不能直接拷贝）

元素的下标是 hash & (capacity - 1)（容量 2 的幂时），一旦容量从 16 变成 32，掩码从 1111 变成 11111，同一个 hash 算出的下标就可能变了。所以不能原样搬，必须按新容量重新计算每个元素的桶位置。

Java 8 的优化：容量翻倍后，旧桶里的元素要么留在原下标，要么去原下标 + 旧容量，二选一（取决于 hash 多出来的那一位是 0 还是 1）。这样不用重新算 hash 取模，只需判断一个 bit，把一条链拆成「低位链」和「高位链」两条，效率更高。

四、扩容的代价与注意点

扩容是 O(n)：要搬所有元素。所以单次 put 偶尔会很慢，但摊到大量插入上，均摊仍是 O(1)。
预估容量避免多次扩容：如果已知要存 1000 个元素，直接 new HashMap<>(2048)（或按 期望/0.75 设置初始容量），一次到位，省掉多次扩容搬迁。
扩容不是无限的：达到最大容量（1<<30）后不再扩，只能容忍冲突加剧。

五、并发下扩容的坑

Java 7 的 HashMap 在多线程同时扩容时，头插法可能形成环形链表，导致 get 死循环、CPU 100%。这也是「HashMap 线程不安全、并发要用 ConcurrentHashMap」的经典例证。Java 8 改成尾插并优化了扩容逻辑，缓解了成环问题，但多线程下仍不保证安全，该用 ConcurrentHashMap 还是得用。

六、常见误区与追问

参数	含义	影响
capacity	桶数组容量	决定可分散的桶数
size	已存元素个数	触发扩容判断
load factor	`size / capacity`	衡量拥挤程度
threshold	`capacity * loadFactor`	超过后扩容

capacity=16, loadFactor=0.75
threshold = 16 * 0.75 = 12
插入第 13 个元素时通常触发扩容

记忆钩子：负载因子是在空间和时间之间调旋钮。太高省空间但冲突多，太低冲突少但浪费桶数组。

数字例子：容量 16、负载因子 0.75 时阈值是 12；扩容到 32 后阈值变成 24。如果插入 100 万个元素却初始容量很小，会经历多次扩容和 rehash；如果能估算规模，预设合理初始容量可以减少扩容成本。

误区：负载因子越小越好。 过小会让桶数组很大，浪费内存并影响缓存效率。
误区：扩容只是数组变长，不需要处理元素。 元素下标依赖容量，容量变了需要重新分布或迁移。
误区：0.75 是数学最优常数。 它是工程折中，兼顾空间占用和冲突概率，不是所有场景的绝对最优。
追问：为什么扩容代价高？ 需要分配新数组，并把旧元素迁移到新桶位置，单次可能 O(n)。
追问：什么时候需要预设初始容量？ 已知即将放入大量元素时，预设容量能减少多次扩容。
追问：并发扩容有什么风险？ 非线程安全 HashMap 并发写可能破坏结构，应该用并发容器或外部同步。

七、加强记忆

负载因子 = 元素数 / 桶数，是哈希表的拥挤度；越大越挤越慢，越小越浪费。超过阈值（HashMap 默认 0.75）就扩容翻倍并 rehash——容量变了下标就得重算，把扎堆元素重新散开，恢复 O(1)。扩容单次 O(n) 但均摊 O(1)，已知规模应预设初始容量。并发扩容有坑，多线程用 ConcurrentHashMap。

简化版

详细版