Почему расширения хеш-таблицы обычно делаются путем удвоения размера?
Я провел немного исследования на хеш-таблицах, и я продолжаю бежать через эмпирическое правило, что, когда существует определенное число записей (или макс. или через коэффициент загрузки как 75%) хеш-таблица должна быть расширена.
Почти всегда рекомендация состоит в том, чтобы удвоить (или дважды плюс 1, т.е. 2n+1) размер хеш-таблицы. Однако я не смог найти серьезное основание для этого.
Почему дважды размер, вместо того, чтобы, скажем, увеличить его 25% или увеличить его до размера следующего простого числа или следующих k простых чисел (например, три)?
Я уже знаю, что это часто - хорошая идея выбрать начальный размер хеш-таблицы, который является простым числом, по крайней мере, если Ваша хеш-функция использует модуль, такой как универсальное хеширование. И я знаю вот почему, что обычно рекомендуется сделать 2n+1 вместо 2n (например, http://www.concentric.net/~Ttwang/tech/hashsize.htm)
Однако как я сказал, я не видел реального объяснения того, почему удвоение или doubling-one является на самом деле хорошим выбором, а не некоторым другим методом выбора размера для новой хеш-таблицы.
(И да я прочитал статью Wikipedia о хеш-таблицах :) http://en.wikipedia.org/wiki/Hash_table
5 ответов
Хеш-таблицы не могли требовать "вставку амортизированного постоянного времени", если, например, изменение размера было постоянным приращением. В этом случае стоимость изменения размера (которая растет с размером хеш-таблицы) сделает стоимость одной вставки линейной по отношению к общему количеству вставляемых элементов. Поскольку изменение размера становится все более дорогостоящим с увеличением размера таблицы, это должно происходить «все реже и реже», чтобы амортизированная стоимость вставки оставалась постоянной.
Большинство реализаций позволяют увеличивать среднюю занятость сегмента до тех пор, пока не будет заранее зафиксирована граница перед изменением размера (где-то между 0,5 и 3, что является приемлемым значением). В соответствии с этим соглашением сразу после изменения размера средняя занятость ковша становится вдвое меньше. При изменении размера путем удвоения средняя занятость ковша остается в диапазоне шириной * 2.
Дополнительное примечание: из-за статистической кластеризации вы должны взять среднее заполнение сегмента как 0,5, если вы хотите, чтобы многие сегменты содержали не более одного элемента (максимальная скорость для поиска, игнорируя сложные эффекты размера кеша), или до 3, если вы хотите минимальное количество пустых корзин (которые соответствуют потраченному впустую пространству).
Удвоение объема памяти при расширении любого типа коллекции - часто используемая стратегия для предотвращения фрагментации памяти и отсутствия необходимости слишком частого перераспределения. Как вы отметили, могут быть причины иметь простое количество элементов. Зная свое приложение и свои данные, вы также можете предсказать рост количества элементов и, таким образом, выбрать другой (больший или меньший) фактор роста, чем удвоение.
Общие реализации, найденные в библиотеках, являются именно такими: Общие реализации. Они должны сосредоточиться на том, чтобы быть разумным выбором в самых разных ситуациях. Зная контекст, почти всегда можно написать более специализированную и более эффективную реализацию.
Я читал очень интересную дискуссию о стратегии роста именно на этом сайте... только не могу найти ее снова.
Хотя 2 широко используется, было продемонстрировано, что это не самое лучшее значение. Одна из часто упоминаемых проблем заключается в том, что оно плохо справляется со схемами аллокаторов (которые часто выделяют блоки power of twos), поскольку в этом случае всегда потребуется перераспределение, в то время как меньшее число на самом деле может быть перераспределено в том же блоке (имитируя рост на месте) и, таким образом, быстрее.
Так, например, в стандартной библиотеке VC++ используется коэффициент роста 1.5 (в идеале это должно быть золотое число, если используется стратегия распределения памяти по принципу "первый подходит") после длительного обсуждения в списке рассылки. Причина объясняется здесь:
Мне было бы интересно, использует ли какая-либо другая реализация векторов коэффициент роста, отличный от 2, и я также хотел бы знать, использует ли VC7 1.5 или 2 (поскольку у меня нет этого компилятора).
Есть техническая причина предпочесть 1.5 2 - точнее, предпочесть значения меньше, чем
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... отверстие можно срочно утилизировать.
Она может, сохраняя свой предыдущий размер, расти фибонаправленно.
Конечно, это должно соответствовать стратегии распределения памяти.
Если вы не знаете, сколько объектов вы в итоге будете использовать (допустим, N),
, удвоив пространство, вы сделаете log2N перераспределений максимум.
Я предполагаю, что если вы выберете правильное начальное "n", вы увеличите шансы
что 2*n + 1 будут давать простые числа при последующих перераспределениях.
Для удвоения размера применимы те же рассуждения, что и для реализации vector/ArrayList, см. этот ответ.