Как обрабатываются хэш-коллизии?

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

например. Swift Dictonary использует хеш-значения с помощью своих ключей. Я предполагаю, что он просматривает свои значения через хэш. Итак, как бы Swift Dictionary сохранил значения для разных ключей, которые имеют одинаковый хэш?

Ответы

Ответ 1

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

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

Этот момент единственный способ узнать, как Swift обрабатывает столкновения, будет дизассемблировать библиотеку (то есть, если вы не работаете в Apple и не имеете доступа к исходному коду). Любопытные люди сделали это до NSDictionary и решили, что он использует линейное зондирование, самый простой вариант метода открытой адресации.

Ответ 2

Существует два основных метода:

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

Или оба.