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中的容器和更多的容器（例如：關聯等）共享幾乎相同的界面，很容易改變另一個界面，很少或根本沒有改變使用的代碼。