Может ли хэш для разных ключей совпадать?

Что проверяют

Понимаете ли вы, что коллизии неизбежны, и умеете ли оценить, когда они реально бьют по данным: дедупликация, джойны, партиционирование, признаки. Следом часто просят прикинуть вероятность коллизии на миллионе ключей или объяснить hashing trick.

Как отвечать

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

Оценка через парадокс дней рождения: при b-битном хэше вероятность хотя бы одной коллизии достигает 50% примерно на 1,18 · 2^(b/2) ключах. Для 32 бит это около 77 тысяч ключей, для 64 бит около 5 миллиардов. 32-битный хэш для дедупликации миллионов строк не годится.

Где это важно:

• хэш-таблицы (dict и set в Python, hash join и groupby в pandas и Spark): коллизии разрешаются сравнением самих ключей, результат остаётся верным, страдает только скорость;
• дедупликация и ключи по хэшу (pd.util.hash_pandas_object, xxhash64 или sha2 в Spark): здесь коллизия означает, что две разные строки посчитаются одной. Берите 64 или 128 бит, а у совпавших хэшей сверяйте исходные поля;
• hashing trick (FeatureHasher, HashingVectorizer в scikit-learn, по умолчанию 2^20 признаков): коллизии допускаются сознательно ради фиксированного размера, а alternate_sign=True по умолчанию гасит смещение от совпадений;
• партиционирование: hash(key) % N раскладывает строки по партициям, и перекос в ключах даёт перекос в партициях.

MD5 на случайных данных коллизий почти не даёт, но криптографически сломан: совпадение можно подобрать намеренно, и для защиты от подделки нужен SHA-256.

Где спотыкаются

Используют встроенный hash() Python для детерминированного разбиения на train и test. Хэш строк рандомизируется при каждом запуске процесса (PYTHONHASHSEED), и выборки меняются между запусками. Нужен hashlib или zlib.crc32.

Считают совпадение хэшей доказательством равенства строк и удаляют «дубли», не сверив сами значения.

Выбирают слишком маленький n_features в hashing trick: частые токены начинают делить один столбец, и качество модели падает без видимой ошибки.