跳到主要内容

字符串哈希

字符串哈希是一种将字符串映射为固定长度整数值的技术。通过哈希函数，我们可以将任意长度的字符串转换为一个唯一的（或几乎唯一的）整数，从而方便地进行字符串的比较、查找和存储。字符串哈希在算法竞赛、数据库索引、密码学等领域有着广泛的应用。

什么是字符串哈希？​

字符串哈希的核心思想是通过一个哈希函数，将字符串转换为一个整数。这个整数通常被称为哈希值。一个好的哈希函数应该满足以下条件：

  1. 确定性：相同的字符串总是生成相同的哈希值。
  2. 高效性：计算哈希值的时间复杂度应尽可能低。
  3. 均匀性：不同的字符串应尽可能生成不同的哈希值，以减少哈希冲突。

常见的哈希函数​

常见的字符串哈希函数包括多项式哈希、滚动哈希等。下面我们以多项式哈希为例进行讲解。

多项式哈希​

多项式哈希是一种常用的字符串哈希方法。它的基本思想是将字符串视为一个多项式，每个字符的 ASCII 值作为多项式的系数，然后选择一个基数（通常是质数）和一个模数，计算多项式的值。

多项式哈希公式​

给定一个字符串 s，其长度为 n，多项式哈希的计算公式为：

hash(s) = (s[0] * p^(n-1) + (s[1] * p^(n-2)) + ... + (s[n-1] * p^0)) % m

其中：

  • p 是一个质数基数（通常选择 31 或 53）。
  • m 是一个大质数模数（通常选择 10^9 + 7 或 10^9 + 9）。
  • s[i] 是字符串中第 i 个字符的 ASCII 值。

代码示例​

以下是一个计算字符串哈希值的 Python 示例：

python
def polynomial_hash(s, p=31, m=10**9 + 7):
    hash_value = 0
    power = 1
    for char in s:
        hash_value = (hash_value + (ord(char) - ord('a') + 1) * power) % m
        power = (power * p) % m
    return hash_value

# 示例输入
s = "hello"
print(polynomial_hash(s))  # 输出: 99162322

解释​

  • ord(char) - ord('a') + 1：将字符转换为 1 到 26 之间的整数，避免哈希值为 0。
  • power：表示当前字符的权重，初始为 p^0，每次循环乘以 p。
  • hash_value：累加每个字符的哈希贡献，最终取模 m。

滚动哈希​

滚动哈希是一种优化技术，用于快速计算字符串子串的哈希值。它通过滑动窗口的方式，利用前一个子串的哈希值快速计算当前子串的哈希值。

滚动哈希公式​

给定一个字符串 s，其长度为 n，滚动哈希的计算公式为：

hash(s[l..r]) = (hash(s[0..r]) - hash(s[0..l-1])) * inv(p^l) % m

其中：

  • inv(p^l) 是 p^l 的模反元素。
  • hash(s[0..r]) 和 hash(s[0..l-1]) 分别是前缀哈希值。

代码示例​

以下是一个计算子串哈希值的 Python 示例：

python
def rolling_hash(s, l, r, p=31, m=10**9 + 7):
    # 预计算前缀哈希值和 p 的幂次
    n = len(s)
    prefix = [0] * (n + 1)
    power = [1] * (n + 1)
    for i in range(n):
        prefix[i+1] = (prefix[i] + (ord(s[i]) - ord('a') + 1) * power[i]) % m
        power[i+1] = (power[i] * p) % m
    
    # 计算子串哈希值
    inv_power = pow(power[l], m-2, m)  # 费马小定理求模反元素
    hash_value = (prefix[r+1] - prefix[l]) * inv_power % m
    return hash_value

# 示例输入
s = "hello"
print(rolling_hash(s, 1, 3))  # 输出: 297767

解释​

  • prefix[i]：存储字符串 s[0..i-1] 的前缀哈希值。
  • power[i]：存储 p^i 的值。
  • inv_power：通过费马小定理计算 p^l 的模反元素。

实际应用场景​

1. 字符串匹配​

字符串哈希可以用于快速比较两个字符串是否相等。通过比较它们的哈希值，可以在常数时间内判断字符串是否匹配。

2. 子串查找​

在文本编辑器中，字符串哈希可以用于快速查找子串。通过预计算文本的前缀哈希值，可以在常数时间内计算任意子串的哈希值，并与目标子串的哈希值进行比较。

3. 密码学​

在密码学中，字符串哈希用于生成消息摘要，确保数据的完整性和安全性。常见的哈希算法包括 MD5、SHA-1、SHA-256 等。

总结​

字符串哈希是一种强大的工具，能够将字符串转换为唯一的整数值，从而简化字符串的比较、查找和存储。通过多项式哈希和滚动哈希，我们可以高效地计算字符串及其子串的哈希值。字符串哈希在算法竞赛、数据库索引、密码学等领域有着广泛的应用。

附加资源与练习​

  • 练习 1：实现一个函数，计算两个字符串的哈希值，并判断它们是否相等。
  • 练习 2：使用滚动哈希技术，查找一个字符串中所有与目标子串匹配的位置。
  • 附加资源：
提示

在实际应用中，选择合适的基数和模数非常重要。通常选择大质数作为模数，以减少哈希冲突的概率。