Хороший алгоритм для уникальной случайной генерации идентификаторов

Мне нужно создать случайный идентификатор, буквенно-цифровой номер, 6 символов, в качестве идентификатора для службы коротких ссылок.

В настоящее время я генерирую случайный 6-символьный код, смотрю в db, чтобы узнать, использовалось ли оно раньше, и если оно есть, повторите процесс. Мне нужно, чтобы он был уникальным для всех комбинаций 36 ^ 6. По мере роста системы ухудшается ее производительность.

Известен ли хороший подход, который минимизирует попадание в db, сохраняет состояние во всем мире и не займет больше 100 мс для поиска?

спасибо для любой помощи

Ответ 1

Эта проблема имеет хорошо известное решение:

http://en.wikipedia.org/wiki/Linear_congruential_generator

Просто сгенерируйте следующее случайное число с помощью LCG, затем преобразуйте его в базу 36 и напишите соответствующую псевдослучайную строку.

Удачи!

Ответ 2

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

Чтобы сделать этот последовательный идентификатор буквенно-цифровым, преобразуйте его в базу 36.

Если вам не нравится тот факт, что первые назначенные идентификаторы будут выглядеть как 000000, 000001,... 00000z, 000010,..., вы можете использовать математический трюк: внутренне сохраняйте последовательный, числовой идентификатор, но для внешнего представления, видимого пользователю, умножьте его (mod 36 ^ 6) на большое простое, меньшее 36 ^ 6-1 - 1679979167, было бы достойным выбором - до преобразования в base 36. Это сделает ваши идентификаторы случайными для пользователя, даже если они действительно не являются.

Здесь образец python с выходом:

def baseN(num,b,numerals="0123456789abcdefghijklmnopqrstuvwxyz"):
    return ((num == 0) and numerals[0]) or (baseN(num // b, b, numerals).lstrip(numerals[0]) + numerals[num % b])

for internalID in range(1,200):
    mangled = (internalID*1679979167)%(36**6)
    print internalID, mangled, baseN(mangled,36)

(код baseN - jellyfishtree из здесь)

1 1679979167 rs7s7z
2 1183175998 jkfkfy
3 686372829 bcncnx
4 189569660 34v4vw
5 1869548827 ux2x3v
6 1372745658 mpapbu
7 875942489 ehihjt
8 379139320 69q9rs
9 2059118487 y1y1zr
10 1562315318 pu5u7q
11 1065512149 hmdmfp
12 568708980 9eleno