5.4 哈希(Hash)表

　　以上讲的查找方法基于比较的,查找效率依赖比较次数,其实理想的查找希望不经比较,一次存取便能得到所查记录,那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,这样查找k时,只要根据这个对应关系f找到给定值k的像f(k)。这种对应关系f叫哈希（hash）函数。按这种思想建立的表叫哈希表（也叫散列表）。哈希表存取方便但存储时容易冲突（collision）：即不同的关键字可以对应同一哈希地址。如何确定哈希函数和解决冲突是关键。

　　1.哈希函数的构造方法

　　直接定址法:H(k)=k 或H(k)=a*k+b(线形函数)

　　如:人口数字统计表

　　地址 1 2 3 ... 100

　　年龄 1 2 3 ... 100

　　人数 67  3533 244 ... 4

　　当给定值k=84,则首先和a[6]比在依次和a[7],a[8]比结果a[8]=84查找成功。

　　当给定值k=38,则首先和a[12]比,再和a[13]比,由于a[13]没有,查找不成功,表中不存在关键字等于38的记录。