В readme популярной библиотеки для генерации идентификаторов есть такой пункт:
random % alphabetявляется распространённой ошибкой, когда дело доходит до написания собственного генератора идентификаторов. При использовании такого подхода распределение будет неравномерным; для некоторых символов вероятность их появления будет ниже, чем для других. Таким образом, при грубом переборе потребуется меньшее количество попыток.
Также там приводится такая иллюстрация
и ссылка на статью на английском, в которой объясняется проблема. Тем не менее, ниже я хочу дать своё объяснение.
Собственный генератор идентификаторов
Как правило, за основу берётся криптографически безопасный генератор случайных чисел. В JS это crypto.randomBytes, а в Clojure — java.security.SecureRandom. С помощью такого генератора мы можем получать случайные значения из диапазона от 0 до 255. Вероятность выпадения каждого из них 1/256. Если у вас богатое воображение можете представить кубик с 256 гранями. Но допустим, нас интересуют только 26 значений — буквы латинского алфавита от «a» до «z».
Ошибочное решение
Возможно, первое решение, которое придёт вам в голову — использовать операцию получения остатка от деления % или rem. И тут кроется опасность. Чтобы её увидеть, применим rem ко всему диапазону значений:
(->> (range 256) ;; Создаём диапазон от 0 до 255.
(map #(rem % 26)) ;; Получаем остаток от деления на 26.
frequencies ;; Подсчитываем количество каждого значения.
sort) ;; Сортируем.
;; => ([0 10] [1 10] [2 10] … [21 10] [22 9] [23 9] [24 9] [25 9])
Видно, что значения с 22-го по 25-е — индексы букв «w», «x», «y» и «z» из рисунка выше — появились лишь 9, а не 10 раз как остальные. Это означает, что вероятность их выпадения будет меньше, чем у других символов. А это, в свою очередь, позволит снизить количество попыток при грубом переборе.
Частное решение
Чтобы понять почему так получилось, разделим 256 на 26 и получим 9,8462. Ага, значит 256 на 26 нацело не делится. А какие числа делятся? Правильно — степени двойки: 2, 4, 8, 16, 32, 64, 128 и 256. Таким образом, если количество символов в алфавите равно степени двойки, распределение будет ровным. Возьмём, например, 64 и проверим:
(->> (range 256)
(map #(rem % 64))
frequencies
sort)
;; => ([0 4] [1 4] [2 4] … [60 4] [61 4] [62 4] [63 4])
Все значения появились ровно по 4 раза. Здорово!
Общее решение
Но что делать, если мы всё-таки хотим использовать алфавит длина которого не является степенью двойки? Зная длину алфавита мы можем найти ближайшую к ней степень двойки в большую сторону. Это можно сделать вычислив логарифм по основанию 2 от длины алфавита. Так как в математической библиотеке нет функции логарифма по основанию 2, воспользуемся свойством перехода к новому основанию логарифма:
(/ (Math/log 26)
(Math/log 2))
;; => 4.700439718141093
Поскольку число получилось нецелым, округлим его в большую сторону и получим 5. Возведя 2 в 5 получаем 32. Как мы помним, степень двойки делится на 256 без остатка, т. к. 256 тоже является степенью двойки. Теперь при получении остатка от деления на 32, мы будем получать равномерно распределённые значения в диапазоне от 0 до 31. Но что делать со значениями, которые больше длины алфавита: 26, 27, 28, 29, 30, и 31? Ответ прост — ничего, мы будем их игнорировать.
Точно так и устроен алгоритм в Nano ID с той лишь разницей, что вместо операции % он использует побитовое умножение на маску (в нашем случае маска была бы равна 32 - 1 = 31 или 11111 в двоичной системе). При этом если сгенерированных значений не хватает из-за того, что какие-то из них приходится игнорировать, он запрашивает новые, и так до тех пор пока не получится идентификатор нужной длины.
(->> (range 256)
(map #(bit-and % 31)) ;; Побитовое умножение на маску.
frequencies
sort)
;; => ([0 8] [1 8] [2 8] … [29 8] [30 8] [31 8])
Заключение
Будьте крайне осторожны, если пишете собственный генератор случайных чисел для критичных данных. Взятие за основу безопасных генераторов из коробки не гарантирует, что ваш собственный генератор будет устойчив к перебору.
Nano ID за свою простоту, минимализм и возможность адаптации к решаемой задаче (customization) получил широкую популярность. Он был портирован на множество языков программирования. Если по какой-то причине вас не устраивает UUID, а писать свой генератор вам не хочется, попробуйте Nano ID.