【数据结构笔记41】散列表/哈希表的性能分享
本次笔记内容：
11.4 散列表的性能分析
平均查找长度
平均查找长度（ASL）用来度量散列表查找效率：成功、不成功两种指标。
关键词的比较次数，取决于产生冲突的多少。
影响冲突产生的三个因素
（1）散列函数是否均匀；
（2）处理冲突的方法；
（3）散列表的装填因子α。
不同方法的性能
线性探测法查找性能
线性探测查找性能期望公式如上。
平方探测法和双散列探测法的查找性能
平方探测法和双散列探测法的查找性能性能如上。
期望探测次数与装填因子α的关系
如上图，合理的最大装载因子α应该不超过0.85。
分离链接法的查找性能
如上图，分离链接法的装载因子有可能超过1。
总结
如上图，散列法与关键字空间大小n无关，适于关键字直接比较的计算量大的问题；但散列法是一个以空间换时间的方法，并且不适于范围查找。
开发地址法：
- 是一个数组，存储效率高，随机查找；
- 但是有“聚集”现象。
分离链接法：
- 组合运用顺序存储和链式存储，链表部分的存储效率和查找效率都比较低；
- 关键字删除不需要“懒惰删除法”；
- 装载因子大时，效率可能会较低。