几个重要概念 散列技术的两个重要问题 负载因子a=n/ 散列表的空间大小为m 用散列技术时需要考虑的两个首 填入表中的结点数为 要问题是: 冲突 )如何构造选择)使结点“分布均 某个散列函数对于不相等的关健码计算出了相同的 匀”的散列函数? 在实际应用中,不产生冲突的散列函数极少存在 (2)一旦发生冲突,用什么方法来解 同义词 决 发生冲突的两个关健 还需考虑散列表本身的组织方法 叔新有,盘 张 9.3.1散列函数 散列函数的选取原则 散列函数:把关键码值映射到 ■运算尽可能简单 存储位置的函数,通常用h来表 ■函数的值域必须在表长的范围内 ■尽可能使得关键码不同时,其散列 Address Hash( key 函数值亦不相同 订恤 张铭趣 张帖 需要考虑各种因素 常用散列函数选取方法 关键码长度 令1.除余法 散列表大小 令2.乘余取整法 关键码分布情况 令3.平方取中法 记录的检索频率 Q4.数字分析法 5.基数转换法 6.折叠法 Q7. ELFhash字符串散列函数 权新有,种8 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 43 几个重要概念 „ 负载因子α=n/m „ 散列表的空间大小为m „ 填入表中的结点数为n „ 冲突 „ 某个散列函数对于不相等的关键码计算出了相同的 散列地址 „ 在实际应用中，不产生冲突的散列函数极少存在 „ 同义词 „ 发生冲突的两个关键码 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 44 散列技术的两个重要问题 „ 采用散列技术时需要考虑的两个首 要问题是： „ （1）如何构造(选择)使结点“分布均 匀”的散列函数？ „ （2）一旦发生冲突，用什么方法来解 决？ „ 还需考虑散列表本身的组织方法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 45 9.3.1 散列函数 „ 散列函数：把关键码值映射到 存储位置的函数，通常用h来表 示 Address ＝ Hash ( key ) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 46 散列函数的选取原则 „ 运算尽可能简单 „ 函数的值域必须在表长的范围内 „ 尽可能使得关键码不同时，其散列 函数值亦不相同 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 47 需要考虑各种因素 „ 关键码长度 „ 散列表大小 „ 关键码分布情况 „ 记录的检索频率 „ … 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 48 常用散列函数选取方法 „ 1. 除余法 „ 2. 乘余取整法 „ 3. 平方取中法 „ 4. 数字分析法 „ 5. 基数转换法 „ 6. 折叠法 „ 7. ELFhash字符串散列函数