Алгоритм примерно такой:
1) Берем размер хеш-таблицы в n = size(K). Метод открытой адресации.
2) Берем любую хеш-функцию (по области определения больше чем n
SHA1, MD5, xxhash, mur-mur-hash)
3) Начинаем наполнять таблицу.
4) Как только детектирована коллизия - удаляем старую таблицу и создаем новую
с размером например 120% от исходного n.
5) Повторяем алгортм до тех пор пока не будут расставлены все ключи.
Изучать хеширование на базе целых чисел - вобщем-то не интересно. Более общий случай - это
строки (String) и я-бы делал эксперименты со строками и с реальными данными (мобильные
телефоны емейлы налоговые номера и прочее). Целые числа - это .... слишком синтетические
тесты и их результаты потом никуда натянуть нельзя.
Да, для данной конкретной ситуации с хеш-функцией CRC32 можно предложить математическое объяснение такого поведения.
CRC32 - это циклический редундантный код (Cyclic Redundancy Check), который обычно используется для обнаружения ошибок в данных. Он оперирует с битами данных и вычисляет контрольную сумму для обнаружения ошибок в передаче данных.
При использовании CRC32 в вашем коде в качестве параметра хеш-функции для хэш-таблицы, вы фактически создаете некоторую последовательность хешей, каждый из которых зависит от предыдущего. Так как CRC32 обрабатывает данные по битам и вычисляет контрольную сумму, его свойства обеспечивают некоторую случайность и разнообразие в вычисленных хеш-значениях.
Когда вы используете хеш с предыдущей итерации для получения нового хеша (25-я строка), вы создаете последовательность хешей, которая зависит от предыдущих значений. Это приводит к тому, что каждый следующий хеш зависит от предыдущего и от входных данных (ключей), и, таким образом, обеспечивает разнообразие хешей. Кроме того, при каждом исполнении цикла происходит пересчет хеш-значения с новым параметром, что увеличивает разнообразие хешей в процессе.
С другой стороны, если вы используете обычный инкремент в качестве параметра хеш-функции (40-я строка), то вы просто увеличиваете параметр на 1 на каждой итерации. Это не создает достаточное разнообразие в хеш-значениях для обеспечения успешного поиска хеша без коллизий.
Таким образом, математическое объяснение заключается в том, что использование CRC32 и его свойства циклического редундантного кода, а также зависимость от предыдущего значения, обеспечивают разнообразие хешей при использовании хеша с предыдущей итерации. Это позволяет алгоритму быстро находить подходящий параметр для успешного заполнения бакета без коллизий.
