Почему расширения хеш-таблицы обычно делаются путем удвоения размера?

Question

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

Практически всегда рекомендуется удваивать (или удваивать плюс 1, то есть 2n + 1) размер хеш-таблицы. Однако мне не удалось найти вескую причину для этого.

Зачем удваивать размер, а не, скажем, увеличивать его на 25% или увеличивать до размера следующего простого числа или следующих k простых чисел (например, трех)?

Я уже знаю, что часто хорошей идеей является выбор начального размера хеш-таблицы, который является простым числом, по крайней мере, если ваша хеш-функция использует модуль, такой как универсальное хеширование. И я знаю, что поэтому обычно рекомендуется делать 2n + 1 вместо 2n (например, http://www.concentric.net/~Ttwang/tech/hashsize.htm)

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

(И да, я читал статью в Википедии о хэш-таблицах :) http://en.wikipedia.org/wiki/Hash_table

Answer 1

Хеш-таблицы не могут претендовать на «вставку амортизированного постоянного времени», если, например, изменение размера происходило с постоянным приращением. В этом случае стоимость изменения размера (которая увеличивается с размером хеш-таблицы) сделает стоимость одной вставки линейной по общему количеству вставляемых элементов. Поскольку изменение размера становится все более и более дорогим с размером таблицы, это должно происходить «все реже и реже», чтобы поддерживать постоянную амортизированную стоимость вставки.

Большинство реализаций позволяют увеличивать среднее заполнение сегмента до тех пор, пока граница не будет заранее установлена ​​до изменения размера (где-то между 0,5 и 3, что является приемлемым значением). С этим соглашением, только после изменения размера, средняя занятость ведра становится наполовину меньше. Изменение размера путем удвоения сохраняет среднее заполнение ковша в полосе ширины * 2.

Подпримечание: из-за статистической кластеризации вы должны взять среднее заполнение сегмента всего 0,5, если вы хотите, чтобы во многих сегментах было не более одного элемента (максимальная скорость для обнаружения игнорирования сложных эффектов размера кэша), или до 3, если требуется минимальное количество пустых сегментов (соответствующих пустому пространству).

Answer 2

Я прочитал очень интересную дискуссию о стратегии роста на этом самом сайте ... просто не могу найти ее снова.

Хотя обычно используется 2, было продемонстрировано, что это не лучшее значение. Одна из часто упоминаемых проблем заключается в том, что она плохо справляется со схемами распределителей (которые часто распределяют мощность по двум блокам), поскольку она всегда требует перераспределения, тогда как на самом деле меньшее количество может быть перераспределено в одном и том же блоке (имитируя рост на месте) и, следовательно, быть быстрее.

Таким образом, например, стандартная библиотека VC++ использует коэффициент роста 1.5 (в идеале это должно быть золотое число, если используется стратегия выделения памяти в первую очередь) после обширного обсуждения в списке рассылки. Объяснение объясняется здесь :

Мне было бы интересно, если бы другие реализации векторов использовали коэффициент роста, отличный от 2, и я также хотел бы знать, использует ли VC7 1,5 или 2 (поскольку у меня нет этого компилятора здесь).

Существует техническая причина, по которой предпочтение отдается 1,5, а точнее - значениям, меньшим 1+sqrt(5)/2.

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

Оказывается, что если коэффициент роста равен >= 1+sqrt(5)/2, то новая память всегда будет слишком большой для оставленной дыры, оставленной мягче; если это < 1+sqrt(5)/2, новая память в конечном итоге будет соответствовать. Таким образом, 1.5 достаточно мал, чтобы можно было повторно использовать память.

Конечно, если фактор роста равен >= 2, то новая память всегда будет слишком большой для дыры, которая до сих пор оставалась; если это < 2, новая память со временем будет соответствовать. Предположительно, причина (1+sqrt(5))/2 заключается в ...

• Начальное распределение s.
• Первое изменение размера k*s.
• Второе изменение размера k*k*s, которое будет соответствовать отверстию, если k*k*s <= k*s+s, то есть, если k <= (1+sqrt(5))/2

... отверстие можно переработать как можно скорее.

При сохранении своего прежнего размера он может расти фибоначтически.

Конечно, он должен быть адаптирован к стратегии выделения памяти.

Answer 3

Одна из причин удвоения размера, характерного для хеш-контейнеров, заключается в том, что если емкость контейнера всегда равна степени двух, то вместо использования универсального модуля для преобразования хеш-функции в смещение, тот же результат может быть достигнут с помощью немного сдвигается. Modulo - медленная операция по тем же причинам, что и целочисленное деление. (То, является ли целочисленное деление «медленным» в контексте того, что еще происходит в программе, конечно же, зависит от регистра, но оно, безусловно, медленнее, чем другая основная целочисленная арифметика.)

Answer 4

Для удвоения размера применяются те же аргументы, что и для реализаций vector / ArrayList, см. этот ответ .

Answer 5

Если вы не знаете, сколько объектов вы в конечном итоге будете использовать (скажем, N),
удвоив пространство, вы получите максимум ₂ N перераспределений.

Я предполагаю, что если вы выберете правильное начальное "n", вы увеличите коэффициент
что 2 * n + 1 будет производить простые числа в последующих перераспределениях.

Answer 6

Удвоение памяти при расширении любого типа коллекции - часто используемая стратегия, предотвращающая фрагментацию памяти и не требующая слишком частого перераспределения. Как вы указали, могут быть причины иметь простое число элементов. Зная ваше приложение и ваши данные, вы также сможете прогнозировать рост числа элементов и, таким образом, выбрать другой (больший или меньший) коэффициент роста, чем удвоение.

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