Уникально идентифицирующие URL-адреса с одним 64-разрядным номером

Question

Это в основном математическая проблема, но очень программируемая: если у меня есть 1 миллиард строк, содержащих URL-адреса, и я беру первые 64 бита хэша MD5 каждого из них, что я бы ожидал?

Как изменяется ответ, если у меня есть только 100 миллионов URL-адресов?

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

Могу ли я лучше использовать что-то другое, кроме MD5? Имейте в виду, я не ищу безопасности, просто хорошая быстрая хеш-функция. Кроме того, хорошая поддержка MySQL в MySQL.

EDIT: not quite a duplicate

Answer 1

Если первые 64 бита MD5 составили хеш с идеальным распределением, парадокс дня рождения все равно означал бы, что вы столкнулись бы за каждые 2^32 URL-адреса. Другими словами, вероятность столкновения - это количество URL-адресов, разделенных на 4 294 967 296. См. http://en.wikipedia.org/wiki/Birthday_paradox#Cast_as_a_collision_problem.

Я бы не чувствовал себя комфортно, просто выбрасывая половину бит в MD5; было бы лучше XOR для высоких и низких 64-битных слов, чтобы дать им возможность смешать. Опять же, MD5 отнюдь не является быстрым или безопасным, поэтому я бы не стал его беспокоить. Если вы хотите ослепительную скорость с хорошим дистрибутивом, но без предлогов безопасности, вы можете попробовать 64-битные версии MurmurHash. См. http://en.wikipedia.org/wiki/MurmurHash для получения более подробной информации и кода.

Answer 2

Вы отметили это как "день рождения-парадокс", я думаю, что вы know the answer already.

P(Collision) = 1 - (2^64)!/((2^64)^n (1 - n)!) 

где n - 1 миллиард в вашем случае.

Вы будете немного лучше использовать что-то другое, чем MD5, потому что MD5 имеет pratical collusion problem.

Answer 3

Из того, что я вижу, что вам нужна хэш-функция со следующими требованиями,

1. Хэша произвольных строк длиной до 64-битного значения
   • в Хороше - Избегайте столкновения
   • Не обязательно в одну сторону (безопасность не требуется)
   • Предпочтительно быстро - это необходимый признак для приложения без охраны

Этот hash function survey может быть полезен для сверления функции, наиболее подходящей для вас.
Я предлагаю попробовать несколько функций отсюда и охарактеризовать их для вашего вероятного набора ввода (выберите несколько миллиардов URL-адресов, которые, как вы думаете, вы увидите).

Вы можете создать another column like this test survey для вашего тестового URL-адреса, чтобы охарактеризовать и выбрать из существующих или любых новых хеш-функций (больше строк в этой таблице), которые вы можете проверить. У них исходный код MSVC++ начинается с (reference to ZIP link).

Изменение хеш-функций в соответствии с вашей шириной вывода (64-бит) даст вам более точную характеристику для вашего приложения.

Answer 4

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

Вероятность остается вероятностью. Его, как бросать кости 10 или 100 раз, каковы шансы получить все шестеро? Вероятность говорит, что она низкая, но она все еще может произойти. Может быть, даже много раз подряд ...

Итак, пока birthday paradox показывает вам, как рассчитать вероятности, вам все равно нужно решить, приемлемы ли конфликты или нет.

... и столкновений приемлемы, а хеши все равно правильный путь; найти 64-битный алгоритм хеширования вместо того, чтобы полагаться на «половину-MD5», имеющую хороший дистрибутив. (Хотя он, вероятно, имеет ...)

Answer 5

Если у вас есть 2^n хэш-возможности, вероятность столкновения составляет 50% при наличии 2^(n/2) предметов.

E.G. если ваш хэш составляет 64 бита, у вас есть 2^64 хэш-возможности, у вас будет 50% вероятность столкновения, если у вас есть 2^32 элемента в коллекции.