Swift: почему требуется, чтобы тип ключа в словаре был типа Hashable
Если я хочу создать Dictionary<Key:Value>(), он необходим для объекта типа Key для протокола Hashable. Почему так, как реализованы словари?
Я имею в виду, что я бы понял, что если Key просто должен соответствовать протоколу типа Equatable, поскольку программе придется искать соответствующее значение, однако дополнительный var hashValue: Int, который поставляется вместе с Hashable, немного сбивает с толку.
Это не столько вопрос Swift, сколько общий вопрос программирования. По определению словарь - это структура данных, которая использует хэши ключей для поиска их значений.
@rmaddy имеет больше смысла :-) Почему они называют это словарем? Следует называть это HashMap, например Java
@BallpointBen Словарь (общая структура вычислительных данных, также известная как ассоциативный массив) не требует использования хэша для поиска значения, это более общий характер. Словарь - это набор пар ключ-значение, который можно использовать для хранения и поиска значений, просто имея соответствующий ключ. Хеш-часть - это оптимизация для ускорения поиска за счет реализации словаря в виде хеш-карты. С таким же успехом это может быть структура типа дерева поиска.
И «структура типа дерева поиска» потребовала бы, чтобы элементы были Comparable вместо Hashable. У каждого есть свои компромиссы. OP: Если вы ищете ассоциативный тип данных, который использует ключи Equatable, см. DictionaryLiteral, который по сути является просто оболочкой для Array<(Key: Equatable, Value)>.
Ответы 1
Хэшируемые ключи делают словарные вставки и поиск более эффективными, особенно для больших словарей.
Если ключ не является хешируемым, чтобы найти конкретный ключ, вы должны (в худшем случае) прочитать и сравнить на равенство все ключи в словаре.
Хэшируемые ключи естественным образом делятся на сегменты по их хеш-значениям, и чтобы найти конкретный ключ, вы вычисляете его хэш для определения сегмента, в котором он находится, тогда вам нужно только сравнить ключи равенства, которые принадлежат одному и тому же сегменту. Если хэш-функция выбрана правильно и количество элементов в словаре меньше максимального значения Int, у вас есть довольно хороший шанс иметь только один ключ на ведро, что делает поиск столь же эффективным, как O (1).
Больше информации в этот связанный вопрос.
Подсказка: словарь - это хеш-карта.