Алгоритм URL-адреса YouTube?

Ответ 1

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

Этот пост Джеффа Этвуда - хороший обзор темы.

И здесь - онлайн-калькулятор хэшей, с которым вы можете играть.

Ответ 2

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

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

Например, вы можете взять монотонно увеличивающийся идентификатор базы данных и умножить его на несколько простых чисел около 2 ^ 64, а затем base64 - результат. Если вы не хотите, чтобы люди могли угадать, вы могли бы выбрать более сложное отображение или просто выбрать случайное число, которого еще нет в базе данных.

Нормальная base64 добавила бы равные в конце, но в этом случае это подразумевается, потому что размер известен. Отображение символов может легко быть чем-то помимо стандартного.

Ответ 3

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

(A-Z) + (a-z) + (0-9) + (-) + (_). (64 символа).

Используя кодировку Base64 и только до 11 символов, они могут генерировать 73+ уникальных идентификатора Quintilian. Насколько большой пул идентификаторов?

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

И они достигли такого огромного числа, используя только 11 символов (64 * 64 * 64 * 64 * 64 * 64 * 64 * 64 * 64 * 64 * 64), если им нужно больше идентификаторов, они просто должны добавить 1 больше символов к их идентификаторам.

Таким образом, когда видео загружается на YouTube, они в основном случайным образом выбирают из 73+ возможностей Quintilian и видят, если оно уже выполнено или нет. Если вы не используете его иначе, посмотрите на другой.

Подробнее об этом см. .

Ответ 4

Лучше всего, чтобы просто генерировать случайные строки и отслеживать (например, в БД), какие строки вы уже использовали, чтобы вы не дублировали. Это очень легко реализовать, и оно не может потерпеть неудачу при правильной реализации (без дубликатов и т.д.).

Ответ 5

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

Пример в PHP:

$id = 9999;
//$url_id = base_convert($id, 10, 26+26+10); // PHP doesn't like this
$url_id = base_convert($id, 10, 26+10); // Works, but only digits + lowercase

К сожалению, PHP поддерживает только до базы 36 (цифры + алфавит). База 62 поддерживает алфавит как в верхнем, так и в нижнем регистре.

Люди говорят об этих других системах:

• Случайное число/письма - Почему? Если вы хотите, чтобы люди не увидели следующее видео (id + 1), просто сделайте его закрытым. На веб-сайте, таком как youtube, где он активно показывает любое видео, которое у него есть, зачем беспокоиться о случайных идентификаторах?
• Хеширование идентификатора - эта концепция дизайна действительно воняет. Думаю об этом; поэтому у вас есть идентификатор, гарантированный вашим программным обеспечением DBM, чтобы быть уникальным, и вы хэш его (вводя коэффициент столкновения)? Дайте мне одну причину, чтобы даже рассмотреть эту идею.
• Использование идентификатора в URL-адресе. Честно говоря, я не вижу никаких проблем с этим, хотя он будет увеличиваться, если на самом деле вы можете выразить одно и то же число с меньшим количеством букв (отсюда и мое решение).
• Использование Base64 - Base64 ожидает байтов данных, буквально от нуля до пробелов. Зачем использовать эту функцию, когда ваши данные состоят из числа (т.е. Сочетание из 10 разных символов, а не 256)?

Ответ 6

Вы можете создать GUID и иметь это как ID для видео. Гиды вряд ли столкнутся.

Ответ 7

Я не думаю, что параметр URL v имеет какое-либо отношение к контенту (свойства видео, название, описание и т.д.).

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

Ответ 8

Я предлагаю использовать идеальную хэш-функцию:

Идеальная хэш-функция для кодируемых человеческих порядковых кодов

Как показывает принятый ответ, возьмите число, затем примените последовательность "биективных" (или обратимых) операций на число, чтобы получить хешированный номер.

Номера ввода должны быть в последовательности: 0, 1, 2, 3 и т.д.

Ответ 9

Просто выберите случайные значения, пока вы не увидите их раньше.

Случайная выборка и исчерпание всех значений из набора выполняется в ожидаемое время O(nlogn): Что такое значение O для наивного случайного выбора из конечного набора?

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

Ответ 10

Вероятно, у YouTube есть предварительно сгенерированная таблица базы данных со всеми возможностями от 000000 до aaaaaaa до XXXXXX. Когда создается видео, случайная строка из таблицы будет извлечена, удалена и использована для идентификатора видео. Благодаря этому методу идентификаторы будут гарантированы уникальными и случайными для людей. Таблица может быть предварительно отфильтрована в таких записях, как 00bbee!