Почему 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, Но я узнал, что чем больше элементов в хэше, тем медленнее это работает? И я не могу понять причину. По моему мнению, после применения хеш-функции и нахождения сегмента равных элементов (поскольку все равные элементы сгруппированы вместе), stl просто помещает их в конец сегмента.

Так что здесь не так?

UDP: я нашел описание функции unordered_multiset::insert

Вставки отдельных элементов: Средний регистр: постоянный. В худшем случае: линейный по размеру контейнера.

Таким образом, вопрос теперь можно перефразировать так: "Почему наихудший случай является линейным"

Answer 1

Все идет в одном ведре. Чтобы положить что-то в конец ведра, вы должны найти конец ведра, и чем больше вещей в ведре, тем дольше это занимает.

Answer 2

Контейнер пытается сбалансировать себя путем реорганизации хранилища так, чтобы средний размер сегмента был ниже load_factor. Это достигается путем добавления большего количества сегментов в надежде, что данные будут распределены более равномерно.

Когда вы сохраняете одинаковое значение во всех элементах, они все равно окажутся в одном и том же сегменте. Наихудшее условие для хеш-таблицы!