爲什麼unordered_multiset作品不好等於多鍵

Question

我有這樣一段代碼：

unordered_multiset<int> t; 
for (int i = 0; i < 1000000; i++) { 
    if (i % 10000 == 0) 
     cout << i << endl; 

    t.insert(10); 
} 

所以它只是把很多相等的元素在一個unordered_multiset。但是我發現我有更多的散列元素會更慢一些呢？我不明白原因。在我看來，在應用哈希函數並找到相等元素的桶（因爲所有相同的元素被組合在一起）之後，只需將它們放在桶的末尾。

那麼這裏有什麼問題？

UDP： 我發現unordered_multiset ::插入功能的描述

單元素插入： 平均情況：不變。 最差情況：容器大小呈線性。

所以，現在的問題可以表述爲：「爲什麼最糟糕的情況是線性的」

Answer 1

容器試圖通過重組存儲使平均桶大小是load_factor低於自身平衡。它通過添加更多桶來實現這一點，希望數據將更均勻地分佈。

當您在所有元素中存儲相同的值時，無論如何它們都會在同一個存儲桶中結束。哈希表最糟糕的可能條件！

Answer 2

一切都在同一個桶中。爲了把一些東西放在桶的最後，你必須找到桶的末端，桶中的東西越多，需要的時間就越長。