第七章 查找 十、散列查找

一、哈希表（散列表）

哈希表的数据元素的关键字与其存储地址直接相关。

二、解决冲突的方法

三、散列表中元素的查找

总共对比了3个关键字，所以查找长度为3.

四、查找效率计算

（1）成功的概率

需要对比一次的关键字为6个；

需要对比两次的关键字为4个；

需要对比三次的关键字为1个；

需要对比四次的关键字为1个；

关键字总数为12个；

把它们加起来除以总数12，得到ASL；

（2）失败的概率

失败的情况一共有13种；

第一个关键字失败时，需要比较0次；

第二个关键字失败时，需要比较4次；

第三个关键字失败时，需要比较0次；

第四个关键字失败时，需要比较2次；

第五个关键字失败时，需要比较0次；

第六个关键字失败时，需要比较0次；

第七个关键字失败时，需要比较2次；

第八个关键字失败时，需要比较1次；

第九个关键字失败时，需要比较0次；

第十个关键字失败时，需要比较0次；

第十一个关键字失败时，需要比较2次；

第十二个关键字失败时，需要比较1次；

第十三个关键字失败时，需要比较0次；

把它们加起来除以总数13，得到ASL；

五、如何设计哈希函数让冲突减少

（1）除留余数法

（2）直接定址法

（3）数字分析法

六、处理冲突的方法

1、线性探测法

当发生冲突时，依次向后检测空的地址，当检测到地址为空，则将其放入该地址。

注意：对比了几次，查找长度就是几次。

2、平方探测法

3、伪随机序列法

4、总结