hash查找.ppt

决定哈希表查找的ASL的因素： （1）选用的哈希函数; （2）选用的处理冲突的方法; （3）哈希表饱和的程度，装载因子α=n/m 值的大小。 一般情况下，可以认为选用的哈希函数 是“均匀”的，则在讨论ASL时，可以不考虑它 的因素。 线性探测再散列 随机探测再散列 链地址法 8.3.5 hash表的查找分析 装填（负载）因子 α= 表中填入的记录数 hash表的长度 8.3 hash(散列)查找 前述的查找方法建立在 “比较” 的基础上，查找的次数依赖于查找过程中进行比较的次数。 问题：能否不用比较就能直接计算出记录的存储地址，从而找到所要的结点？ 解决方法：采用散列方法。 8.3.1 hash函数和hash表 一、hash表 根据设定的散列函数和相应解决冲突的方法为一组结点建立的一张表，表中的结点的存储位置依赖于设定的散列函数和处理冲突的方法。 二、基本思想： 以结点的关键值k为自变量，通过一定的函数关系 h 计算出对应的函数值 h(k), 把这个值解释为结点的存储地址（散列地址）， 将结点存入该地址中去。 设计1个hash函数，计算 Hash函数， 其函数值恰好 是 key 在 hash 表中的地址 hash(key)=i (0..m-1) 地址 key info 0 1 2 3 i key m-1 例8-1：hash查找示例。 人口统计表。 在右表中查找 1982年出生的人数。 查找方法（1）：顺序查找 查找方法（2）：二分查找 查找方法（3）：hash 查找 hash(key)=key-1949 =1982-1949 =33 地址 年份 人数 0 1949 -------- 1 1950 -------- 2 1951 -------- 3 1952 -------- 40 。。。 1989 。。。 59 2008 ------ 三、冲突的概念 若对于不同的键值k1和k2,且k1 ≠ k2,但 hash(k1)=hash(k2)， 即具有相同的散列地址，这种现象称为冲突。 称 k1、k2称为同义词。 例：key={3,15,20,24}，m=5（表长）， hash(k)=k%5 hash(15)=0 hash(20)=0 产生冲突。 四、表长m的选取 参考：n / m≈ 3 / 4 m: hash表的表长， n: hash表中关键字个数。 五、要解决的问题 （1）如何选择一个好的散列函数 （ 能将关键值均匀地分布在整个地址空间，使冲突机会尽量的少 ） （2）如何选定一个解决冲突的办法。 8.3.2 hash函数的构造方法 （1）直接定址法 哈希函数为关键字的线性函数。 hash(key) = key 或者 hash(key) = a ? key + b 如例8-1所示， hash(key)=key-1949 （2）数字分析法 假设关键字集合中的每个关键字都是由s位 数字组成(k1, k2, …, kn)，分析关键字集中的全 体，并从中提取分布均匀的若干位或它们的组合 作为地址。 参见教材 P278 仅限于：能预先估计出全体关键字的每一位 上各种数字出现的频度。 （3）平方取中法 若关键字的每一位都有某些数字重复出现频度 很高的现象，则先求关键字的平方值，以通过“平方” 扩大差别，同时平方值的中间几位受到整个关键字中 各位的影响。 例如：a=0100, 则 a2=0010000 i =1100, 则 i2 =1210000 j =1200, 则 j2 =1440000 若超出范围