Однозначное определение URL с одним 64-разрядным числом
Я недавно провел несколько дней, работая над автоматизацией развертывания в моей компании.
Мы используем комбинацию CruiseControl, NAnt, MSBuild для генерации версии выпуска приложения. Тогда отдельный сценарий использует MSDeploy и XCopy, чтобы скопировать живой сайт и передать новые файлы.
Наше решение кратко описано в ответе на этот вопрос , Автоматизируют Развертывание для веб-приложений?
5 ответов
Если бы первые 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.
Вы отметили это как «парадокс дня рождения», я думаю, вы уже знаете ответ .
P(Collision) = 1 - (2^64)!/((2^64)^n (1 - n)!)
где n - 1 миллиард в вашем случае.
Вам будет немного лучше использовать что-то другое, кроме MD5, потому что MD5 имеет практическую проблему сговора .
Просто используя хэш, всегда есть вероятность коллизий. И вы заранее не знаете, произойдут ли столкновения один или два, или даже сотни или тысячи раз в вашем списке URL-адресов.
Вероятность остается всего лишь вероятностью. Это все равно что бросить кости 10 или 100 раз, каковы шансы получить все шестерки? Вероятность говорит, что она мала, но все же может случиться. Может быть, даже много раз подряд ...
Итак, хотя парадокс дня рождения показывает вам, как вычислять вероятности, вам все равно нужно решить, допустимы ли столкновения или нет.
... и коллизии приемлемы, и хэши по-прежнему верный путь; найдите 64-битный алгоритм хеширования вместо того, чтобы полагаться на "половину MD5", имеющую хорошее распределение. (Хотя, наверное, ...)
Насколько я понимаю, вам нужна хеш-функция со следующими требованиями:
- Хеширование строк произвольной длины в 64-битное значение.
- Будьте добры - избегайте коллизий
- Не обязательно одностороннее (безопасность не требуется)
- Желательно быстро - что является необходимой характеристикой для приложений, не связанных с безопасностью.
Это обзор хэш-функций может быть полезно для перехода к наиболее подходящей для вас функции.
Я предлагаю опробовать несколько функций отсюда и охарактеризовать их для вашего вероятного набора входных данных (выберите несколько миллиардов URL-адресов, которые, по вашему мнению, вы увидите).
На самом деле вы можете создать другой столбец, подобный этому тесту для вашего тестового списка URL-адресов, чтобы охарактеризовать и выбрать из существующих или любых новых хэш-функций (больше строк в этой таблице), которые вы, возможно, захотите проверить. Для начала у них есть исходный код MSVC ++ ( ссылка на ZIP-ссылку ).
Изменение хэш-функций в соответствии с шириной вывода (64-разрядной) даст вам более точную характеристику для вашего приложения.
Если у вас есть 2 ^ n вариантов хеширования, вероятность коллизии составляет более 50%, когда у вас есть 2 ^ (n / 2) элементов.
Например, если ваш хэш 64-битный, у вас есть 2 ^ 64 хеш-возможностей, у вас будет 50% шанс столкновения, если у вас есть 2 ^ 32 элемента в коллекции.