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

Question

Я хочу знать вероятность получения дубликатов при вызове метода GetHashCode() для string экземпляров.Например, согласно этому сообщению в блоге, blair и brainlessness имеют одинаковый хэш-код (1758039503) на компьютере x86.

Answer 1

Large.

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

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

График, показывающий взаимосвязь между размером набора и вероятностью столкновения, см. В моей статье на эту тему:

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

Answer 2

Маленький - если вы говорите о вероятности столкновения двух произвольных неравных строк. (Конечно, это будет зависеть от того, насколько «произвольны» строки - разные контексты будут использовать разные строки.)

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

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

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

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

Answer 3

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

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

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

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

Answer 4

Я провел тест по базе данных из 466 тыс. Английских слов и получил 48 столкновений с string.GetHashCode().MurmurHash дает немного лучшие результаты.Больше результатов здесь: https://github.com/jitbit/MurmurHash.net

Answer 5

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

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

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

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

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

Answer 6

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