std :: unordered_map заблокировать подсчет ведра

Question

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

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

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

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

Есть ли какой-либо способ для меня ограничить количество ведер в хеш-таблице?

Answer 1

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

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

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

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

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

Answer 2

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