哈希表负载因子与扩容机制

描述：
负载因子是哈希表中一个关键的性能参数，定义为当前元素个数与哈希表总槽位数的比值（即 负载因子 = 元素数量 / 哈希表大小）。它衡量了哈希表的“填满程度”。当负载因子过高时，哈希冲突的概率会显著增加，导致查找、插入等操作的时间复杂度退化（最坏情况下从 O(1) 升至 O(n)）。因此，当负载因子超过某个预设阈值时，哈希表会触发扩容（Rehashing）操作，即创建一个更大的新数组，并将所有现有键值对重新哈希到新数组中，从而降低负载因子，维持操作的高效性。

解题过程：

1. 理解负载因子的作用

   • 负载因子直接影响哈希表的空间利用率与时间效率的权衡。
   • 若负载因子过低（如 0.1），说明哈希表空闲槽位多，空间浪费严重，但冲突概率低，操作速度快。
   • 若负载因子过高（如 0.9），空间利用率高，但冲突频繁，链表（或冲突解决结构）变长，性能下降。
   • 因此需设定一个合理的阈值（如 Java HashMap 默认 0.75），在空间和效率间取得平衡。

2. 扩容触发条件

   • 假设当前哈希表大小为 capacity，已存储元素数量为 size，负载因子阈值为 loadFactorThreshold（例如 0.75）。
   • 当插入新元素后满足 size / capacity > loadFactorThreshold 时，触发扩容。
   • 例如：表大小为 10，阈值 0.75，当插入第 8 个元素时（8/10 = 0.8 > 0.75），需扩容。

3. 扩容具体步骤

   • 分配新数组：新大小通常为原大小的 2 倍（或其他质数，目的是减少哈希值聚集）。例如原表大小为 10，新表大小为 20。
   • 重新哈希（Rehash）：遍历原哈希表的每个槽位，对每个键值对执行以下操作：
     1. 使用哈希函数重新计算键在新大小下的槽位索引（newIndex = hash(key) % newCapacity）。
     2. 将键值对插入新数组的对应位置（冲突解决策略不变，如链地址法仍挂载到链表）。
   • 释放原数组：所有元素迁移完成后，原数组被回收，哈希表实例改为引用新数组。

4. 扩容的性能分析

   • 扩容操作的时间复杂度为 O(n)，因为需遍历所有元素。
   • 但由于扩容不是频繁发生，均摊分析（Amortized Analysis）下，插入操作的平均时间复杂度仍为 O(1)。
   • 优化策略：可在扩容时预留空间，避免在临界点频繁插入删除导致反复扩容。

5. 示例说明

   • 初始：表大小 4，阈值 0.75，当前元素数 0。
   • 插入 3 个元素后，负载因子 = 3/4 = 0.75，不扩容。
   • 插入第 4 个元素前检查：4/4 = 1.0 > 0.75，触发扩容。
   • 新表大小变为 8，将原 3 个元素重新哈希到新表，再插入第 4 个元素。
   • 此时负载因子降为 4/8 = 0.5，性能恢复。

通过以上步骤，哈希表能在负载因子过高时自动调整规模，保证操作的高效性。