面试题库 › 客户端 › 变长字符串如何做哈希及冲突处理

变长字符串如何做哈希及冲突处理

难度 ★★☆在 2 场真实面经中被问到 方向:客户端考点:哈希表

哪些公司问过

腾讯1快手1

常见岗位:游戏客户端

答案要点

  1. 变长字符串哈希需遍历全部字符,让字符及其位置都参与运算
  2. 多项式哈希:h = h*base + c,对大质数取模或用 64 位无符号自然溢出
  3. 经典实现有 BKDR、djb2(初值 5381,乘 33)、FNV(异或与乘法交替)
  4. 预处理前缀哈希和 base 幂,可 O(1) 求任意子串哈希
  5. 冲突用双哈希降低概率,哈希表中用链地址法或开放寻址法处理

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题