Нужно ли нам определять количество подсчетов при создании unordered_map?
В конструкторе unordered_mapмы можем определить количество выделенных сегментов. Я думал, что смогу сократить время перефразировки. Тем не менее, это может также ухудшить производительность в некоторых случаях. Перефразировка происходит при вставке, когда
Перефразировка происходит только в том случае, если новое количество элементов больше
max_load_factor()*bucket_count(), Если вставка прошла успешно,
указатели и ссылки на элемент, полученный во время его хранения в
дескриптор узла признан недействительным, а указатели и ссылки получены
этот элемент, прежде чем он был извлечен, становятся действительными. (начиная с C ++ 17)
Выше документ от std::unordered_map, Я думаю, что повышение похоже? Но в его документе не указано условие перефразировки.
Если я инициализирую количество сегментов до 100, и есть сегмент, содержащий все 100 элементов, то перефразировка не произойдет, пока не будет вставлен элемент 101 … Если я использую счетчик по умолчанию, я предполагаю, что это << 100, перепрошивка может произойти гораздо раньше.
Если да, то когда мы хотим инициализировать количество сегментов?
Решение
Если да, то когда мы хотим инициализировать количество сегментов?
Когда профилирование показывает, это помогает.
Более конкретный совет не может быть дан, поскольку это зависит как от точных данных, так и от используемой хэш-функции.
Как обычно, если по умолчанию достаточно быстро, просто используйте это.
Другие решения
Хорошее эмпирическое правило заключается в том, что хэш-таблица должна заполняться только на 70% (70% — это коэффициент загрузки). Это приводит к некоторым столкновениям, но не слишком много.
Если вы заранее знаете, что количество предметов, которые вы планируете поместить в свою таблицу, N затем установите количество ведер в ((int)N/0.7)+1 может быть хорошим выбором, чтобы избежать необходимости перефразировать. Если вы экспериментируете с коэффициентом загрузки, вы хотите использовать ((int)N/load_factor)+1,
Создание слишком большой таблицы, вероятно, не сильно повлияет на скорость: стоимость выделения памяти не сильно зависит от того, сколько памяти вы выделяете, и, при превышении определенного размера, все таблицы будут иметь низкую производительность кэша для случайного доступа.