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

Question

Чтобы решить этот вопрос, я поиграл с пользовательской структурой, которая реализует протокол Hashable. Я пытаюсь увидеть, сколько раз перегрузка оператора эквивалентности (==) вызывается в зависимости от того, есть ли столкновение хешей или нет при заполнении Dictionary,

Обновить

matt написал более понятный пример пользовательской структуры, которая реализует протокол Hashable и показывает, как часто hashValue а также == позвонить Я копирую его код ниже. Чтобы увидеть мой оригинальный пример, посмотрите историю изменений.

struct S : Hashable {
    static func ==(lhs:S,rhs:S) -> Bool {
        print("called == for", lhs.id, rhs.id)
        return lhs.id == rhs.id
    }
    let id : Int
    var hashValue : Int {
        print("called hashValue for", self.id)
        return self.id
    }
    init(_ id:Int) {self.id = id}
}
var s = Set<S>()
for i in 1...5 {
    print("inserting", i)
    s.insert(S(i))
}

Это дает результаты:

/*
inserting 1
called hashValue for 1
inserting 2
called hashValue for 2
called == for 1 2
called hashValue for 1
called hashValue for 2
inserting 3
called hashValue for 3
inserting 4
called hashValue for 4
called == for 3 4
called == for 1 4
called hashValue for 2
called hashValue for 3
called hashValue for 1
called hashValue for 4
called == for 3 4
called == for 1 4
inserting 5
called hashValue for 5
*/

Поскольку Hashable использует Equatable для различения хеш-коллизий (я так или иначе предполагаю), я бы ожидал func ==() вызывается только при хеш-коллизиях. Тем не менее, в примере @ matt выше нет коллизий хешей, и все же == все еще вызывается. В других моих экспериментах форсирование коллизий хешей (см. Историю редактирования этого вопроса), == казалось, вызывали случайное количество раз.

Что здесь происходит?

Answer 1

Ну, вот ваш ответ:

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

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

---

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

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

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