为何字符串哈希比较被认为是O(1)？线性实现引发的疑惑

你提到的矛盾点核心在于时间复杂度的语境不同，拆解来看：

• 首先，compute_hash函数遍历字符串计算哈希值的过程确实是O(n)，这是预处理阶段的开销——每个字符串只需要计算一次哈希值，之后可以把这个哈希值存储起来复用。
• 资料里说的“字符串比较时间复杂度降至O(1)”，指的是预处理完成后，每次比较两个字符串的哈希值的操作：直接对比两个整数，时间复杂度是O(1)，而不是直接对比字符串本身（直接对比最坏情况需要遍历到最后一个字符，是O(n)）。

举个实际场景的例子：如果你需要在一个包含1000个字符串的集合里，多次查找某个目标字符串，用哈希的话：

1. 先花O(n)每个的时间把所有字符串的哈希值都算好存起来（总预处理O(total_length)）；
2. 之后每次查找，只需要计算目标字符串的哈希（O(k)，k是目标字符串长度），然后和集合里的哈希值做O(1)的对比，不用再逐个字符比对每个字符串。

反过来，如果只需要比较两个字符串一次，哈希法反而多了计算哈希的开销，不如直接字符串对比高效；但当需要多次重复比较时，预处理的O(n)成本会被平摊，每次比较的实际成本就变成了O(1)，这才是字符串哈希优化的意义所在。

你引用的cp-algorithms的描述：

字符串哈希的核心思路是将每个字符串映射为整数，通过比较这些整数替代直接比较字符串，从而将字符串比较的执行时间降至O(1)。

对应的哈希实现代码：

long long compute_hash(string const& s) {
    const int p = 31;
    const int m = 1e9 + 9;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}

内容的提问来源于stack exchange，提问作者asdf