7.5.4 散列性能分析

性能由函数、冲突策略、装填因子和键分布共同决定。线性探测随alpha接近1，成功与失败探测次数急剧增大；拉链法平均链长约alpha，但分布不均会出现长链。

手工推演

m=10存8项，alpha=.8；再插一项变.9，空槽更少，失败查找往往需走更长簇。扩容到23后alpha约.39，需用新模数重散列全部键。

结构与代码

扩容不能只复制原数组位置，因为h依赖表长。统计ASL时按每个成功键实际探测次数求均值；失败ASL按各初始地址的失败探测长度求均值。

正确性

重散列保持键集合不变但重建每键合法位置；降低alpha缩短期望冲突链。

错解反馈

ASL只看alpha而忽略分布；扩容原位复制；成功与失败探测次数混在一个分母。

迁移训练

为何开放定址表不能等到完全满再扩容？答案失败查找趋近扫描全表，插入可能无空槽。