7.5.1 散列表概念

散列用h(key)直接映射桶。不同键映射同址叫冲突，无法靠“好函数”完全消除。装填因子alpha=记录数/桶数影响性能。目标是分布均匀、计算快，并配合冲突处理。

手工推演

表长7，h(k)=k mod7，键10、17、24都映射3，形成冲突簇。查找必须沿规定冲突路径直到命中或满足失败条件。

结构与代码

散列表通常不保持关键字顺序，因此范围查询不擅长。平均可接近O(1)，最坏冲突集中时O(n)。

正确性

查找使用与插入完全相同的探测/链规则，才能保证已插入键可被找到。

错解反馈

认为无冲突；把平均O(1)写成最坏；查找与插入使用不同表长或函数。

迁移训练

表长10存7项，装填因子多少？答案0.7。