floppa322, я вот решил следующее посчитать. Допустим я не буду вставлять конфликтующие ключи. А просто буду вести их список. Долг типа. Вот получилось так на 5 млн.
2023-07-28 20:06:28,511 : [INFO] - Start demo
2023-07-28 20:06:29,417 : [INFO] - Populated successfully!
2023-07-28 20:06:29,417 : [INFO] - Inserted : 3160854
2023-07-28 20:06:29,419 : [INFO] - Collision list size : 1839146
2023-07-28 20:06:29,419 : [INFO] - Hash set physical size is 5000000 slots (20000000 bytes)
2023-07-28 20:06:29,419 : [INFO] - Inserted/slots ratio : 63%
2023-07-28 20:06:29,419 : [INFO] - Finish
Из 5 лямов успешно вставились порядка 3.1 млн. Долговых ключей на 1.8. Хорошая новость
их хотя-бы не так много. Далее я могу рекурсивно применить алгоритм построения этой-же
таблицы к списку долговых ключей. Но теперь мне уже не нужно 5 млн слотов. Я сразу создаю
1.8. И если эта геометрическая прогрессия работает (100% - 63% = 37%) то каждый раз
я буду получать треть от оригнального размера. Хеш функцию в данном случае можно
даже не менять. Просто меняется у нас остаток от деления. Будет пирамида таблиц.
Алгоритм примерно такой:
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 и его свойства циклического редундантного кода, а также зависимость от предыдущего значения, обеспечивают разнообразие хешей при использовании хеша с предыдущей итерации. Это позволяет алгоритму быстро находить подходящий параметр для успешного заполнения бакета без коллизий.
Почему O(1) нельзя в данном случае ? Всегда можно сделать размер таблицы n^2 и захешировать, в среднем за 2 раза без коллизий сойдётся. Но с одной стороны так много памяти жалко, с другой, даже, если там будет всего лишь 10к интов, то оно даже в L3 не уложится (нужно 400 мб для этого, а стандавртный серверный L3 обычно 128/256 мб)