变长字符串如何做哈希及冲突处理
哪些公司问过
答案要点
- 变长字符串哈希需遍历全部字符,让字符及其位置都参与运算
- 多项式哈希:h = h*base + c,对大质数取模或用 64 位无符号自然溢出
- 经典实现有 BKDR、djb2(初值 5381,乘 33)、FNV(异或与乘法交替)
- 预处理前缀哈希和 base 幂,可 O(1) 求任意子串哈希
- 冲突用双哈希降低概率,哈希表中用链地址法或开放寻址法处理
易错点
- 只取字符串首尾或固定前几位计算哈希,冲突严重
- 简单把字符值相加,导致字母相同、顺序不同的串哈希一样
- 把哈希值相等当作字符串相等,不做最终比对
面试官常见追问
- 哈希冲突怎么解决?
- 线性探测怎么删除元素?
- 什么是 hash 攻击?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。