数据结构--散列函数的构造方法

一、概述散列哈希函数的作用将任意整数型 / 字符型关键字通过固定运算压缩映射为 0表长 - 1 范围内的散列地址。构造原则必背计算简单、速度快地址分布均匀尽量减少哈希冲突能够覆盖整个散列表空间。常用五种标准构造方法直接定址法、除留余数法、数字分析法、平方取中法、折叠法。二、直接定址法1. 公式H(key)key或H(key)a×keyb、为常数做线性映射。2. 原理直接利用关键字本身或经过简单线性变换作为散列地址一一对应。3. 特点优点无哈希冲突计算最简单缺点关键字必须连续、分布集中若关键字跨度大会造成散列表空间大量浪费。4. 适用场景关键字取值连续、范围狭小、分布规律明确的场景。三、数字分析法1. 原理针对位数固定的数字关键字分析每一位数字的分布规律剔除重复多、分布集中的无效位选取数字随机、分散性强的若干位组合作为散列地址。2. 举例一组学号20260311、20260315、20260320前几位固定重复中间段集中取末尾两位作为地址分布更均匀。3. 特点优点地址均匀冲突少缺点必须预先掌握全部关键字的数字规律无法通用。4. 适用场景关键字位数固定、样本已知、批量静态数据。四、平方取中法1. 原理对关键字整体进行平方运算平方后数值会打乱原有数字规律截取平方结果中间若干位作为散列地址。2. 核心优势关键字首尾数字容易集中重复中间位随机性最强映射更均匀有效降低冲突。3. 特点优点无需分析关键字规律通用性强分散效果好缺点大数平方运算稍复杂计算开销略大。4. 适用场景关键字分布无规律、无法提前分析数位的情况。五、折叠法1. 原理将关键字按固定长度分割成若干段对所有分段数值进行叠加求和再取后几位作为散列地址。分为两种移位叠加分段直接相加边界叠加相邻段反向翻转后再相加进一步打乱规律。2. 举例关键字5689427按 3 位分割568 | 942 | 7分段求和取低位作为存储地址。3. 特点优点适合关键字位数多、数值范围大的数据缺点分割规则需要人为设定随机度一般。4. 适用场景超长数字关键字、大数值编号类数据。六、除留余数法1. 公式H(key)key Mod pp 为选取的模数。2. 选取规则必考设散列表表长为 m要求pmp 优先选取质数避免选取含有大量公因数的合数如偶数、5 的倍数防止地址聚集。3. 原理利用取模运算将大范围关键字压缩到 0∼p−1区间运算简单、映射稳定。4. 特点优点计算极简、实现容易、通用性最强、适配所有类型关键字缺点若 p 选取不当会出现地址集中、冲突增多。5. 适用场景绝大多数散列表的默认构造方法笔试、代码、工程全部通用。七、五种方法整体对比总结直接定址法无冲突仅限连续关键字数字分析法靠数位筛选适合已知固定样本平方取中法平方乱序中间取值分散性好折叠法分段叠加适合长关键字除留余数法万能通用考试核心、首选方法。