20230410 11.4. 散列表的性能分析

• 平均查找长度（ASL）用来度量散列表查找效率：成功、不成功
• 关键词的比较次数，取决于产生冲突的多少
• 影响产生冲突多少有以下三个因素：
  • 散列函数是否均匀；
  • 处理冲突的方法；
  • 散列表的装填因子α

开放地址法：

• 散列表是一个数组，存储效率高，随机查找。
• 散列表有“聚集”现象

分离链法：

• 散列表是顺序存储和链式存储的结合，链表部分的存储效率和查找效率都比较低。
• 关键字删除不需要“懒惰删除”法，从而没有存储“垃圾”。
• 太小的α可能导致空间浪费，大的α又将付出更多的时间代价。不均匀的链表长度导致时间效率的严重下降。