本节总结

本节重点讲述了散列检索方法，主要介绍了几种散列函数，针对冲突问题，介绍了开散列和闭散列两种解决方法，最后分析了散列检索的效率问题。散列法的平均检索长度不随表目数量的增加而增加，而是随负载因子的增大而增加。如果安排得好，平均检索长度可以小于1.5。正是由于这个特性，散列法成为一种很受欢迎的高效检索方法。例如，搜索引擎中关键词字典、域名服务器DNS中域名与IP地址的对应（例如，db.pku.edu.cn与162.105.203.98，www.google.com与216.239.53.99）、操作系统中命令路径下的所有可执行程序名、编译系统中的符号表等，都采用了散列技术以提高查找速度。