Генерация короткого уникального идентификатора PHP с использованием auto_increment?

StackOverflow https://stackoverflow.com/questions/1650185

Вопрос

Я хотел бы сгенерировать короткий уникальный идентификатор без необходимости проверять наличие коллизий.

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

Обычно беспокойство о коллизиях не является проблемой, но уникальный идентификатор, который я хочу сгенерировать, представляет собой короткую уникальную строку из 5-8 символов, буквенно-цифровую, как это делает tinyurl.

Редактировать:Я хотел бы начать с 5 символов, и если я наберу 60 миллионов записей, то перейду к 6..и так далее, и тому подобное.

С этой целью я подумал, что мог бы использовать значение auto_increment, которое скрыто от пользователей, и представить им вместо этого MD5 или какой-то другой метод для генерации уникальной строки из этого.

Сгенерированные строки не должны выглядеть линейными, поэтому просто преобразуйте идентификатор auto_incremented в base 36 [0-9A-Z] немного упрощенно, но я собираюсь использовать функцию, подобную этой.

Редактировать:Безопасность не является проблемой, поскольку это не будет использоваться для защиты информации.Это просто ярлык для более длинной строки.Спасибо.

Благодарим вас за ваши предложения и приносим извинения за задержку.Дантист..

Это было полезно?

Решение

Вам понадобится что-то правильное по конструкции, т.е.функция перестановки:это функция, которая выполняет взаимно однозначное обратимое преобразование одного целого числа (вашего последовательного счетчика) в другое.Несколько примеров (любая комбинация из них также должна работать):

  • инвертирование некоторых битов (например,используя XOR, ^ в PHP)
  • меняем местами биты (($i & 0xc) >> 2 | ($i & 0x3) << 2), или просто изменить порядок следования всех битов
  • добавление постоянного значения по модулю вашего максимального диапазона (должно быть в два раза больше, если вы комбинируете это с приведенными выше)

Пример:эта функция преобразует 0, 1, 2, 3, 5, ..в 13, 4, 12, 7, 15, ..для номеров до 15:

$i=($input+97) & 0xf;
$result=((($i&0x1) << 3) + (($i&0xe) >> 1)) ^ 0x5;

Редактировать

Более простым способом было бы использовать линейный конгруэнтный генератор (LCG, который обычно используется для генерации случайных чисел), который определяется формулой вида:

X_n+1 = (a * X_n + c) mod m

Для хорошие ценности из a, c и m - последовательность X_0, X_1 ..X_m-1 будет содержать все числа от 0 до m-1 ровно один раз.Теперь вы можете начать с линейно возрастающего индекса и использовать Далее значение в последовательности LCG в качестве вашего "секретного" ключа.

РЕДАКТИРОВАТЬ 2

Реализация:Ты можешь разработайте свои собственные параметры LCG, но если вы ошибетесь, это не будет охватывать весь диапазон (и, следовательно, иметь дубликаты), поэтому я буду использовать опубликованный и опробованный набор параметров здесь из этот документ:

a = 16807, c = 0, m = 2147483647

Это дает вам диапазон 2 **31.С помощью pack() вы можете получить результирующее целое число в виде строки, base64_encode() делает его читаемой строкой (до 6 значащих символов, 6 бит на байт), так что это может быть ваша функция:

substr(base64_encode(pack("l", (16807 * $index) % 2147483647)), 0, 6)

Другие советы

Вероятно, вы могли бы сгенерировать MD5-хэш текущей даты, времени / случайного числа и обрезать его до нужной вам длины (5-8 символов) и сохранить его как поле id.

Если вы используете хранение этой информации в базе данных, вам не нужно использовать цикл for для проверки коллизии, но вы могли бы просто выполнить оператор select - что-то вроде

SELECT count(1) c FROM Table WHERE id = :id

где :id будет вновь сгенерированным идентификатором.Если c больше 0, то вы знаете, что оно уже существует.

Редактировать

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

Я предполагаю, как вы сказали, кодировка base64 уже преобразует число в короткую строку.Чтобы избежать проблемы с последовательностью, у вас могло бы быть некоторое сопоставление ваших автоматически сгенерированных идентификаторов с некоторым "случайным" значением (уникальное сопоставление).Затем вы можете base64 закодировать это уникальное значение.

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

INSERT INTO MappingTable (mappedId) SELECT values FROM TemporaryTable ORDER BY RAND()

Где MappingTable будет иметь идентификатор 2 полей (ваш автоматически сгенерированный идентификатор будет сопоставляться с этим) и mappedId (для чего вы бы сгенерировали кодировку base64).

Когда вы приблизитесь к 10,000,000, вы можете снова перезапустить приведенный выше код и изменить значения во временной таблице на 10,000,001-20,000,000 или что-то в этом роде.

вы можете использовать побитовый XOR для шифрования некоторых битов: 

select thefield ^ 377 from thetable;

+-----+---------+
| a   | a ^ 377 |
+-----+---------+
| 154 |     483 |
| 152 |     481 |
|  69 |     316 |
|  35 |     346 |
|  72 |     305 |
| 139 |     498 |
|  96 |     281 |
|  31 |     358 |
|  11 |     370 |
| 127 |     262 |
+-----+---------+

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

  

MD5 возрастающего числа   должно быть хорошо, но я волнуюсь, что если   вы обрезаете свой MD5 (который   обычно 128 бит) до 5-8   персонажи, вы почти наверняка   повредить его способность действовать как   уникальная подпись ...

Совершенно верно. Особенно, если вы достигаете вероятности столкновения 80%, усеченный MD5 будет так же хорош, как любое случайное число, чтобы гарантировать уникальность, то есть бесполезную.

Но так как вы все равно используете базу данных, почему бы просто не использовать УНИКАЛЬНЫЙ ИНДЕКС? Таким образом, проверка уникальности выполняется (гораздо более эффективным способом, чем использование цикла) самой MySQL. Просто попробуйте выполнить INSERT с вашим ключом, сгенерированным MD5, и, если он потерпит неудачу, попробуйте еще раз ...

Если вы не можете использовать поле с автоинкрементом и хотите иметь абсолютно уникальное значение, используйте UUID . Если вы решите использовать что-то еще (кроме автоматического приращения), вам будет глупо НЕ проверять наличие коллизий.

В этом посте есть что-то похожее на то, что вам нужно.

http://kevin.vanzonneveld.net/techblog/article/lor_t____y_t__tube___t__t__t_ а>

MD5 с возрастающим числом должен быть в порядке, но я боюсь, что если вы урезаете свой MD5 (который обычно составляет 128 бит) до 5-8 символов, вы почти наверняка повредите его способность действовать как уникальная подпись ...

Не связан с StackOverflow
scroll top