Hashing散列速记模板一、核心目标Hashing 用函数 f(x) 直接定位位置实现平均 O(1) 查找/插入/删除。二、四拍理解必须背① 定义symbol table key → value② 冲突不同key映射到同一位置③ 解决链表 or open addressing④ 验证平均 O(1)依赖装填因子 α三、Hash函数设计1. 基本原则✔ 计算快✔ 分布均匀✔ 减少周期性冲突2. 常见函数整数h(x)x mod TableSizeTableSize最好取素数字符串h(x)Σ(x[i]·32^i) mod M用5代替×32四、冲突解决两大类1. Separate Chaining拉链法思想 同一桶挂链表装填因子 α N / M性质✔ α可以 1✔ 平均查找 O(1α)✔α≈1最优2. Open Addressing开放定址思想冲突就往表内找空位 h_i(x) (h(x)f(i)) mod M三种方式线性探测f(i)i易聚集平方探测f(i)i²缓解聚集双散列f(i)i·h2(x)最好关键问题✔ 装填因子必须 0.5否则性能急剧下降✔ 删除要 lazy delete标记删除五、重要现象1. 一次聚集primary clustering线性探测导致连续占用 → 越来越长 → 更容易冲突2. 二次聚集secondary clustering平方探测相同hash值 → 探测序列相同六、平方探测核心定理半满定理当TableSize为素数α 0.5则✔ 一定可以找到空位证明核心平方探测前 n/2 个位置不重复 → 不会卡死七、复杂度总结Separate Chaining平均 O(1α)Open Addressing成功查找 O(1/(1−α))不成功查找更慢八、真题讲解collision定义不同key → 同一hash值2.【2015-2016 1-6】insert vs find复杂度 ✔ 相同平均原因都依赖冲突链长度错误点通常是❌ “α0.5仍保证成功”❌ “double hashingquadratic probing”❌ “插入复杂度固定O(1)”6.【R2-12】unsuccessful search probe length线性探测下平均失败查找 ≈ 1/(1−α)7.【2023-2024 T/F】表size8仍能失败✔ True原因平方探测可能无法覆盖所有位置非素数9.【double hashing平均查找】核心比linear probing更均匀 → 更接近O(1)10.【R2-13】线性探测最小probe次数所有key同hash→ 123...n n(n1)/2九、考试最重要总结⭐ 一、三句话核心✔ Hashing O(1)均摊✔ 冲突 unavoidable✔ 解决 chaining / probing⭐ 二、装填因子方法αchaining可 1open addressing必须 0.5⭐ 三、探测方式线性 → 聚集严重平方 → 改善但有限双散列 → 最优⭐ 四、必考公式成功查找1/(1−α)失败查找1/(1−α)²⭐ 五、一句话总结Hashing 用函数直接定位 冲突用结构或探测解决使平均复杂度保持 O(1)。再散列Rehashing Robin Hood Hashing 速记当开放定址哈希表过满或性能下降时重新建一个更大的表通常约2倍取素数把所有合法元素重新插入。二、复杂度单次ON均摊后 O(1)三、触发条件超级重点✔ 插入失败✔ 装填因子 α ≥ 0.5开放定址✔ 性能明显下降四、关键规则✔ 新表必须取素数✔ 删除元素不搬lazy delete只跳过✔ 所有元素重新hash不是搬位置五、为什么要再散列因为开放定址α越大 → probe越长最坏 → 插入失败六、Rehashing本质总结通过扩大表长降低装填因子 α使探测序列恢复O(1)平均性能七、真题讲解Rehashing1.【2020-2021 R2-16】何时必须rehash✔ insertion fails → 必须❌ half full → 不一定必须❌clustering 聚类→ 不能直接触发❌ hash不均匀 → 不属于必要条件✔ 必须表过满插入失败❌ 不必须冲突模式变化clustering出现八、Robin Hood Hashing重点选讲核心思想线性探测改进“走得远的人优先”定义探测距离d(x) 实际位置 − hash位置核心规则当新元素进入✔ 如果新元素探测距离 当前元素→ 交换劫富济贫一句话解释把“走得太远的人”拉回去让“更惨的继续往前”九、Robin Hood特点✔ 优点降低方差查找更稳定worst-case更可控❌ 缺点插入更慢删除复杂需要记录探测距离✔ 复杂度平均O(1)最坏查找O(log N)比线性更稳定十、考试最重要对比方法插入查找特点Linear probingO(1)均摊O(1)均摊一次聚集严重Quadratic probingO(1)均摊O(1)均摊改善聚集Double hashingO(1)O(1)最均匀Robin Hood稍慢更稳定降低方差⭐ 三、Robin Hood一句话用“交换机制”均衡探测距离减少查找波动⭐ 四、核心对比Rehashing 扩容恢复O(1)Robin Hood 优化分布稳定性Rehashing解决“太满”Robin Hood解决“探测不均”