🤔 Коллизия - когда для разных ключей получается одно и тоже хэш значение?

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

🚩Причины возникновения

🟠Ограниченное количество возможных хеш-значений
Поскольку количество возможных хеш-значений фиксировано (и обычно меньше, чем количество возможных ключей), статистически неизбежно, что разные ключи будут иметь одинаковые хеш-значения.
🟠Неидеальные хеш-функции
Хеш-функции могут не равномерно распределять хеш-значения, что увеличивает вероятность коллизий.

🚩Способы решения

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

🟠Открытая адресация (Open Addressing)
Включает в себя методы, такие как линейное пробирование, квадратичное пробирование и двойное хеширование. При возникновении коллизии метод находит следующую свободную ячейку в таблице для размещения нового элемента.

🟠Двойное хеширование (Double Hashing)
Использует вторую хеш-функцию для определения интервала между пробами, уменьшая вероятность коллизий, которые происходят при первичном хешировании.

Ставь 👍 и забирай 📚 Базу знаний