есть строки длиной до 100 символов, при построении строк применяется набор из 55 символов.
для каждой строки вычисляется hash, hash — 4 байтный (скажем crc32),
Как подсчитать вероятность, что в наборе из 5000 строк, окажутся 2 строки с одникаковым hash ?

Здравствуйте, Аноним, Вы писали:

А>есть строки длиной до 100 символов, при построении строк применяется набор из 55 символов.
А>для каждой строки вычисляется hash, hash — 4 байтный (скажем crc32),
А>Как подсчитать вероятность, что в наборе из 5000 строк, окажутся 2 строки с одникаковым hash ?

В первом приближении, это будет
C(H,N)/(H^N)
где
H — мощность множества значений хеша (минимум из мощности "куда" = 2^32 и мощности "откуда" = 1+55+55^2+...+55^100)
N — размер набора
C(из скольки, по сколько) — количество комбинаций, C(n,k) = n!/(k!*(n-k)!)

Здравствуйте, <Аноним>, Вы писали:


А>есть строки длиной до 100 символов, при построении строк применяется набор из 55 символов.
А>для каждой строки вычисляется hash, hash — 4 байтный (скажем crc32),
А>Как подсчитать вероятность, что в наборе из 5000 строк, окажутся 2 строки с одникаковым hash ?

Для твоего события необходимо, чтобы две строки имели одинаковый хэш и чтобы 4998 строк имели любой другой отличающийся хэш. Вероятность получения определенного хеша равна 2^-32. Вероятность неполучения определенного хэша, соответственно, 1-2^-32, т.к. получение и неполучение конкретного хеша — два несовместимых события. Вероятность получения сочетания 5000 строк, где 2 строки имеют одинаковый хеш по теории умножения вероятностей равна (2^-32)^2*(1-2^-32)^4998.
Количество сочетаний по 2 элемента из 5000 элементов будет равно 5000!/(2!*(5000-2)!)=5000*4999/2.
Таким образом по теореме сложения вероятностей, вероятность получения искомого события будет равна:
5000*4999/2*(2^-32)^2*(1-2^-32)^4998 = 6,8e-13 или 6,8e-11%

Здравствуйте, Кодт, Вы писали:

К>В первом приближении, это будет
К>C(H,N)/(H^N)
К>где
К>H — мощность множества значений хеша (минимум из мощности "куда" = 2^32 и мощности "откуда" = 1+55+55^2+...+55^100)
К>N — размер набора
К>C(из скольки, по сколько) — количество комбинаций, C(n,k) = n!/(k!*(n-k)!)

Ох неправду написал...
Выше — вероятность того, что все хеши разные. Вероятность того, что есть хотя бы одна коллизия — это 1-C(H,N)/(H^N)