<分区>
std::unordered_map被实现为哈希表。根据this :
In case of single element insertions, the Worst Case time complexity is
O(linear in container size)and Average case isO(1)
现在我正在使用 std::unordered_map<int, int>更新输入数组中元素的频率。
我的问题是我不明白如何确定平均情况和最坏情况何时发生？
<分区>
std::unordered_map被实现为哈希表。根据this :
In case of single element insertions, the Worst Case time complexity is
O(linear in container size)and Average case isO(1)
现在我正在使用 std::unordered_map<int, int>更新输入数组中元素的频率。
我的问题是我不明白如何确定平均情况和最坏情况何时发生？
最佳答案
最坏的情况可能发生在两种情况下。首先，如果您的哈希表已满，则必须对其进行扩展，其中包括重新散列所有元素。如何定义哈希表何时已满？有一个名为负载因子 的参数，它被定义为一个比率:number_of_elements / number_of_buckets .当负载因子超过max_load_factor时, 哈希表被扩展。默认情况下，unordered_map 容器有一个 max_load_factor of 1.0 .因此，如果您的插入触发重新散列，它不会是 O(1) .
第二种情况取决于哈希表的冲突解决技术的实现。最流行的实现是链接、线性探测、双重哈希。由于 C++ 标准强加的某些要求，all practical implementations of std::unordered_map use chaining用于冲突解决。简而言之，链接意味着将同一个桶中的所有条目组织为一个链表(或最近一些实现中的 BST)，这意味着添加一个新元素需要遍历该列表。理论上，在非均匀散列函数或通过选择一些病态输入的情况下，所有条目最终都可能在同一个桶中，添加新元素的复杂性实际上可能变成 O(linear in container size)。 .正如其他人已经提到的，std::hash<int>是一个很好的哈希函数，所以在实践中你不必太担心它。
关于C++ - std::unordered_map <int,int> 中的最坏情况和平均情况插入时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52471474/