为什么哈希函数是O(1)

Question

为什么查找给定字符串的哈希值只能在恒定时间内运行？

我正在尝试编写一个优化程序来使用字符串哈希来比较两个字符串。

据我所知，字符串的哈希通常由多项式滚动哈希函数定义。网上消息称计算这个哈希值并进行比较的时间复杂度为 O(1)。例如，https://cp-algorithms.com/string/string-hashing.html表示

字符串散列背后的想法如下：我们将每个字符串映射为一个整数，然后比较它们而不是字符串。这样做可以将字符串比较的执行时间减少到 O(1)。

但是，此哈希函数的实际实现（根据https://cp-algorithms.com/string/string-hashing.html）包括循环整个字符串：

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

这难道不能保证比较两个字符串的线性时间复杂度，而不是 O(1) 吗？任何帮助表示赞赏！

Answer 1

Big-O 表示法是一种描述算法的执行时间如何随着其处理的数据集的大小而增长的方式。为了应用该定义，我们必须指定将增长的数据集是什么。

在大多数情况下，这是显而易见的，但有时有点含糊不清，这就是其中之一。在这种情况下，“数据集”是否指单个字符串？如果是这样，那么该算法的复杂度为 O(N)，因为它必须执行的操作序列随着字符串的大小线性增长。但是，如果“数据集”指的是关联哈希表中的项目数，那么该算法可以被视为 O(1)，因为在处理一百万个条目时，它的运行速度同样快（对于任何给定的字符串）哈希表就像两个条目的哈希表一样。

关于使用哈希来比较两个字符串：一旦计算了两个字符串的哈希值，并将这些哈希值存储在某处，您就可以在 O(1) 时间内比较这两个哈希值（因为比较两个整数是固定成本的）操作，无论计算它们的字符串的大小如何）。但值得注意的是，这种比较只能告诉您两个字符串是否不同——如果两个哈希值相等，您仍然不能 100% 确定这两个字符串相等，因为（由于鸽巢原理）两个不同的字符串可以散列到相同的值。因此，在这种情况下，您仍然需要以常规 O(N)/逐个字符的方式比较字符串。