PHP CRC32 дает одно и то же целочисленное значение для двух разных строк
Я использую функцию PHP crc32 для генерации числового эквивалента для MongoId, так как я использую этот числовой идентификатор в поиске mysql, так как поиск строки медленный.
Я сталкивался со случаем, когда crc32 дает одинаковое числовое значение для двух разных mongoid.
Любая помощь или предложение будет принята с благодарностью.
Спасибо
Gaurav
Решение
Ответ @ MarkAdler объясняет, почему вы получаете хэш-конфликт. Но если бы я был на твоем месте, меня бы больше интересовало, что я мог с этим поделать.
Конечно, вы могли бы использовать другой алгоритм хеширования, который генерирует более длинные хэши (меньше вероятность столкновения), но все еще приемлемо быстр. Вы найдете высоко оцененный обзор нескольких альтернатив в этот вопрос от programmers.stackexchange.com. У них у всех есть коллизии (по совпадению CRC32 неплохо справился с тестовыми наборами этого ответа), но вы можете попробовать некоторые из них на монгоидах и посмотреть, что произойдет.
Я также нашел это умное предложение: Чтобы сгенерировать 64-битный хеш, вы можете взять два разные 32-битные алгоритмы хеширования и объединение хэшей (конечно, это более или менее вдвое снизит скорость вашего хэширования).
Более надежным решением было бы написать код с пониманием, что хеш — это сегмент, и вы иногда получите несколько результатов (или неверный результат) из запроса crc32. Просто добавьте второй шаг, чтобы проверить не хэшированные идентификаторы возвращенных записей. Так как будет только несколько попаданий, это не займет много времени.
Другие решения
Если ваши строки не четыре байта или меньше, то это неизбежный что многие строки будут иметь любое заданное значение CRC-32. Если у вас есть хотя бы одна более чем 2 ^ 32 возможных строк, то абсолютно гарантировано, что по крайней мере две из этих строк будут отображаться в один и тот же CRC-32.
Там нет помощи или предложения. Вы не можете ожидать, что не будет никаких коллизий, если только не будет меньше возможных строк, чем возможных CRC.
Кстати, вы можете намеренно строить такие случаи с моим поддельный код, который позволяет вам дать ему набор битов, которые вы бы хотели изменить в строке, и он сообщит вам, какие из этих битов нужно перевернуть, чтобы получить желаемый CRC.