Разбираюсь в задаче и довожу её до понятного результата
- Опыт работы
- 3 месяца
- На сайте с
- 2026 года
- Юридический статус
- Самозанятый
Учебно-исследовательский проект по анализу алгоритмов хеширования и структур данных на их основе.
Целью было не просто реализовать хеш-функцию, а экспериментально проверить её свойства: распределение результатов, вероятность коллизий и лавинный эффект, а также сопоставить экспериментальные данные с теоретическими оценками.
В работе также рассматривались хеш-таблицы, парадокс дней рождения как модель возникновения коллизий и фильтр Блума.
Реализовала программную часть исследования на Python и C++. В частности, исследовала MurmurHash3 и проводила серии вычислительных экспериментов на случайно генерируемых входных данных.
Для проверки лавинного эффекта изменяла отдельные биты входных значений и измеряла расстояние Хэмминга между исходным и новым хешем. Исследование проводилось для ключей различной длины и большого числа случайных значений.
Отдельно анализировала вероятность возникновения коллизий и сравнивала экспериментальные результаты с теоретической моделью, связанной с парадоксом дней рождения.
Результаты обрабатывала статистически и визуализировала для последующего анализа.
Экспериментально подтверждено устойчивое проявление лавинного эффекта MurmurHash3: при изменении одного входного бита в среднем менялась примерно половина битов результата.
В одном из экспериментов среднее значение составило около 15,99 изменившихся битов из 32, а частота изменения отдельных выходных битов находилась примерно в диапазоне 0,485–0,513.
Получен воспроизводимый набор экспериментов для анализа качества хеширования и сравнения экспериментальных результатов с теоретическими оценками.
