Why unordered_multiset works bad for many equal keys

Question

I have this piece of code:

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

    t.insert(10);
}

So it just puts a lot of equal elements in an unordered_multiset. But I found out that the more elements I have in hash more slower this works? And I cannot realize the reason. In my opinion after applying the hash function and finding equal element's bucket (since all equal elements are grouped together) stl just put them at the end of bucket.

So what's wrong here?

Udp: I found the the description of unordered_multiset::insert function

Single element insertions: Average case: constant. Worst case: linear in container size.

So the question now can be rephrased as: "Why the worst case is linear"

Answer 1

The container tries to balance itself by reorganizing the storage so that the average bucket size is below the load_factor. It does this by adding more buckets with the hope that the data will be more evenly distributed.

When you store the same value in all elements, they will end up in the same bucket anyway. Worst possible condition for a hash table!

Answer 2

Everything goes in the same bucket. To put something at the end of the bucket, you have to find the end of the bucket, and the more things in the bucket, the longer that takes.