四、性能分析

4.1 时间复杂度

操作	平均情况	最坏情况 (全冲突)
插入	$O(1)$	$O(n)$
删除	$O(1)$	$O(n)$
查找	$O(1)$	$O(n)$

4.2 装载因子 (Load Factor)

衡量哈希表“满”的程度。

$$ \alpha = \frac{\text{填入表中的元素个数}}{\text{哈希表的长度}} $$

• $\alpha$ 越大：冲突概率越大，查找越慢，空间利用率高。
• $\alpha$ 越小：冲突概率越小，查找快，但浪费空间。

4.3 扩容 (Rehashing)

当装载因子超过某个阈值（如 Java HashMap 默认为 0.75）时，需要扩容。

1. 申请一个2倍大小的新数组。
2. 重新计算所有旧数据的哈希值，放入新数组（因为 % Size 变了，位置也会变）。
3. 这个过程非常耗时 ($O(n)$)。

---