字符串哈希的思路是把字符串映射为整数，用整数比较代替一部分字符串比较。预处理完成后，可以在 O(1) 时间内取得任意子串的哈希值，常用于重复子串、字符串匹配和二分答案。

哈希函数存在冲突：不同字符串可能得到相同的哈希值。因此字符串哈希是一种概率算法，哈希相等不能严格证明字符串相等。对正确性要求很高的场景，应使用双哈希或在哈希相等后再次比较原字符串。

一、多项式滚动哈希

给定字符串 s，选择一个基数 base，令 code(s[i]) 为字符编码，定义前缀哈希：

prefix[0] = 0
prefix[i + 1] = prefix[i] * base + code(s[i])

使用模数 mod 时，以上计算需要在每一步取模。也可以使用 uint64_t 的自然溢出，让运算结果按 2^64 取模。无符号整数的溢出是 C++ 标准定义的行为，但仍然存在哈希冲突。

二、O(1) 计算子串哈希

设 prefix[i] 表示前 i 个字符的哈希值，power[i] 表示 base^i。对于半开区间 [left, right)：

hash(left, right) =
    prefix[right] - prefix[left] * power[right - left]

减法和乘法都在选定的模数下进行。使用 uint64_t 自然溢出时，减法和乘法也会自动按 2^64 计算。

2.1 C++17 实现

#include <cstdint>
#include <string_view>
#include <vector>

class RollingHash {
public:
  using Value = std::uint64_t;

  explicit RollingHash(std::string_view text,
                       Value base = 911382323)
      : prefix_(text.size() + 1), power_(text.size() + 1, 1) {
    for (std::size_t i = 0; i < text.size(); ++i) {
      const Value code = static_cast<unsigned char>(text[i]) + 1;
      prefix_[i + 1] = prefix_[i] * base + code;
      power_[i + 1] = power_[i] * base;
    }
  }

  // 返回 text[left:right] 的哈希值，区间为半开区间。
  Value Hash(std::size_t left, std::size_t right) const {
    return prefix_[right] -
           prefix_[left] * power_[right - left];
  }

  bool Equal(std::size_t left1, std::size_t right1,
             std::size_t left2, std::size_t right2) const {
    if (right1 - left1 != right2 - left2) {
      return false;
    }
    return Hash(left1, right1) == Hash(left2, right2);
  }

private:
  std::vector<Value> prefix_;
  std::vector<Value> power_;
};

std::string_view 按字节访问字符串。如果输入包含 UTF-8 中文，代码比较的是 UTF-8 字节序列，而不是 Unicode 码点；只要所有字符串使用相同的 UTF-8 编码，哈希比较仍然是一致的。

预处理时间复杂度为 O(n)，空间复杂度为 O(n)，每次子串哈希查询为 O(1)。

三、如何降低哈希冲突概率

常见做法包括：

  1. 选择合适的基数，不要使用过小的固定基数。
  2. 使用两个不同模数计算两个哈希值。
  3. 使用两个不同基数计算两个自然溢出哈希值。
  4. 哈希相等时，再对候选字符串进行原文比较。

“模数越大，冲突概率一定越低”并不是严格结论，实际概率还取决于哈希函数、输入分布和攻击方式。对于可能受到构造输入攻击的场景，不能只依赖一个固定哈希函数。

四、应用场景

字符串哈希可以用于：

  • 判断两个等长子串是否相等。
  • 二分查找最长重复子串。
  • 统计重复的固定长度子串。
  • 将字符串匹配问题转换为整数集合查找。

相关题目：187. 重复的 DNA 序列、1044. 最长重复子串。

五、总结

  • 滚动哈希使用前缀哈希和幂数组在 O(1) 时间内计算子串哈希。
  • 哈希相等不代表字符串一定相等，哈希冲突必须纳入设计考虑。
  • 双哈希或哈希后验证原文可以进一步降低错误概率。
  • 使用半开区间可以统一处理子串长度和边界。