когда изменить размер хеш-таблицы?

Question

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

Мой вопрос: как получается это число?

Это произвольно?на основании тестирования?на основе какой-то другой логики?

Answer 1

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

Несколько лет назад я читал какую-то книгу компиляторов (не помню названия или авторов), в которой предлагалось использовать связанные списки, пока у вас не будет более 10–12 элементов. Казалось бы, поддержка более 10 коллизий означает время для изменения размера.

Разработка и реализация Dynamic. Хеширование для наборов и таблиц в Icon предполагает, что средней длины цепочки хеширования 5 (в этом алгоритме среднее число коллизий) достаточно для запуска перефразирования. Кажется, подтверждается тестированием, но я не уверен, что правильно читаю статью.

Похоже, что изменение размера в основном результат тестирования.

Answer 2

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

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

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

Answer 3

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

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

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

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

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

Answer 4

Столкновения сильно зависят от данных и используемой хэш-функции.

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

Answer 5

Насколько мне известно, число является эвристическим, основанным на эмпирическом тестировании.

При достаточно хорошем распределении значений хеш-функции кажется, что магический коэффициент загрузки, как вы говорите, обычнооколо 70%.Меньший коэффициент загрузки означает, что вы теряете пространство без реальной выгоды;более высокий коэффициент загрузки означает, что вы будете использовать меньше места, но будете тратить больше времени на обработку коллизий хешей.

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