四、散列检索效率分析

我们可以根据完成一次操作，即插入、删除和检索操作，所需要的记录访问次数来衡量散列方法的性能。由于散列表的插入和删除操作都是基于检索进行的：在删除一条记录之前必须先找到该记录，因此删除一条记录之前需要的访问数等于成功检索到它需要的访问数；而插入一条记录时，必须找到探查序列的尾部（对于不考虑删除的情况，是尾部的空槽；对于考虑删除的情况，也要找到尾部，才能确定是否有重复记录），这等于对这条记录进行一次不成功的检索。因此，散列表的效率实质上还是平均检索长度，而且我们需要区别对待成功的检索与不成功的检索。
    当散列表比较空的时候，所插入的记录比较容易插入到其空闲的基地址。如果散列表中的记录比较多，插入记录时，很可能要靠冲突解决策略来寻找探查序列中合适的另一个槽。而且，检索记录时，很多时候需要沿着探查序列逐个查找。随着散列表记录不断增加，越来越多的记录有可能放到离其基地址更远的地方。
    根据这些讨论，我们可以看到散列方法预期的代价与负载因子α= N/M有关。其中，M是散列表存储空间大小，N是表中当前的记录数目。
    从图9-8可以看出，开散列方法的效率最好，实际系统中使用的散列大多都是开散列。开散列方法非常简单、易于实现，它不会产生聚集现象（聚集导致更大的平均检索长度），删除也极为方便。大部分数据结构教材用比较多的篇幅来讨论闭散列方法，是因为闭散列需要考虑的因素更多，因而更需要精心设计，闭散列在某些受限制的系统中（例如不能使用堆栈分配新空间）有独到的用途。并且，经过精心设计的闭散列的效率比开散列稳定。