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

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

Как правило, вы смотрите на коэффициент загрузки (неофициально, вы уже сказали, что), который формально определяется как α = n / N , то есть отношение используется к общему ковши. Для того, чтобы хэш-таблица функционировала должным образом (или, по крайней мере, рассуждала о ее производительности в математических терминах), она должна быть α <1. </p>

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

Answer 3

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

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

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

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

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

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

Answer 4

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

Answer 5

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

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