9.3 哈希查找
9.3.1 什么是哈希表
– 查找效率由比较一次缩小的查找范围决定。
•顺序查找是对无序集的查找，关键字比较的结果为“=”
或“≠”两种可能，其平均时间为O（n）。
•而二分法查找和各种树表的查找是对有序集的查找，关
键字比较的结果为“>”、“=”、“<”三种可能，其查找
速度较快，平均时间为O（log
2
n）。
– 要想提高查找的效率，就不能只是依赖于比较进行查找。
理想的情况是依据关键字直接得到其对应的数据元素位置
，即要求关键字与数据元素间存在一一对应关系，通过这
个关系，能很快地由关键字得到对应的数据元素位置，其
查找的时间期望值为O（1）。
