Проблемы с коллизией хэшей

Если у меня есть система, в которой хэш генерируется из общей перестановки 1 миллиона возможностей. Если вероятность столкновения составляет 10%, следует ли мне беспокоиться о том, что алгоритм генерации будет работать 5 раз?

  • У меня есть система, похожая на jsfiddle, где пользователь может «сохранить» файл на моем сервере. Теперь я использую '23456789abcdefghijkmnopqrstuvwxyz', который составляет 33 символа, а файл имеет длину 4 символа, всего 33^4 = 1,185,921 возможностей.
  • «Имя файла» генерируется случайным образом, и в случае коллизии он перезапускается, чтобы получить другое имя файла. Используя калькулятор парадокса дня рождения, я вижу, что после 500 записей у меня есть 10 % вероятность столкновения.
  • Каковы шансы, что я получу столкновение более 5 раз подряд? как насчет 4?
  • Есть ли способ выяснить это? Должен ли я беспокоиться об этом? Что происходит после 5000 записей?
  • Есть ли программа, которая может понять это с любыми произвольными входными данными?

php algorithm hash probability hash-collision
person qwertymk    schedule 18.04.2012    source источник
comment
Мне кажется, что у вас слишком маленькое пространство ключей, почему всего 4 символа? Для коротких URL?   -  person Stefan H    schedule 18.04.2012
comment
Хм, а нельзя ли использовать парадокс дня рождения, заменив 365 количеством возможных хэшей, чтобы получить свой результат? Я думаю, это дало бы вам шансы — а для 5000 хэшей шансы такие, на которые вы бы поставили деньги.   -  person ExternalUse    schedule 18.04.2012
comment
@ExternalUse Я думаю, это то, что сделал ОП. Если вы замените 365 на 1185921 и попытаетесь сгенерировать 500 значений, вероятность того, что два из них будут одинаковыми, составляет чуть менее 10%.   -  person Ted Hopp    schedule 18.04.2012
comment
О, я неправильно понял вопрос. Он хотел знать о вероятности того, что это произойдет подряд. На это мой ответ: шансы на это идентичны.   -  person ExternalUse    schedule 18.04.2012
comment
@ExternalUse вероятность того, что монета приземлится на одну сторону, равна 1/2, но вероятность того, что она дважды приземлится на одну сторону, составляет (1/2) ^ 2 = 1/4.   -  person Martin Risell Lilja    schedule 18.04.2012
comment
@noHDD - это неправильно. Вероятность приземления на определенной стороне дважды = 1/4. Вероятность выпадения (дважды решка или дважды решка) равна 1/2.   -  person Ted Hopp    schedule 18.04.2012
comment
@noHDD Разве это не 1 / (o ^ n), где o — количество возможных результатов, а n — количество последовательных событий?   -  person DaveRandom    schedule 18.04.2012
comment
Я не могу избавиться от мысли, что этот вопрос найдет лучший дом и лучшие ответы на math.stackexchange.com...   -  person DaveRandom    schedule 18.04.2012
comment
@DaveRandom Я процитирую свою книгу по математике со шведского; В соответствии с классическим определением вероятности P(решка и орел) = 1/4, потому что у нас есть только одна положительная возможность из наших четырех возможных исходов. Это то же самое, что и P(решка) * P(орел) = 1/2 * 1/2 = 1/4 = (1/2) ^ 2 = 2 ^ -2 Ваше решение тоже верное: 1 / (o ^ п) = (1/о) ^ п. Я также согласен, что это лучше подходит для математики :)   -  person Martin Risell Lilja    schedule 18.04.2012

Ответы (2)


arrow_upward
3
arrow_downward

Я не думаю, что расчеты парадокса дней рождения применимы. Существует разница между вероятностью того, что 500 случайных чисел из 1185921 будут разными, и вероятностью того, что одно новое число будет другим, если у вас есть 500 известных уникальных чисел.

Если у вас есть 500 назначенных номеров и вы генерируете новый номер случайным образом, вероятность столкновения будет равна 500/1185921. При взятии 500 имен вероятность 4-х столкновений подряд составляет (500/1185921)4 ‹ 10-13. С 5000 существующих имен файлов вероятность того, что новое имя станет конфликтом, составляет 5 000/1185 921, а вероятность 4 конфликтов подряд составляет ‹ 10-9.

person Ted Hopp    schedule 18.04.2012

arrow_upward
1
arrow_downward

Моя математика немного заржавела, так что потерпите меня.
Шанс получить x столкновений подряд просто:

chance of collision ^ x;

Где вероятность столкновения:

entries/space (which is 500/1185921 or 0.04%).

Вы можете видеть выше, что это ухудшится с большим количеством записей (и лучше с большим пространством).

Также обратите внимание, что парадокс дня рождения, возможно, не совсем то, что вам нужно. Вероятность 10 % — это вероятность того, что любые две записи столкнутся с коллизией, а не вероятность коллизии для следующей записи.

person Jim    schedule 18.04.2012