为什么哈希函数是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)？任何帮助都将不胜感激！

- asdf

---

回复：“为什么给定字符串的哈希值只能在常数时间内运行？”：它并不是这样；但如果您编辑问题以解释为什么您认为它是这样，那么有人可能会为您澄清您所误解的内容。 - ruakh

大 O 表示法可能有些相对性。这个哈希算法的复杂度是 O(n)，其中 n 是字符串大小，但这与哈希表关注的字符串列表大小无关。如果你只关心在哈希表中查找一个元素所需的查找次数，那么它主要是 O(1)。还要注意，哈希值可以计算一次，缓存并且反复使用时的复杂度是平摊的 O(1)。 - user4581301

我认为你不应该合理地缓存哈希值，@user4581301。你需要一个从值到其缓存哈希的映射，但这又需要基于树或哈希映射的实现。 - Ulrich Eckhardt

理论上，您将拥有一些字符串的平均长度，这将是您的实际成本。这只意味着您的哈希具有高“常数”因子。 - NathanOliver

在这种情况下，可能不需要。可能会有一个围绕着std::string的包装器，记录哈希值以及string，但我怀疑这里是否是这种情况。 - user4581301

除非是练习，否则C++标准库为许多类型提供了哈希支持，包括std :: string。（请参阅https://en.cppreference.com/w/cpp/string/basic_string/hash）。 - user18978409

Answer 1

大O符号是一种描述算法执行时间如何随着其操作数据集的大小而增长的方法。为了应用这个定义，我们必须明确正在增长的数据集是什么。

在大多数情况下，这是显而易见的，但有时可能有点模糊不清，这就是其中之一。在这种情况下，“数据集”是指单个字符串吗？如果是，那么该算法的复杂度为O(N)，因为它执行的操作序列会随着字符串长度的增加而线性增长。但是，如果“数据集”是指相关哈希表中项数的数量，那么该算法可以被认为是O(1)，因为当处理具有100万个条目的Hashtable和处理具有两个条目的Hashtable时，对于任何给定的字符串，它的操作速度都是相同的。

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

- Jeremy Friesner

Answer 2

字符串哈希的想法是将每个字符串映射到一个整数，然后比较这些整数而不是字符串。这样做可以将字符串比较的执行时间降低到O(1)。

这句话有点误导人。计算字符串的哈希值需要O(n)的时间。但是一旦您计算出哈希值，就可以通过比较它们的哈希值来比较字符串。该段落仅涉及哈希值的比较，这是O(1)的。

但即使如此，说字符串比较变成了O(1)也是错误的。当哈希值不匹配时，字符串比较才是O(1)。匹配的哈希值不能保证字符串相同，您必须通过比较实际字符串来进行双重检查，这需要O(n)的时间。

因此，哈希给您提供了快速检测大多数情况下2个字符串是否相等的能力。如果您只想比较2个字符串，则完全没有意义。只有在多次比较时，使用字符串哈希才值得。您需要计算哈希值，存储它并多次使用它才能获得任何好处。

PS：有些应用程序假装哈希冲突不会发生，并且如果它们的哈希值匹配，则认为2个字符串相等。使用强加密哈希时，这几乎是确定的。但碰撞并非不可能发生，这就像玩俄罗斯轮盘赌。

- Goswin von Brederlow