unordered_set::find的复杂性可预测吗？

Question

在寻找适合我正在构建的应用程序的容器时，我浏览了unordered_set的文档。考虑到我的应用程序通常只需要insert和find函数，这个类看起来相当有吸引力。但是，由于find是O(1)摊销的，但是O(n)最坏的情况--我会频繁地使用该函数，这会使我的应用程序成败。是什么导致了复杂性的激增？遇到O(n)搜索的可能性可预测吗？

Answer 1

_unordered_set_是作为哈希表实现的，也就是说，哈希表的常见实现之一是使用哈希桶的容器(例如:向量)(它是一个容器(例如:列表)，它包含在同一个桶中的unordered_set元素的)。

当在unordered_set中插入元素时，将应用哈希函数，这将为您提供放置桶的位置。

可以在同一个桶中插入不同的元素，当您找到一个元素时，将应用散列函数，为您提供存储桶，您需要使用它们的元素搜索您要查找的元素。

最坏的情况是，所有元素都在同一个桶中结束(依赖于用于将元素存储在同一个桶中的容器)，当所有元素都在同一个桶中时，O(n)是最糟糕的搜索运行时间。

以同一桶结尾的元素的关键点是散列函数(它有多好)和元素(可能暴露哈希函数的特定弱点)。

如果在您的情况下有足够的可预见性，那么通常无法预测的元素(您可以选择一个散列函数来均匀地分布这类元素)。

为了加快搜索速度，关键是使用好的散列函数(在桶中平均分配元素，并在需要时使用重散列增加桶大小(注意此选项，散列函数将应用于所有元素)。

我建议，如果对于您的应用程序来说非常重要的是存储该元素，那么您进行性能测试时要尽可能接近生产数据(并从那里作出决定)，即STL中的容器和同一组中的容器(例如:关联的，等等)。共享几乎相同的接口，很容易彼此更改，所使用的代码很少或根本不改变。