8.1. 闭散列分析¶

散列的效率如何？ 我们可以用执行一次操作所需的 记录访问次数来衡量散列的性能。 主要关注的操作是插入、删除和查找。 区分成功查找和不成功查找是很有用的。 在删除一条记录之前，必须先找到它。 因此，删除一条记录所需的访问次数 等同于成功查找该记录所需的次数。 要插入一条记录，必须找到该记录探测 序列上的一个空槽位。 这等同于对该记录进行 一次不成功的查找 （回想一下，插入期间对该记录的成功查找 应当产生错误，因为不允许把两条具有相同键的 记录存储在表中）。

当散列表为空时，插入的第一条记录总是 会发现其起始位置是空闲的。 因此，只需一次记录访问就能找到空闲槽位。 如果所有记录都存储在其起始位置，那么成功 查找也只需一次记录访问。 随着表开始被填满，一条记录能够 插入其起始位置的概率会降低。 如果一条记录散列到一个已被占用的槽位，那么冲突解决 策略必须找到另一个槽位来存储它。 查找未存储在起始位置的记录也需要 额外的记录访问，因为要沿着该记录的探测 序列去查找它。 随着表被填满，越来越多的记录可能 离其起始位置越来越远。

从这段讨论可以看出，散列的期望代价是 表有多满的一个函数。 把表的 装填因子 定义为 \(\alpha = N/M\) ， 其中 \(N\) 是当前在表中的记录数。

在假设探测序列遵循散列表中槽位的 随机排列的情况下，我们可以解析地 推导出插入（或不成功查找）期望代价的估计值，它是 \(\alpha\) 的函数。 假设表中每个槽位成为下一条记录 起始槽位的概率相等， 那么发现起始位置已被占用的概率就是 \(\alpha\) 。 同时发现起始位置和探测序列上 下一个槽位都已被占用的概率是 \((N(N-1))/(M(M-1))\) 。 出现 \(i\) 次冲突的概率是 \((N(N-1) ... (N-i+1))/(M(M-1) ... (M-i+1))\) 。 如果 \(N\) 和 \(M\) 都很大， 那么它约等于 \((N/M)^i\) 。 期望探测次数等于 1 加上对 \(i >= 1\) 时出现 \(i\) 次冲突的概率求和， 其结果约为

成功查找（或删除）的代价与最初插入该记录 时的代价相同。 然而，插入代价的期望值取决于 \(\alpha\) 的取值， 不是删除时的取值，而是最初插入时的取值。 我们可以通过从 0 积分到 \(\alpha\) 的当前值 来推导出这一代价的估计值（本质上是所有 插入代价的平均），结果为 \((1/\alpha) \log_e 1/(1-\alpha).\)

重要的是要认识到，这些公式表示的是 在不切实际地假设探测序列基于散列表中槽位的 随机排列时，操作的期望 代价。 这样我们就避免了由不完美的 冲突解决策略带来的全部额外开销。 因此，这些代价是平均情况下的下界估计。 线性探测下真正的平均代价是 插入或不成功查找为 \(.5(1 + 1/(1-\alpha)^2)\) ， 删除或成功查找为 \(.5(1 + 1/(1-\alpha))\) 。

图 10.8.1 展示了随着 \(\alpha\) 增大，期望的记录访问次数如何增长。 横轴是 \(\alpha\) 的取值，纵轴 是访问散列表的期望次数。 实线表示"随机"探测的代价（理论下界）， 而虚线表示线性探测的代价 （一种相对较差的冲突解决策略）。 最左边的两条线表示插入的代价 （等价于不成功查找）； 最右边的两条线表示删除的代价 （等价于成功查找）。

从图中可以看出，当表不太满时，散列的代价 通常接近一次记录访问。 这是极其高效的，远优于 需要 \(\log n\) 次记录访问的二分查找。 随着 \(\alpha\) 增大，期望代价也随之增大。 对于较小的 \(\alpha\) 值，期望代价较低。 在散列表大约半满之前，它一直低于 2。 当表几乎为空时，向表中添加一条新记录 不会使未来查找操作的代价增加太多。 然而，一旦表变得半满，每次额外 插入所引起的额外查找代价就会迅速增加。 基于这一分析，经验法则是设计散列 系统时让散列表永远不要超过大约 半满，因为超过这一点后性能会迅速下降。 这就要求实现者大致了解在最大装载时 表中可能有多少条记录，并据此 选择表长。 目标应当是：一方面让表足够小，以免 浪费大量空间；另一方面又让它足够大， 以保持良好性能。