unordered_set<int> find 方法的时间复杂度
Time complexity of unordered_set<int> find method
unordered_set<int>中find方法的时间复杂度是多少？
还有可以更改哈希函数吗？
what is the time complexity of find method in unordered_set?
...它就在您链接的页面中：
Complexity:
Average case: constant.
Worst case: linear in container size.
and also it it possible to change the hash functions?
是的。再一次，看at the documentation!
std::unordered_map 采用 Hash 模板参数。这是一个 自定义点 ，您可以在其中注入自己的哈希逻辑。自定义 Hash 必须满足 Hash 概念。
我猜您对默认的 max_load_factor 为 1 感到困惑。当您在 unordered_set 中插入一个 int x 时，它会进入桶 i（i=x%桶数).因此，正如您可以想象的那样，即使散列函数不会发生冲突，因为它将每个 int 映射到自身，mod 操作在某些情况下也会发生“冲突”。例如，如果按顺序插入 1、4 和 6，则 1 和 6 将在同一个桶中，查找函数将需要遍历桶才能找到它们。只有当负载因子达到最大负载因子时，桶的数量才会增加。加载因子是每个桶中元素数量的算术平均值。所以你实际上可以在每个桶中有多个元素，你甚至可以在同一个桶中拥有相同的所有元素。在这种情况下，查找集合内的元素需要在存储桶内进行传统的顺序搜索 (O(n))。这里有一个例子：
unordered_set<int> n;
n.insert(1);
n.insert(12);
n.insert(23);
n.insert(34);
n.insert(45);
在那种情况下，每个 int 都在桶 1 中，因此当您查找 56 (56%11 = 1) 时，您需要遍历整个桶（大小 n，O(n)）。加载因子为 0.4545（5 个元素/11 个桶），因此没有添加任何桶。您可以减少 max_load_factor（某些语言使用 0.75 的负载因子），但这会增加重新散列的次数，因为您需要更频繁地保留桶（保留过程是摊销常数，因为它使用std::vector 使用相同的方法，这就是为什么在示例中我们有 11 个桶）
unordered_set<int>中find方法的时间复杂度是多少？
还有可以更改哈希函数吗？
what is the time complexity of find method in unordered_set?
...它就在您链接的页面中：
Complexity:
Average case: constant.
Worst case: linear in container size.
and also it it possible to change the hash functions?
是的。再一次，看at the documentation!
std::unordered_map 采用 Hash 模板参数。这是一个 自定义点 ，您可以在其中注入自己的哈希逻辑。自定义 Hash 必须满足 Hash 概念。
我猜您对默认的 max_load_factor 为 1 感到困惑。当您在 unordered_set 中插入一个 int x 时，它会进入桶 i（i=x%桶数).因此，正如您可以想象的那样，即使散列函数不会发生冲突，因为它将每个 int 映射到自身，mod 操作在某些情况下也会发生“冲突”。例如，如果按顺序插入 1、4 和 6，则 1 和 6 将在同一个桶中，查找函数将需要遍历桶才能找到它们。只有当负载因子达到最大负载因子时，桶的数量才会增加。加载因子是每个桶中元素数量的算术平均值。所以你实际上可以在每个桶中有多个元素，你甚至可以在同一个桶中拥有相同的所有元素。在这种情况下，查找集合内的元素需要在存储桶内进行传统的顺序搜索 (O(n))。这里有一个例子：
unordered_set<int> n;
n.insert(1);
n.insert(12);
n.insert(23);
n.insert(34);
n.insert(45);
在那种情况下，每个 int 都在桶 1 中，因此当您查找 56 (56%11 = 1) 时，您需要遍历整个桶（大小 n，O(n)）。加载因子为 0.4545（5 个元素/11 个桶），因此没有添加任何桶。您可以减少 max_load_factor（某些语言使用 0.75 的负载因子），但这会增加重新散列的次数，因为您需要更频繁地保留桶（保留过程是摊销常数，因为它使用std::vector 使用相同的方法，这就是为什么在示例中我们有 11 个桶）