std::unordered_map блокирует количество сегментов

Question

Я пытаюсь сделать тест производительности на контейнере std:: unordered_map в C++11.

Я хочу посмотреть, как коэффициент загрузки контейнера влияет на производительность для вставок. В частности, потому что меня интересует использование хеш-таблицы в качестве базовой структуры данных для поиска пар в огромном наборе чисел.

Как я понимаю документация, это не представляется возможным. Я могу установить количество ведер с rehash() но это делается автоматически в любое время max_load_factor превышен

Я могу установить max_load_factor но, насколько я понимаю, это только определяет, когда выполняется перефразировка, но не позволяет подвергать стол тяжелой нагрузке, что я и хочу сделать.

Можно ли как-то жестко ограничить количество сегментов в хэш-таблице?

Answer 1

Установить max_load_factor в INFINITY, Таким образом, контейнер никогда не должен поддаваться искушению сделать автоматический rehash чтобы сохранить load_factor ниже max_load_factor,

Answer 2

Не уверен, что это хороший ответ, но это объяснение, почему это может быть невозможно.

Если у вас есть открытая адресация, вам нужно resize, но это детали реализации. У вас может быть реализация, использующая цепочечное разрешение коллизий и накладывающая ограничение на длину цепочки, а также изменяющая размер при ее нарушении. Многие вещи могут произойти под капотом.

Я имею в виду, что с точки зрения пользователя вам не гарантировано, что вы можете безопасно исправить количество сегментов, потому что некоторые реализации могут взорваться. Даже если вы допустите высокий коэффициент загрузки, время от времени при добавлении размер таблицы будет изменяться, потому что целевой бак заполнен, иначе он не сможет принять элемент. Это может произойти даже при относительно низких коэффициентах нагрузки.

Конечно, некоторые реализации могут обрабатывать произвольно большие коэффициенты загрузки, но это не общее свойство.

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