Как сокращатель URL-адресов Google генерирует 5-значный хэш без коллизий?
Как средство сокращения URL-адресов Google может сгенерировать уникальный хеш с пятью символами без коллизий . Похоже, неизбежны коллизии, когда разные URL-адреса генерируют один и тот же хеш.
stackoverflow.com => http://goo.gl/LQysz
Также интересно то, что один и тот же URL-адрес генерирует каждый раз совершенно другой хэш:
stackoverflow.com => http://goo.gl/Dl7sz
Итак, выполнив некоторые вычисления, используя символы нижнего регистра, символы верхнего регистра и цифры, общее количество комбинаций составляет 62 ^ 5 = 916,132,832 коллизии явно должны произойти.
Как Google это делает?
1 ответ
У них есть хэш-таблица с хешем к URL.
считают количество строк в той таблице и шифруют, это с поточным шифром тогда кодирует base62.
Используя поточный шифр вместо хеша даст Вам короткий псевдослучайный вывод, который не сталкивается ни с каким предыдущим выводом, таким образом, Вы не должны проверять таблицу.