Какова веростность коллизии в рандомной строке?

Question

[WebDev]

Есть функция, которая генерирует случайную строку, состоящую из английских букв в двух регистрах и цифр 0-9. У меня есть таблица с данными и каждой записи нужно присвоить уникальную строку. Чем короче будет эта строка, тем лучше. Предлагается строка из 5 символов. Записей в таблице примерно 500 000, количество будет расти, примерно до 2 миллионов. Какой длины случайной строки будет достаточно, чтобы свести к минимуму риск появления дубликатов?

Answer 1

[Сергей Соколов]

Возможно лучше будет не случайную строку генерить, а последовательные id записей однозначно мапить (см. биекция, bijection) в пространство вашего алфавита. Так 100% не будет коллизий.

Чтобы коды последовательных id не выглядели последовательно, можно, например, реверсировать порядок бит в числе перед записью его новым алфавитом. Это сохранит однозначность отображения.

2 млн. записей укладываются в 20 бит (0 .. 2097151). Алфавит из англ. букв в двух регистрах и цифр состоит из 26+26+10 = 62 символов. Может, ещё пару символов добавить, будет ровно 64 (6 бит). Итого для одного id понадобится всего 4 символа вашего алфавита, и это с избытком: вместо 20 бит, целых 24 будете записывать.

Answer 2

[Антон Иванов]

Я бы обратил ваше внимание на стандартизированный UUID. Да, он длиннее и 5, и тем более 8 символов. Но он защищён от коллизий. И как плюс поддерживается "из коробки" большинством SQL баз данных (MySQL точно).

https://ru.wikipedia.org/wiki/UUID

Для PHP существует много скриптов, генерирующих уникальный UUID. Например,
https://github.com/ramsey/uuid

Answer 3

[OKyJIucT]

Имел опыт, когда 8символьный хеш (0-9a-f) показывал коллизии после 2 миллионов записей в таблице. Расширили до полного алфавита в двух регистрах - проблема ушла.

Answer 4

[Николай Конюхов]

Более 8 символов

Answer 5

[Радость моя]

Как выше написал конь - вероятность все равно есть. Это вы играете в лотерею - совпадет не совпадет.

Правильным будет повесить на поле со сгенерированной строкой unique-индекс, и все. А вставлять через insert ignore into, либо ловить ошибку вставки и перегенерировать строку. это 100% гарантия несовпадений. Иначе вы всегда рискуете.

Answer 6

[SagePtr]

Если пойдёт псевдослучайная строка, то тут рассмотрено множество методов: https://habrahabr.ru/company/virgilsecurity/blog/3...

Answer 7

[profesor08]

На пользуйся, вероятность коллизии - 0
php.net/manual/ru/function.uniqid.php

Еще можешь сделать нумерацию от 1 до N и перевести числа в какое-то строковое представление при помощи любого понравившегося алгоритма, важно чтоб уникальность данных гарантировалось уникальностью исходных.