[Coutty]

По-моему tinyurl.com никак не подбирает уникальное слово, а просто строит рандомную комбинацию из 6 символов.
1. Создать рандомную комбинацию букв латинского алфавита или использовать специальную хэш-функцию над url'ом.
2. Проверить наличие такой в базе.
3. В случае коллизии или п.1, или изменить один символ на следующий. В случае перехода на п.1 возможен очень долгий цикл, во втором случае - возникновение "кучи" и потери ценности хэш-системы. Но так ли это? Какова вероятность коллизии?

Если брать только латинский алфавит, то 26 в степени 6 = 308 млн. с хвостиком.
Если добавить к латиннице ещё и цифры, то уже 2,1 млрд. комбинаций. Думаю, этот сервис не настолько популярен, чтобы в нём часто возникали коллизии.

[Igor_I]

Да 1 пункт мало волнует, как именно создать комбинацию из 6 символов.
Вот 2 пункт, проверка, вот в чём загвоздка. Ведь 308 млн. это общее количество уникальных комбинаций, реально коллизи начнутся меньше чем через миллион комбинация. Я проверял Правда давно и результаты не помню. Проверял разницу между просто rand и функцией по созданию случайной строки при использовании rand. Создал таблицу с уникальным полем и писал туда слова. Больше миллиона слов не было. И функция выиграла. Насчёт вероятности коллизий - это всё-таки математика, я в ней не силён.
Насчёт популярности, это у нас не популярно, а у них весьма, тот же твиттер преобразовывал все ссылки через tinyurl.com.

[Coutty]

Второй пункт зависит исключительно от первого.
Хотел сейчас проверить вероятности коллизий, да после создания 16384 строк всё повисает (даже если маленькими порциями по 10000 записей добавлять). Наверное я что-то делаю не так...

И всё-таки при 36-символьном алфавите (буквы+цифры) вероятность коллизии в пределах первых десяти миллионов записей ничтожно мала. Даже если и будет - сгенерировать просто другую запись. Сколько коллизий подряд выпадет в первой сотне миллионов? Вряд ли даже 10 штук. Другой вопрос - а справится ли СУБД с обработкой таблицы на 100 (или даже 10) млн. строк?

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

[Sham]

а справится ли СУБД с обработкой таблицы на 100 (или даже 10) млн. строк? »

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

[Igor_I]

Сделал базу и таблицу с 2 полями, первое поле уникальное. Слово состоит из 6 символов. Вставленно 1.999.048 записи.
Видно, что после 1 миллиона записей время увеличивается.
Здесь 2 миллиона циклов.
На вставку 200000 записей уходит по
10% = 24.054500818253
20% = 26.072400093079
30% = 27.169686079025
40% = 27.423403024673
50% = 27.355036973953
60% = 35.397845029831
70% = 47.092970848083
80% = 62.26985001564
90% = 81.317250967026
100% = 96.546401023865

Общее время = 454.699381
memory_get_usage = 82456
memory_get_peak_usage = 107236

То есть получается пропущенно 952 цикла, выходит на 2 миллиона вариантов - 952 коллизии.

Здесь один миллион циклов.
На вставку 100000 записей уходит по
10% = 12.130727052689
20% = 13.389132976532
30% = 12.968748092651
40% = 12.946455955505
50% = 14.068972110748
60% = 13.874950885773
70% = 14.403827905655
80% = 14.447467088699
90% = 14.580943107605
100% = 15.551143884659
Вставленно записей = 999779
Общее время = 138.36254
memory_get_usage = 84204
memory_get_peak_usage = 107616

[Sham]

имхо рандом тут неудачное решение... лучше реализовать последовательное изменение автонабора символов (a, b, ..., aa, ab,..., aaa, aab,...., aaaaaa, aaaaab, aaaaac.... и тд). Последнюю сгенерированную строку хранить в другом месте, чтобы на основании ее сделать следующий набор (последняя строка мб введена юзером - при наличии фичи, как на tinyurl).

[Igor_I]

Sham, вариант интересный, до такого не додумался Насчёт фичи надо будет подумать. Скорее всего она не нужна.

[Coutty]

Я думаю, что на том же tinyurl.com специально не стали использовать последовательную выдачу. Почему - другой вопрос.

[Sham]

на том же tinyurl.com специально не стали использовать последовательную выдачу »

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