Вероятность получения дублирующегося значения при вызове метода GetHashCode() в строках

Ответ 1

Большой.

(Извините, Джон!)

Вероятность получения хэш-столкновения между короткими строками чрезвычайно велика. Учитывая набор из десяти тысяч отдельных коротких строк, взятых из общих слов, вероятность наличия хотя бы одного столкновения в наборе составляет приблизительно 1%. Если у вас восемьдесят тысяч строк, вероятность наличия хотя бы одного столкновения составляет более 50%.

Для графика, показывающего взаимосвязь между установленным размером и вероятностью столкновения, см. мою статью по теме:

http://blogs.msdn.com/b/ericlippert/archive/2010/03/22/socks-birthdays-and-hash-collisions.aspx

Ответ 2

Маленький - если вы говорите о вероятности каких-либо двух произвольных неравных строк, имеющих столкновение. (Это будет зависеть от того, как, конечно, "произвольные" строки, в разных контекстах будут использоваться разные строки.)

Большой - если вы говорите о вероятности наличия хотя бы одного столкновения в большом пуле произвольных строк. Маленькие индивидуальные вероятности не соответствуют проблеме дня рождения.

Это обо всем, что вам нужно знать. Есть определенные случаи, когда будут столкновения, и должны быть даны, что есть только 2 ³² возможных хеш-кодов, и больше, чем много строк, поэтому принцип pigeonhole доказывает, что хотя бы один хеш-код должен иметь более одной строки, которая его генерирует. Тем не менее, вы должны верить, что хэш был разработан, чтобы быть довольно разумным.

Вы можете полагаться на него как довольно хороший способ сужения возможных совпадений для определенной строки. Было бы необычным набором естественно возникающих строк, которые порождали много столкновений - и даже когда бывают некоторые столкновения, очевидно, если вы можете сузить поиск кандидатов с 50K до менее 10 строк, это довольно большой выигрыш. Но вы не должны полагаться на него как уникальное значение для любой строки.

Обратите внимание, что алгоритм, используемый в .NET 4, отличается между x86 и x64, поэтому пример, вероятно, недействителен на обеих платформах.

Ответ 3

Я думаю, что все, что можно сказать, "мало, но конечно и не обязательно равно нулю" - другими словами, вы не должны полагаться на GetHashCode(), когда-либо возвращающем уникальные значения для двух разных экземпляров.

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

Другими словами, если два объекта имеют разные хеш-коды, вы знаете, что они разные, и не нужно (возможно, дорогого) более глубокого сравнения.

Однако, если хэш-коды для двух объектов одинаковы, вы должны продолжить сравнивать сами объекты, чтобы убедиться, что они на самом деле одинаковы.

Ответ 4

На всякий случай ваш вопрос должен состоять в том, какова вероятность столкновения в группе строк,

Для n доступных слотов и m занимающих предметы:
Проб. отсутствие столкновения при первой вставке - 1.
Проб. без столкновения на второй вставке (n - 1)/n
Проб. без столкновения на третьей вставке (n - 2)/n
Проб. (n - (m - 1))/n

Вероятность отсутствия столкновения после m вставок является произведением вышеуказанных значений: (n - 1)!/((n - m)! * n ^ (m - 1)).

что упрощает (n выбирает k)/(n ^ m).

И все правы, вы не можете предположить 0 столкновений, поэтому, говоря, что вероятность "низкая" может быть правдой, но не позволяет предположить, что конфликтов не будет. Если вы смотрите на хэш-таблицу, я думаю, что в стандарте вы начинаете испытывать проблемы со значительными столкновениями, когда у вас есть хеш-таблица размером около 2/3.

Ответ 5

Вероятность столкновения между двумя случайно выбранными строками равна 1 / 2^(bits in hash code), если хеш является совершенным, что маловероятно или невозможно.