unordered_set :: find的复杂性是否可预测？

Question

在寻找适合我正在构建的应用程序的容器时,我遇到了文档unordered_set.鉴于我的应用程序通常只需要insert和find函数,这个类似乎很有吸引力.然而,我find被O(1)摊销的事实略微推迟,但O(n)最坏的情况 - 我会经常使用该函数,它可能会成就或破坏我的应用程序.导致复杂性飙升的原因是什么？进入O(n)搜索的可能性是否可预测？

Answer 1

_unordered_set_被实现为哈希表,也就是说,哈希表的一个常见实现是使用哈希桶的容器(例如:like vector)(它是同一个unordered_set元素的容器(例如:like list))桶).

在unordered_set中插入元素时,会应用散列函数,然后为您提供放置的存储区.

可能会有多个元素插入到同一个存储桶中,当您找到一个元素时,哈希函数会应用,为您提供存储桶,您需要搜索他们正在寻找的元素.

最糟糕的情况是所有元素都在同一个桶中结束(取决于用于在同一个桶O(n)中存储元素的容器是当所有元素都在同一个桶中时搜索的最差运行时间).

在同一个桶中结束的元素的关键点是散列函数(它有多好)和元素(可以暴露散列函数的特定弱点).

如果在你的情况下有足够的可预测性(你可以选择一个均匀分布这种元素的散列函数),那么这些元素通常无法预测.

为了加速搜索,关键点是使用良好的哈希函数(均匀分布桶中的元素,并在需要时使用rehash增加桶大小(注意此选项,哈希函数将应用于所有元素)).

我建议,如果对于您的应用程序来说存储这些元素非常重要,那么您应该尽可能接近生产数据进行性能测试(并从那里做出决策),这表示STL中的容器和更多相同组的容器(例如:associative等等)共享几乎相同的界面,易于彼此更改,使用的代码很少或没有变化.