Уникальная идентификация URL-адресов с помощью одного 64-битного числа.

Question

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

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

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

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

РЕДАКТИРОВАТЬ: не совсем дубликат

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

Вы отметили это как «парадокс дня рождения», я думаю, вы уже знаю ответ.

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

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

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

Answer 3

Насколько я вижу, вам нужна хеш-функция со следующими требованиями:

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

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

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

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

Answer 4

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

НАПРИМЕР.если ваш хеш составляет 64 бита, у вас есть 2 ^ 64 возможности хеширования, у вас будет 50% вероятность столкновения, если у вас есть 2 ^ 32 элемента в коллекции.

Answer 5

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

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

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

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