怎样建立微网站,中国住房和城乡建设部网站证书查询,有哪些做兼职的设计网站有哪些工作,韵博工业设计哈希函数的概念#xff1a;哈希函数是哈希表#xff08;散列表#xff09;的核心组件#xff0c;其作用是将任意长度的键#xff08;Key#xff09;映射为固定长度的存储地址#xff0c;以实现高效的数据存储与检索。以下是哈希函数在数据结构中的关键知识点总结#x…哈希函数的概念哈希函数是哈希表散列表的核心组件其作用是将任意长度的键Key映射为固定长度的存储地址以实现高效的数据存储与检索。以下是哈希函数在数据结构中的关键知识点总结
一、哈希函数的核心作用
快速定位数据 通过哈希函数计算键的哈希值直接定位到数组中的存储位置使得插入、删除和查找操作的平均时间复杂度为 O(1。冲突管理 不同键可能映射到相同地址哈希冲突哈希函数的设计需尽可能减少冲突概率并通过冲突解决策略处理实际冲突。
二、常见哈希函数构造方法
直接定址法 公式H(key) a*key b特点适用于键分布连续的场景如年龄存储无冲突但空间利用率低。示例年龄为键时直接以年龄作为数组下标。 除留余数法 公式H(key) key % pp为不大于表长的质数特点简单高效需选择合适质数以减少冲突。示例当表长m10选择p7键12的哈希值为12%75。 平方取中法 步骤对关键字平方后取中间几位作为哈希值。适用场景关键字分布范围大且中间位数较均匀。 折叠法 方法将关键字分割为多段后叠加求和如移位叠加或间界叠加。适用场景长关键字且位数分布均匀。 随机数法 公式H(key) random(key)特点适用于非数值型键需保证随机性以减少冲突。 三、哈希冲突的解决方案
一、开放地址法Open Addressing
核心思想当发生冲突时按规则探测哈希表中的下一个空槽位。 探测方式
线性探测按顺序向后逐个查找空位。 公式H_i (H(key) d_i) % m其中 d_i 1, 2, 3, ..., m-1示例 哈希表长度 m11哈希函数 H(key)key%11。 插入序列 {12, 67, 56, 16, 25, 37} 时37%111但位置1已被25占用。 线性探测后依次检查位置2空插入37到位置2。 二次探测按平方增量跳跃式探测。 公式d_i ±1², ±2², ..., ±k²示例 若 H(key)3 冲突探测顺序为 31²4 → 3-1²2若2为空则插入。 伪随机探测通过伪随机数生成增量序列。 示例 若哈希表长度 m11随机序列为 2,5,9,...冲突时计算 (32)%115若仍冲突则继续 (35)%118。
二、链地址法Separate Chaining
核心思想将哈希地址相同的元素组成链表头指针存储在哈希表中。 示例 哈希表长度13哈希函数 H(key)key%13关键字序列 {32,40,36,53,16,46,71,27,42,24,49,64}。
处理结果 地址0→32→27地址1→40→53→16→42地址10→49→64 平均查找长度 (7*1 4*2 1*3)/12 ≈1.5。
三、再哈希法Double Hashing
核心思想冲突时使用第二个哈希函数重新计算地址。 示例
主哈希函数 H1(key)key%13冲突时使用 H2(key)7-(key%7)。 插入 key37 时若 H1(37)11 冲突则计算 H2(37)7-25新地址 (115)%133若空则插入。 四、公共溢出区法Overflow Area
核心思想单独开辟一个区域存储冲突元素。 示例 哈希表分为主表 HashTable[0..m-1] 和溢出表 OverTable[0..v]。
查找时先查主表未找到则遍历溢出区。
五.方法对比
方法优点缺点开放地址法空间紧凑无需额外结构易产生聚集删除复杂链地址法无聚集支持动态插入/删除需额外存储指针空间开销大再哈希法冲突概率低计算时间增加公共溢出区法实现简单适合冲突较少场景溢出区过大时效率下降
