哈希表的动态扩容与负载因子 描述 哈希表（Hash Table）是一种通过哈希函数将键映射到数组索引以实现高效查找的数据结构。然而，当插入的元素过多时，哈希冲突概率会增加，导致性能下降。动态扩容是哈希表在元素数量达到阈值时自动扩大容量（通常加倍）并重新分配所有元素的过程。负载因子（Load Factor）是触发扩容的关键参数，定义为元素数量与桶数组大小的比值。例如，Java的HashMap默认负载因子为0.75，当元素数量超过容量×0.75时触发扩容。 关键问题 为什么需要动态扩容？ 负载因子如何影响性能？ 扩容的具体步骤是什么？ 如何保证扩容过程的高效性？ 逐步讲解 1. 哈希表的基本结构 哈希表由一个桶数组（每个桶可能存储一个链表或红黑树以解决冲突）和哈希函数组成。 插入元素时，先计算键的哈希值，再通过取模运算得到索引： index = hash(key) % capacity 。 若多个键映射到同一索引（哈希冲突），则通过链地址法或开放定址法处理。 2. 负载因子的作用 负载因子λ = 元素数量 / 桶数组大小。 λ越小，冲突概率越低，但空间浪费越大；λ越大，空间利用率高，但冲突增加，查找效率下降（理想情况下，链地址法的平均查找时间为O(1+λ)）。 经验表明，λ=0.75时在时间与空间成本间取得平衡。若λ超过阈值，需扩容以减少冲突。 3. 触发扩容的条件 设当前容量为 capacity ，元素数量为 size ，负载因子阈值为 loadFactor （如0.75）。 当 size > capacity * loadFactor 时，触发扩容。例如，容量为16的哈希表，当插入第13个元素（16×0.75=12）时扩容。 4. 扩容步骤 步骤1：创建新桶数组 新容量通常为原容量的2倍（保证容量仍为2的幂，便于取模运算优化为位运算）。 例如，原容量16扩容为32，新建一个大小为32的桶数组。 步骤2：重新哈希所有元素 遍历原桶数组中的每个桶（链表或树），对每个元素重新计算哈希值和新索引： new_index = hash(key) % new_capacity 。 由于容量变化，同一链表中的元素可能被分配到新数组的不同位置。 例如，原索引为 hash(key) % 16 ，新索引为 hash(key) % 32 ，元素可能分散到新桶中。 步骤3：迁移元素至新数组 将重新哈希后的元素插入新桶数组。若使用链地址法，直接构建新链表或树。 完成后，原数组被垃圾回收（如Java）或释放（如C++）。 5. 扩容的性能优化 分摊时间复杂度 ：单次插入最坏情况为O(n)（需迁移n个元素），但分摊到多次插入后，平均时间复杂度仍为O(1)。 增量式扩容 ：某些实现（如Redis的哈希表）采用渐进式扩容，在扩容期间同时维护新旧两个数组，分多次迁移元素，避免单次操作停顿过长。 6. 示例演示 假设哈希表初始容量为4，负载因子0.75，链地址法解决冲突。 插入键a、b、c：当插入第3个元素（4×0.75=3）时，触发扩容。 扩容至容量8，重新计算a、b、c的索引（如原a在索引1，新索引可能为5）。 后续插入d、e时，直接插入新数组。 总结 动态扩容是哈希表保持高效性的核心机制，通过负载因子控制空间与时间的权衡。理解扩容过程有助于优化哈希表的使用（如预设容量避免频繁扩容）。实际应用中，需根据场景调整负载因子和初始容量。