Когда вы вставляете элементы в unordered_map и новое количество элементов превышает max_load_factor()*bucket_count(), контейнер растет (растет количество сегментов) и происходит перехеширование.Я провел простой эксперимент: создал распределитель, который печатает размер выделенной памяти каждый раз, когда вызывается метод allocate(size_type n), и использует его с unordered_map. В цикле я вставлял в этот контейнер новые элементы (по одному элементу на каждой итерации).
Для std::unordered_map я получил такие числа:
Код: Выделить всё
2, 5, 11, 23, 47, 97, 199, 409, 823, 1741, 3739, 7517, 15173, 30727, 62233, 126271
и для повышения:
Код: Выделить всё
18, 30, 54, 98, 194, 390, 770, 1544, 3080, 6152, 12290, 24594, 49158, 98318
Мой вопрос: какова стратегия, которую std::unordered_map и boost::unordered_map используют для определения следующего количества сегментов для создавать? Эти цифры жестко закодированы или рассчитаны? Почему такие стратегии считаются хорошими?
Изменить:
Реализация зависит от компилятора. Я использую gcc 7.5 и повышаю версию 1.65.1, но любой ответ (для любой реализации) будет интересен.
Подробнее здесь:
https://stackoverflow.com/questions/652 ... -buckets-a