Чтобы решить this question, я играл с настраиваемой структурой, которая реализует протокол Hashable. Я пытаюсь увидеть, сколько раз перегрузка оператора эквивалентности (==
) вызывается в зависимости от наличия хеш-коллизии или нет при заполнении Dictionary
.Как словарь использует протокол Equatable в Swift?
Update
@matt написал более чистый пример пользовательской структуры, которая реализует Hashable протокол и показывает, как часто hashValue
и ==
дозвонились. Я копирую his code ниже. Чтобы увидеть мой оригинальный пример, посмотрите edit history.
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, и все же ==
все еще вызывается. В других моих экспериментах, вызывающих столкновения хэшей (см. Историю изменений этого вопроса), ==
, казалось, называлось случайным числом раз.
Что здесь происходит?
Ненавижу давать это как ответ или даже комментарий, но это краткая внутренняя деталь реализации. Они могут оптимизировать тип, хотя они хотят, если он соответствует документированным API-интерфейсам словаря. И в документах нет никаких гарантий того, как часто ключи будут проверяться на равенство - они просто требуют, чтобы вы обеспечивали этот интерфейс '=='. Думаю, мы узнаем об этом позже в этом году, когда Swift станет открытым исходным кодом. Также см. Мой аналогичный комментарий к вашему [другому вопросу] (http://stackoverflow.com/questions/31664159/how-to-handle-hash-collisions-for-dictionaries-in-swift). – justinpawela
Вот более простой тест (я думаю): https://gist.github.com/mattneub/430fef70e3496f5ce6917aa35c98f419 Результат делает очень явным, сколько раз вызывается 'hashValue' и' == 'для каждой вставки. – matt
@matt, да, это гораздо более простой и понятный тест. Но теперь я более смущен, чем я думал. В вашем примере нет хеш-коллизий, не так ли? И все же '==' все еще вызван. Я был в предположении, что '==' получил вызов только для случаев хеш-коллизий. – Suragch