CRC32 Вероятность столкновения

Я довольно много проверил другие вопросы, и я все еще не уверен в этом вопросе.

Вот мой случай использования:

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

Поэтому я написал модуль, который берет содержимое корзины покупок и аккуратно оформляет ее в виде оценки в формате PDF.

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

Корзина покупок в настоящее время генерирует 5-значный идентификатор корзины, уникальный для каждого клиента в зависимости от его сеанса. Я взял этот 5-значный идентификатор корзины, а затем добавил к нему время UNIX, что дает мне красивое длинное число для использования в качестве номера оценочного документа.

Итак, я получаю что-то вроде этого: 363821482812537 [36382 — это идентификатор корзины, а 1482812537 — время unix на момент создания оценки PDF]

Проблема в том, что он слишком длинный и БУДЕТ проблемой, так как ссылки на банковские платежи ограничены. В идеале я хотел бы сохранить его до 10 символов или меньше.

Я решил взглянуть на CRC32, чтобы сократить сгенерированные оценочные числа, и, похоже, он способен сократить оценочное число до приемлемого количества символов.

Но может ли кто-нибудь пролить свет на то, с каким столкновением я могу столкнуться?

Несколько вещей, которые следует учитывать:

  1. Идентификатор корзины всегда будет состоять из 5 цифр.

  2. Время Unix всегда будет состоять из 10 цифр до 2286 года.

[Таким образом, у нас всегда будет 15 цифр, которые нужно закодировать, и не более]

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

  2. На данный момент клиентам не будет разрешено самостоятельно генерировать оценки по причинам, не важным для моего вопроса. Таким образом, только администраторы могут генерировать оценки.

Меня беспокоит простой вопрос: буду ли я очень часто сталкиваться с коллизиями с моей 15-значной хеш-кодировкой CRC32, или коллизии будут возникать довольно редко?


crc32 hash-collision
person StuyvesantBlue    schedule 27.12.2016    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Почему бы просто не поддерживать оценочное число, которое вы просто увеличиваете каждый раз, когда вам нужен новый? Вы уже эффективно поддерживаете список используемых номеров для проверки на коллизии, поэтому просто поместите туда свой счетчик. Тогда вам нужно смотреть только на одну вещь вместо n вещей. Принимая CRC, вы отбрасываете информацию, которую могли бы попытаться извлечь из оценочного числа, поэтому изначально не было смысла делать идентификатор из этой информации. Ваш подход кажется намного сложнее, чем должен быть.

Вероятность отдельного столкновения составляет 2-32. Содержание данных не имеет значения, если оно превышает 32 бита, как в данном случае, поскольку CRC очень хорошо смешивает биты. Однако у вас есть n шансов на столкновение, если вы ранее сгенерировали n оценок. Таким образом, с ростом n вероятность столкновения соответственно возрастает. (См. «Проблему дня рождения».) В результате всего после 77 164 оценок существует вероятность 50%, что два их хэша столкнулись.

person Mark Adler    schedule 27.12.2016
comment
Самая большая проблема, с которой я столкнулся, заключалась в том, что две оценки, генерируемые одновременно, вызывают конфликт обновлений в поле счетчика в базе данных MySQL. Как видите, я не очень хорошо разбираюсь в этом деле. Итак, я кое-что прочитал о том, как MySQL выполняет запросы, относительно ссылочной целостности и того факта, что моя БД - это MyISAM, а таблица случаев блокируется и т. Д. Короткая версия, похоже, что, вероятно, не будет конфликта поля счетчика, обновляемого точно в в одно и то же время двумя запросами... Так получилось, что у меня есть неиспользуемое поле, и я буду использовать его в качестве счетчика для оценок. Спасибо за ваше руководство. - person StuyvesantBlue; 29.12.2016