Должны ли мы беспокоиться о конфликте при написании сокращающего URL-адреса, используя хеширование

Question

, думая использовать простое хеширование для создания внутреннего используемого укороченного URL-адреса. функция я строгание использовать как ниже

string s = base64Convert(md5(salt: time in million seconds)) 
    string url = s.substring(0, len: 6) 

    Map url to real url 

будет 64^6 = 68719476736 возможные комбинации. должно быть более чем достаточно для наших внутренних услуг.

однако одна вещь меня беспокоит, как я могу убедиться, что не будет дублирующего URL до 64^6 +1 хэширования времени?

любая мысль?

Answer 1

Как я могу убедиться, что не будет повторяющегося URL до 64^6 +1 хэширования времени?

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

Предполагая равнораспределенности md5, если у вас есть п адреса хэш-и добавить еще один, то есть п возможных исходов, как он будет сталкиваться и 64 - п как бы не сталкивающийся. Таким образом, вероятность столкновения для этого нового элемента равна n/64 . Это значение отличное от нуля даже для n = 1, поэтому второй URL-адрес может уже теоретически совпадать, даже если шансы на это на самом деле очень низки. Чем больше не сталкивающихся URL-адресов у вас есть в вашей базе данных, тем выше вероятность того, что новый хеш столкнется с любым существующим, пока вероятность не станет равной 100% для n = 64 .

Если вы думаете об этом, не забудьте оставить в памяти birthday “paradox”. Если у вас есть набор n URL-адресов, которые вы хотели бы добавить, то шансы любых двух из них сталкиваются с способом больше, чем шансы только последнего, столкнувшегося с любым из тех, что вы добавили до , Если вы do the math, вы обнаружите, что с использованием вашей схемы вы можете ожидать, что хеш составит около 37 000 URL-адресов, прежде чем шансы столкновения между любыми двумя из них превысят 1%.

Итак, теперь вам нужно решить, приемлема ли вероятность столкновения 1%, и достаточно ли 37 000 URL-адресов для ваших нужд. Если вероятностные результаты вас не устраивают, вы можете либо изменить шансы, например. используя более 6 цифр, или вам придется реализовать collision resolution.