unordered_set<int> 的查找方法的时间复杂度是多少？

Question

find方法在unordered_set<int>中的时间复杂度是什么？

同时，是否可以更改哈希函数？

- navid mahdian

---

从你问题中的链接可以看出，该复杂度的平均情况为“常数”，最坏情况为“与容器大小成线性关系”。你还需要什么其他信息？同时，你可以通过更改unordered_set的Hash模板参数或为您的类型专门化std::hash<T>模板来更改哈希函数。 - KABoissonneault

请查看@jogojapan答案中的哈希函数示例，点击此处。 - HDJEMAI

Answer 1

unordered_set中的find方法的时间复杂度是什么？

...在你提供的页面中已经有了答案：

复杂度:

平均情况: 常数。

最坏情况: 与容器大小成线性关系。

---

而且，改变哈希函数是可能的吗？

是的。再次查看文档！

std::unordered_map接受一个Hash模板参数。这是一个自定义点，您可以在其中注入自己的哈希逻辑。自定义的Hash必须满足Hash概念。

- Vittorio Romeo

---

该页面尚未特别讨论INT类型。 - navid mahdian

@navidmahdian：那有什么关系呢？如果它没有特别提到一种类型，那就意味着它适用于所有类型。 - Vittorio Romeo

这是正确的，但我认为类型int可能总是在O(1)中找到一个元素，因为哈希更容易。 - navid mahdian

搜索的复杂度与密钥哈希的复杂度无关。虽然 std::hash<int>{}( 2 ) 可能会返回整数本身，但容器仍然必须探测并将该整数密钥与容器中包含的值进行比较。我不知道你期望什么样的魔法，但如果你有研究表明在所有情况下（即，密钥从未在存储中发生冲突），都可以实现 O(1)，那么请分享一下。 - KABoissonneault

Answer 2

我猜您可能会因为默认的最大负载系数为1而感到困惑。当您向unordered_set中插入一个int x时，它会进入桶i（i = x％桶的数量）。因此，即使哈希函数没有冲突，因为它将每个int映射到自身，但取模运算在某些情况下可能会发生“冲突”。例如，如果您按顺序插入1、4和6，则1和6都将在同一个桶中，并且find函数需要通过桶来找到它们。只有在负载系数达到最大负载系数时才会增加桶的数量。负载系数是每个桶中元素数量的算术平均值。因此，您实际上可以在每个桶中拥有多个元素，甚至可以将所有元素都放在同一个桶中。在这种情况下，查找集合中存在的元素需要对桶进行传统的顺序搜索（O（n））。以下是一个示例：

unordered_set<int> n;
n.insert(1);
n.insert(12);
n.insert(23);
n.insert(34);
n.insert(45);

在这种情况下，每个整数都在桶1中，因此当您查找56（56％11 = 1）时，需要遍历整个桶（大小为n，O（n））。负载因子为0.4545（5个元素/ 11个桶），因此不会添加桶。您可以降低max_load_factor（某些语言使用0.75的负载因子），但这将增加重新哈希的次数，因为您需要更频繁地预留桶（保留过程是分摊常量的，因为它使用与std :: vector相同的方法，这就是为什么在示例中我们有11个桶的原因）。

- ALEJANDRO PEREZ MORENO