Нужно ли нам определять количество подсчетов при создании unordered_map?

Question

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

Перефразировка происходит только в том случае, если новое количество элементов больше max_load_factor()*bucket_count(), Если вставка прошла успешно, указатели и ссылки на элемент, полученные при его удержании в дескрипторе узла, становятся недействительными, а указатели и ссылки, полученные на этот элемент до его извлечения, становятся действительными. (начиная с C++17)

Выше документ от std::unordered_map, Я думаю, что повышение похоже? Но в его документе не указано условие перефразировки.

Если я инициализирую количество сегментов до 100, и есть сегмент, содержащий все 100 элементов, то перефразировка не произойдет, пока не будет вставлен элемент 101... Если я использую счетчик по умолчанию, я предполагаю, что это << 100, Перефразировка может произойти гораздо раньше.

Если да, то когда мы хотим инициализировать количество сегментов?

Answer 1

Если да, то когда мы хотим инициализировать количество сегментов?

Когда профилирование показывает, это помогает.

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

Как обычно, если по умолчанию достаточно быстро, просто используйте это.

Answer 2

Хорошее эмпирическое правило заключается в том, что хэш-таблица должна заполняться только на 70% (70% - это коэффициент загрузки). Это приводит к некоторым столкновениям, но не слишком много.

Если вы заранее знаете, что количество предметов, которые вы планируете поместить в свою таблицу, N затем установите количество ведер в ((int)N/0.7)+1 может быть хорошим выбором, чтобы избежать необходимости перефразировать. Если вы экспериментируете с коэффициентом загрузки, вы хотите использовать ((int)N/load_factor)+1,

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