Как Google URL Shortener генерирует 5-значный хэш без коллизий

Question

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

stackoverflow.com => http://goo.gl/LQysz

Интересно также то, что один и тот же URL генерирует совершенно разные хэши каждый раз:

stackoverflow.com => http://goo.gl/Dl7sz

Итак, выполняя некоторые математические расчеты, используя символы нижнего регистра, символы верхнего регистра и цифры, общее число комбинаций составляет 62 ^ 5 = 916,132,832, что явно должно произойти столкновения.

Как Googleсделать это?

Answer 1

У них есть база данных, которая отслеживает все ранее сгенерированные URL-адреса и более длинные URL-адреса, на которые каждый из этих карт ссылается. Легко убедиться, что новые сгенерированные URL еще не существуют в этой таблице. Немного сложнее масштабировать (у них наверняка есть несколько серверов, поэтому каждому из них нужно назначить набор значений, из которых он может выдавать пользователям). Если они когда-либо дойдут до того, что сгенерируют 916 132 832 URL, они просто добавят еще один символ.

Answer 2

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

2. На самом деле было бы неэффективно иметь систему, предназначенную для создания «хешей» на основе заданного набора данных. Скорее, короткий URL - это просто случайный набор символов, который уже был идентифицирован как десять цифр, плюс 26 строчных букв, плюс 26 прописных букв = 916132832 перестановок (не комбинаций). Случайные короткие URL-адреса являются наиболее эффективным способом заставить его работать, и поэтому они всегда разные (хотя я полагаю, что в алгоритме может быть какой-то другой компонент, например, время суток, но я не думаю, что оно того стоит. ... нет смысла делать его таким сложным: тратить всю эту вычислительную мощность только на то, чтобы сделать глупую 5-символьную строку, которую любая обезьяна могла бы сделать, правильно нажимая кнопку на калькуляторе перестановок).