Как обрабатываются коллизии хешей?
Недавно я немного узнал о хеш-значениях и, следовательно, также слышал о проблеме хеш-коллизий.
Поэтому я задавался вопросом: как с этим справиться?
Например, Свифт Dictonary использует хеш-значения со своими ключами. Я предполагаю, что он ищет свои значения через хеш. Так как бы Свифт Dictionary затем сохранить значения для разных ключей, которые имеют одинаковый хэш?
3 ответа
По сути, есть два основных способа обработки коллизий хеш-функции - отдельная цепочка, когда элементы со сталкивающимися хэш-кодами хранятся в отдельной структуре данных, и открытая адресация, когда коллизионные данные хранятся в другом доступном контейнере, который был выбран с использованием некоторого алгоритма.
Обе стратегии имеют множество подстратегий, описанных в Википедии. Точная стратегия, используемая конкретной реализацией, не удивительно, зависит от конкретной реализации, поэтому авторы могут изменить ее в любое время на что-то более эффективное, не нарушая предположения своих пользователей.
На данный момент, единственный способ выяснить, как Swift обрабатывает коллизии, - это дизассемблирование библиотеки (то есть, если вы не работаете в Apple и не имеете доступа к исходному коду). Любопытные люди сделали это, чтобыNSDictionaryи определили, что он использует линейное зондирование, простейшее изменение метода открытой адресации.
Есть два основных метода:
- Перефразируйте, используя другое простое число, обычно N- 2, где N - исходное простое число, выбранное таким образом, чтобы оба N и N- 2 были простыми.
- Используйте список для хэша.
Или оба.
Словари Swift используют открытую адресацию и линейное зондирование.
Вот ссылка на фактическую исходную документацию, объясняющую все: https://github.com/apple/swift/blob/master/stdlib/public/core/HashedCollections.swift.gyb