Какое значение bucket_count следует использовать, если я знаю предполагаемое количество ключей карты?

Question

Я создаю std::unordered_map, который я немедленно перейду к заполнению с помощью n пар ключ-значение - и я знаю n. После этого не будет добавлено больше элементов - я буду выполнять поиск только.

Что, следовательно, следует передать как bucket_count конструктору?

Примечания:

• Я знаю, что это не очень критическое, и я просто не мог указать ничего, и он будет работать.
• Это связано, но не контратип, What should I pass to unordered_map's bucket count argument if I just want to specify a hash function?)
• Если это поможет ваш ответ, вы можете предположить, что я хочу, чтобы иметь коэффициент нагрузки между f_1 и F_2 (известный заранее).
• Я использую функцию хэш-умолчанию, и я не знаю, что вход как, но это вряд ли будет состязательный к хеширования ..

Answer 1

Согласно n4296 в 23.5.4.2 [unord .map.cnstr] (это окончательный вариант C++ 14) по умолчанию max_load_factor для unordered_map равен 1.0, поэтому вы можете просто установить bucket_count на n.

Существует, очевидно, промежуток времени между увеличением количества ковша для улучшения скорости и уменьшения его (и повышения максимального коэффициента нагрузки) для улучшения пространства.

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

Если вы знаете диапазон коэффициентов нагрузки, которые вы хотите, тогда вы просто установите подсчет ведра на std::ceil(n/(std::max(f_1,f_2)) (и установите коэффициент загрузки, прежде чем заполнять карту).

Answer 2

Учитывая тот факт, что у вас есть диапазон для вашего коэффициента загрузки, единственной недостающей информацией является скорость столкновения. Вы можете просто использовать nb_buckets = n/f_2, и вы обязательно получите коэффициент загрузки менее или равный f_2. Для корректной работы около f_1 необходимо данные о стоимости столкновений.