Какое значение bucket_count следует использовать, если я знаю предполагаемое количество ключей карты?
Я создаю std::unordered_map который я немедленно перейду к заполнению n парами ключ-значение — и я знаю n. После этого больше не будет добавлено никаких элементов — я буду только выполнять поиск.
Что, следовательно, я должен передать как bucket_count конструктору?
Заметки:
- Я знаю, что это не очень важно, и я просто не могу ничего указать, и это сработает.
- Это связано, но не обман, Что я должен передать аргументу подсчета сегментов unordered_map, если я просто хочу указать хеш-функцию?)
- Если это поможет вашему ответу, вы можете предположить, что я хочу иметь коэффициент загрузки между f_1 и f_2 (известный заранее).
- Я использую хеш-функцию по умолчанию, и я не знаю, как выглядит ввод, но он вряд ли будет противостоять хешированию.
Решение
В соответствии с 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)), (и установите коэффициент загрузки, прежде чем заполнять карту).
Другие решения
Учитывая тот факт, что у вас есть диапазон для вашего коэффициента загрузки, единственной недостающей информацией является частота столкновений. Вы можете просто использовать nb_buckets = n / f_2 и вы обязательно получите коэффициент загрузки, меньший или равный f_2, Обеспечение правильности f_1 Требуются данные о частоте столкновений.