不是通过多项式滚动来计算字符串 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字符串，推理是正确的，但字符串长度由要哈希的字符串数决定的"场景"有点奇怪。

如果计算是O(N(，那么散列N个字符串不是O(N²(吗？

给定字符串的长度随字符串的数量而缩放，那么，对于给定的哈希算法，这确实会导致O(n²(。但通常情况下，字符串的长度和要散列的字符串数量之间没有相关性。

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

Answer 2

是的，散列N个长度为N的字符串是一个O(N²(过程。(尽管在实践中，你很少遇到这样巧合的情况。(