Как словарь использует протокол Equatable в Swift?

Ответ 1

Ну, вот твой ответ:

https://bugs.swift.org/browse/SR-3330?focusedCommentId=19980&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-19980

Что на самом деле происходит:

• Мы хэшируем значение только один раз при вставке.
• Мы не используем хеш для сравнения элементов, только ==. Использование хэшей для сравнения целесообразно только в том случае, если вы храните хэши, но это означает больше использования памяти для каждого словаря. Компромисс, который требует оценки.
• Мы пытаемся вставить элемент перед оценкой, может ли Словарь соответствовать этому элементу. Это потому, что элемент уже может быть в Словаре, и в этом случае нам больше не нужны возможности.
• Когда мы изменяем размер словаря, мы должны перефразировать все, потому что мы не сохранили хэши.

Итак, что вы видите:

• один хеш ключа поиска
• некоторые == (в поисках пробела)
• хэши каждого элемента в коллекции (изменить размер)
• один хеш ключа поиска (на самом деле совершенно бесполезный, но не страшно, учитывая, что это происходит только после перераспределения O👎)
• some == (поиск пробела в новом буфере)

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

Ответ 2

Я копирую свой ответ из bugs.swift.org здесь. Он говорит о наборах, но эти данные относятся к словарям одинаково.

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

Причина, по которой вы все еще видите больше вызовов ==, чем вы ожидали бы, если количество кодов равно или больше числа элементов, связанных с детализацией реализации вычисления индекса ведра. Биты hashValue смешиваются или "перетасовываются" перед операцией modulo. Это должно сократить чрезмерные столкновения для типов с неправильными алгоритмами хеширования.

Ответ 3

Хотя на этот вопрос уже был дан ответ, эти ответы подняли некоторые дополнительные вопросы в комментариях. @Suragch спросил, включу ли я свои комментарии в новый ответ, чтобы помочь другим, которые также могут быть смущены отношениями между Equatable и Hashable. Я должен начать с того, что говорю, что у меня есть только элементарное понимание основной механики, но я сделаю все возможное, чтобы объяснить то, что я знаю.

Equatable - довольно простая концепция, и нам не нужно смотреть дальше, чем документы Swift, для краткого определения этого протокола:

Уравниваемый: тип, который можно сравнивать на равенство значений.

Если тип уравниваем, мы можем сравнить два экземпляра с ==. Легко.

Hashable это Hashable история. Я на самом деле громко рассмеялся, когда впервые прочитал определение этого протокола в документации Swift:

Hashable: тип, который может быть хеширован в Hasher для получения целочисленного значения хеша.

Если это не прояснило для вас, вы не одиноки! И в любом случае, если == используется для определения того, является ли экземпляр действительно уникальным (какой он должен быть в наборе или когда используется в качестве ключа в словаре), зачем вообще нужен Hashable? (Это вопрос, который @Suragch задал в комментариях.)

Этот вопрос касается фундаментальной природы хэшированных коллекций (или хеш-таблиц), таких как наборы и словари. Подумайте, почему вы можете выбрать словарь над массивом в первую очередь. Вы выбираете словарь, когда вам нужно найти или сослаться на экземпляр по чему-то другому, кроме известного индекса, верно? В отличие от массива, элементы словаря не нумеруются последовательно, что затрудняет поиск вещей. Если бы все, что у нас было, это ==, нам пришлось бы перебирать элементы нашего словаря, один за другим, и это становилось бы все медленнее и медленнее с увеличением размера словаря.

Вот где приходит магия хеш-функций. Хеш-функция (или хэш-функция) принимает уникальный ключ в качестве аргумента и возвращает адрес элемента. Как вы можете быть уверены, что он вернет правильный адрес? Потому что это та же самая функция, которая использовалась для установки этого адреса в первую очередь! Когда словарь создавался, он брал каждый ключ (или, точнее, уникально идентифицирующие свойства каждого ключа), смешивал их в соответствии с некоторой секретной формулой и выплевывал число (значение хеша) для каждого, и из этих чисел приходили новые индексы для каждого элемента. Позже, когда вы захотите найти один из этих элементов, хеш-код получает те же аргументы, поэтому он возвращает то же значение. И поскольку все, что вы делаете, это вызываете функцию, то здесь не требуется итераций, и результаты бывают быстрыми, независимо от размера коллекции.

Там подвох хотя. Нет хешера идеально. Даже если вы передадите ему уникальные аргументы, иногда он может возвращать одно и то же значение хеша для двух совершенно разных элементов - коллизия хешей. Когда это происходит, ему нужно проверить, действительно ли два элемента одинаковы, и это, конечно же, путем вызова ==.

Но в вашем примере вы напрямую манипулировали hashValue (это было то, что люди делали до появления hash(into:) !), И он все еще назывался == ! Я имею в виду, теоретически, это не должно делать это, поскольку никаких столкновений нет. Но ответ есть в комментарии, цитируемом robinkunde:

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

Хотя обычно нам не нужно беспокоиться о деталях реализации встроенной функции хеширования Swift, эта конкретная деталь важна… За кулисами хэше нужен еще один аргумент, и это размер коллекции. Если размер изменяется (как это происходит неоднократно, когда вы выполняете итерацию по диапазону и вставляете новые элементы в коллекцию), хешер может попытаться добавить больше элементов, чем есть индексированные слоты (или сегменты), и вы получите коллизия или необходимо перефразировать все с нуля с достаточным объемом памяти, чтобы дать каждому элементу уникальный индекс. То, что, кажется, случается, является комбинацией обоих, поскольку комментарий, цитируемый Мэттом, говорит:

Мы пытаемся вставить элемент перед оценкой, может ли Словарь соответствовать этому элементу. Это потому, что элемент уже может быть в Словаре, и в этом случае нам больше не нужны возможности.

Так что моя попытка более простого объяснения хэшированных коллекций, отношения между хеш-функцией и вашим методом == и причины неожиданного поведения. Но все это поднимает еще один вопрос для меня... Почему мы должны вручную объявить Hashable? Разве Apple не могла использовать какой-то алгоритм для синтеза соответствия Hashable для всех типов Equatable? Я имею в виду, что hash(into:) документация гласит:

Компоненты, используемые для хеширования, должны совпадать с компонентами, сравниваемыми в вашей реализации операторов типа ==.

Если компоненты должны быть одинаковыми, не может ли Swift определить наше намерение из нашей реализации Equatable одиночку? Я не уверен, почему он не может предложить такое удобство (аналогично тому, как он предлагает инициализаторы по умолчанию) для тех, кто не хочет большего контроля над деталями. Возможно, однажды Свифт предложит это? На данный момент, однако, они держали их как отдельные проблемы, с Hashable наследуя от Equatable.