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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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