Как обрабатывать хеш-коллизии?

Question

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

Каждый из этих идентификаторов имеет размер 64 бита и генерируется путем хеширования времени создания, сетевого адреса машины и случайного числа. Согласно статье Википедии о проблеме дня рождения, вероятность коллизии хэшей составляет 0,1% для двухсот миллионов записей.

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

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

Как я могу справиться с хеш-коллизиями? Как они обычно обрабатываются?

Answer 1

Обычно коллизии хешей обрабатываются двумя способами:

1. Используйте больший хеш, так что столкновения практически невозможны.

2. Считайте хеш-коды неуникальными и используйте средство сравнения равенства для фактических данных, чтобы определить уникальность.

128-битный GUID использует первый метод. HashSet<T> Класс в.NET является примером второго метода.