Сколько хеш-ведер

Question

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

Допустим, у меня есть 100 ведер. Должен ли я реорганизовать его, когда в нем 50 предметов? 500? 5000? Или я должен искать самое полное ведро и ключ на этом? Затем, когда я достиг этой точки, насколько большим мне будет сделать новую хеш-таблицу?

В связи с этим, если вы заранее знаете примерно, сколько элементов будет добавлено, есть ли способ вычислить количество сегментов, чтобы получить хорошую среднюю производительность?

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

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

Answer 1

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

Насколько вы должны его увеличить? Ну, нет также идеальной стоимости. Самое простое решение - удвоить мощность при каждом увеличении. То есть до 200, 400, 800 и так далее. Если вы думаете, что это слишком много (в конце концов, при увеличении размера хеш-таблицы, когда вы действительно увеличите размер хэш-таблицы, и вы, возможно, никогда не заполните все 16 МБ), вы увеличите коэффициент увеличения. По крайней мере, 1/3 рекомендуется (увеличение от 100 до 133), я бы сказал, возможно, пусть это будет расти на 50% каждый раз как компромисс.

Обратите внимание, что все это также зависит от того, как обрабатываются коллизии. Простой способ справиться с ними (мой личный фаворит) - хранить элементы в связанном списке при столкновении. Если на один и тот же ключ положено 3 предмета, для его поиска остается только до 3 сравнений. Так как связанный список очень неэффективен для поиска, вы можете увеличить емкость раньше, например, если 60% емкости используется для быстрого сохранения хеш-таблицы. OTOH, вы можете сделать что-то более сложное и вести статистику о количестве столкновений. Пока у вас почти нет коллизий (если у вас очень хорошая хеш-функция), вам вообще не нужно повторно хэшировать, даже если используется 99% его емкости. Также, если вы обрабатываете коллизии изощренным способом (например, каждый узел снова является отсортированной таблицей, и вы можете выполнять двоичный поиск по ним), ваш поиск все еще может быть достаточно быстрым, если таблица загружена на 200% (таким образом, у вас в два раза больше элементов как емкость). В этом случае вы можете сохранить статистику о том, насколько велика самая крупная отсортированная таблица, и когда она становится больше, скажем, 8 записей, вы думаете, что она становится слишком медленной, и затем вы повторно хэшируете.

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

Answer 2

Как правило, вы обращаете внимание на коэффициент загрузки (неофициально, вы это уже говорили), который формально определяется как & # 945; & nbsp; = & nbsp; n & nbsp; / & nbsp; N , т. е. отношение используемых к общему количеству сегментов. Чтобы хэш-таблица функционировала должным образом (или, по крайней мере, для оценки ее производительности в математических терминах), она должна быть & # 945; & Nbsp; & Lt; & Nbsp; 1.

Все остальное действительно зависит от эмпирических тестов: если вы видите, что ваша хеш-таблица плохо работает, начиная с & # 945; & nbsp; > & nbsp; 0.5, тогда не забудьте остаться под этим значением. Это значение также зависит от вашей техники разрешения столкновений. Хеширование с цепочкой может потребовать других факторов нагрузки, чем хеширование с открытой адресацией. Еще одним фактором является локальность кэша. Если ваш стол становится слишком большим, он не помещается в основную память. Поскольку ваш доступ к массиву является случайным, загрузка из кэша может стать узким местом.

Answer 3

Обычно существует два типа хеш-таблиц: открытая и закрытая.

В открытой хеш-таблице вы найдете правильное ведро на основе хеша, а затем создадите список элементов, свисающих с этого ведра.

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

Размер открытой хеш-таблицы обычно не изменяется. Вы устанавливаете начальный размер так, как вы считаете разумным для данной проблемы. Как уже отмечали другие, вы можете изменить размер открытой хеш-таблицы, но теперь рассуждать о производительности этой структуры данных становится очень сложно. Если вы измените размер, когда длина данного сегмента равна L, тогда вы могли бы изменить размер только L элементов во всей хеш-таблице, что очень неэффективно.

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

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

Answer 4

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

Ключ с хеш-таблицами - это алгоритм хеширования, а не количество сегментов. В идеале, вы всегда должны иметь не более одного элемента в каждом сегменте, поэтому в идеале вы должны изменять размер, когда количество элементов в хэш-таблице = количество сегментов. Если ваши данные распределены неравномерно, лучше использовать алгоритм хэширования, а не стратегию изменения размера.

Answer 5

Если вы используете Linear Hashing, сама таблица автоматически изменяет размеры, поддерживая постоянный коэффициент загрузки.