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

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

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

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

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

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

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

Ответ 1

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

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

Ответ 4

Те же рассуждения применяются для удвоения размера, как для реализации vector/ArrayList, см. этот ответ.

Ответ 5

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

Ответ 6

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

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