string - 不是通过字符串 O(n) 的多项式滚动来计算哈希值，其中 n 是字符串大小？

Question

只需阅读有关字符串哈希和多项式哈希函数的知识即可计算它。 在我看来，计算哈希(字符串)的时间复杂度好像是 O(N)，其中“N”是字符串大小

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;
}

其中字符串“S”的哈希值可以计算为 S[0] + S[1].P + S[2].P.P + 。 . . S[N - 1].P^(N - 1)

如果计算是 O(N) 那么散列 N 个字符串不是 O(N^2) 吗？

Answer 1

简答:假定您插入了长度为 n 的 n 个字符串，推理是正确的，但是“场景”是字符串由要散列的字符串数决定，有点奇怪。

And if the computation is O(N) then isn't hashing N strings is O(N²)?

鉴于字符串的长度与字符串的数量成比例，那么对于给定的哈希算法，这确实会导致 O(n²)。但通常字符串的长度与要散列的字符串数量之间没有关联。

如果字符串的平均长度为k，并且有n个字符串，那么这是一个O(n×k)算法。因此，您是正确的，对象的“大小”会对性能产生影响，当然，哈希算法会随着对象的大小而缩放。