Как обрабатывать коллизии хешей для словарей в Swift
TLDR
Моя пользовательская структура реализует протокол Hashable. Однако, когда при вставке ключей в Dictionaryони не обрабатываются автоматически. Как мне преодолеть эту проблему?
Фон
Ранее я задавал этот вопрос Как реализовать Hashable протокол в Swift для массива Int (пользовательская структура строк). Позже я добавил свой собственный ответ, который, казалось, работал.
Однако недавно я обнаружил небольшую проблему с hashValue столкновения при использовании Dictionary,
Самый простой пример
Я упростил код до следующего примера.
Пользовательская структура
struct MyStructure: Hashable {
var id: Int
init(id: Int) {
self.id = id
}
var hashValue: Int {
get {
// contrived to produce a hashValue collision for id=1 and id=2
if id == 1 {
return 2
}
return id
}
}
}
func ==(lhs: MyStructure, rhs: MyStructure) -> Bool {
return lhs.hashValue == rhs.hashValue
}
Обратите внимание на глобальную функцию для перегрузки оператора равенства (==), чтобы соответствовать Equatable Protocol, который требуется для Hashable Protocol.
Тонкий словарь ключевой проблемы
Если я создам Dictionary с MyStructure как ключ
var dictionary = [MyStructure : String]()
let ok = MyStructure(id: 0) // hashValue = 0
let collision1 = MyStructure(id: 1) // hashValue = 2
let collision2 = MyStructure(id: 2) // hashValue = 2
dictionary[ok] = "some text"
dictionary[collision1] = "other text"
dictionary[collision2] = "more text"
print(dictionary) // [MyStructure(id: 2): more text, MyStructure(id: 0): some text]
print(dictionary.count) // 2
равные значения хеша вызывают collision1 ключ, который будет перезаписан collision2 ключ. Там нет предупреждения. Если такое столкновение случается только один раз в словаре с 100 ключами, то его легко можно пропустить. (Мне потребовалось много времени, чтобы заметить эту проблему.)
Очевидная проблема с литералом словаря
Если я повторю это с литералом словаря, то проблема станет намного более очевидной, потому что выдается фатальная ошибка.
let ok = MyStructure(id: 0) // hashValue = 0
let collision1 = MyStructure(id: 1) // hashValue = 2
let collision2 = MyStructure(id: 2) // hashValue = 2
let dictionaryLiteral = [
ok : "some text",
collision1 : "other text",
collision2 : "more text"
]
// fatal error: Dictionary literal contains duplicate keys
Вопрос
У меня сложилось впечатление, что это не нужно для hashValue всегда возвращать уникальное значение. Например, Мэтт Томпсон говорит,
Одно из самых распространенных заблуждений относительно реализации пользовательской хеш-функции исходит из... мнения, что хеш-значения должны быть разными.
И уважаемый пользователь SO @Gaffa говорит, что одним из способов обработки коллизий хешей является
Считайте хеш-коды неуникальными и используйте средство сравнения равенства для фактических данных, чтобы определить уникальность.
На мой взгляд, вопрос: должны ли быстрые хеш-функции протокола с возможностью хэширования возвращать уникальные значения? не было должным образом ответили во время этого письма.
После прочтения Свифта Dictionary вопрос Как обрабатываются хеш-коллизии? Я предположил, что Swift автоматически обрабатывает хэш-столкновения с Dictionary, Но, видимо, это не так, если я использую пользовательский класс или структуру.
Этот комментарий заставляет меня думать, что ответ заключается в том, как реализован протокол Equatable, но я не уверен, как мне его изменить.
func ==(lhs: MyStructure, rhs: MyStructure) -> Bool {
return lhs.hashValue == rhs.hashValue
}
Эта функция вызывается для каждого поиска по словарному ключу или только в случае коллизии хешей? (Обновление: см. Этот вопрос)
Что я должен сделать, чтобы определить уникальность, когда (и только когда) происходит коллизия хешей?
4 ответа
func ==(lhs: MyStructure, rhs: MyStructure) -> Bool {
return lhs.hashValue == rhs.hashValue
}
Обратите внимание на глобальную функцию для перегрузки оператора равенства (==), чтобы соответствовать Equatable Protocol, который требуется для Hashable Protocol.
Ваша проблема - неправильная реализация равенства.
Хеш-таблица (например, Swift Dictionary или Set) требует отдельных реализаций равенства и хеширования.
хеш приближает вас к объекту, который вы ищете; равенство дает вам именно тот объект, который вы ищете.
Ваш код использует одну и ту же реализацию для хэша и равенства, и это гарантирует коллизию.
Чтобы решить проблему, реализуйте равенство, чтобы соответствовать точным значениям объекта (однако ваша модель определяет равенство). Например:
func ==(lhs: MyStructure, rhs: MyStructure) -> Bool {
return lhs.id == rhs.id
}
Я думаю, что у вас есть все кусочки головоломки, которые вам нужны - вам просто нужно собрать их вместе. У вас есть куча замечательных источников.
Хеш-коллизии в порядке. В случае коллизии хешей объекты будут проверяться на равенство (только для объектов с совпадающими хешами). По этой причине объекты Equatable соответствие должно основываться на чем-то, кроме hashValueЕсли вы не уверены, что хэши не могут столкнуться.
Это точная причина того, что объекты, которые соответствуют Hashable также должен соответствовать Equatable, Swift нужен более специфичный для предметной области метод сравнения, когда хеширование не обрезает его.
В той же статье NSHipster вы можете увидеть, как Мэтт реализует isEqual: против hash в своем примере Person учебный класс. В частности, у него есть isEqualToPerson: метод, который проверяет другие свойства человека (дату рождения, полное имя) для определения равенства.
- (BOOL)isEqualToPerson:(Person *)person {
if (!person) {
return NO;
}
BOOL haveEqualNames = (!self.name && !person.name) || [self.name isEqualToString:person.name];
BOOL haveEqualBirthdays = (!self.birthday && !person.birthday) || [self.birthday isEqualToDate:person.birthday];
return haveEqualNames && haveEqualBirthdays;
}
Он не использует хеш-значение при проверке на равенство - он использует свойства, специфичные для его класса person.
Кроме того, Swift не позволяет вам просто использовать Hashable объект как ключ словаря - неявно, по наследству протокола - ключи должны соответствовать Equatable также. Для стандартных библиотечных типов Swift об этом уже позаботились, но для ваших пользовательских типов и классов вы должны создать свой собственный == реализация. Вот почему Swift автоматически не обрабатывает словарные коллизии с пользовательскими типами - вы должны реализовать Equatable сам!
В качестве напутствия Мэтт также заявляет, что вы часто можете просто проверить личность, чтобы убедиться, что ваши два объекта находятся по разным адресам памяти и, следовательно, по-разному. В Swift это будет выглядеть так:
if person1 === person2 {
// ...
}
Здесь нет никаких гарантий, что person1 а также person2 имеют разные свойства, просто они занимают отдельное пространство в памяти. И наоборот, в более раннем isEqualToPerson: метод, нет никакой гарантии, что два человека с одинаковыми именами и датами рождения на самом деле одни и те же люди. Таким образом, вы должны рассмотреть, что имеет для вас смысл конкретного типа объекта. Опять, еще одна причина, по которой Swift не реализует Equatable для вас на пользовательских типов.
равные значения хэша приводят к тому, что ключ collision1 перезаписывается ключом collision2. Там нет предупреждения. Если такое столкновение случается только один раз в словаре с 100 ключами, то его легко можно пропустить.
Хеш-коллизия не имеет к этому никакого отношения. (Коллизии хеша никогда не влияют на результат, только на производительность.) Это работает точно так, как задокументировано.
Dictionary операции работают на равенство (==) ключей. Словари не содержат дубликатов ключей (то есть ключей, которые равны). Когда вы устанавливаете значение с помощью ключа, оно перезаписывает любую запись, содержащую равный ключ. Когда вы получаете запись с нижним индексом, он находит значение с ключом, которое не обязательно совпадает с тем, что вы дали. И так далее.
collision1 а также collision2 равны (==), исходя из того, как вы определили == оператор. Таким образом, установка записи с ключом collision2 должен перезаписать любую запись ключом collision1,
PS То же самое относится и к словарям на других языках. Например, в какао, NSDictionary не позволяет дублировать ключи, т.е. ключи, которые isEqual:, В Java Maps не позволяют дублировать ключи, т.е. ключи, которые .equals(),
Вы можете увидеть мои комментарии к ответам на этой странице и этот ответ.Я думаю, что все ответы все еще написаны ОЧЕНЬ запутанным способом.
tl; dr 0) вам не нужно писать реализацию isEqual, т.е. == между hashValues. 1) только предоставить / вернутьhashValue, 2) просто реализоватьEquatableкак обычно
0) Чтобы соответствовать hashableу вас должно быть вычисленное значение с именемhashValue и дать ему соответствующее значение.В отличие отequatable протокол, сравнение hashValues уже есть. ВамНЕ нужно писать:
func ==(lhs: MyStructure, rhs: MyStructure) -> Bool {
return lhs.hashValue == rhs.hashValue
// Snippet A
}
1) Затем он используетhashValueчтобы проверить, существует ли для этого индекса hashValue (рассчитывается по его модулю против счетчика массива) искомый ключ или нет. Он просматривает массив пар ключ / значение этого индекса.
2) Однако в качестве отказоустойчивого, то есть в случае совпадения хэшей, вы возвращаетесь к обычному == FUNC. (Логически вам это нужно из-за отказоустойчивости. Но вам также нужно, потому что протокол Hashable соответствует Equatable, и поэтому вы должны написать реализацию для ==, В противном случае вы получите ошибку компилятора)
func == (lhs: MyStructure, rhs: MyStructure) -> Bool {
return lhs.id == rhs.id
//Snippet B
}
Заключение:
Вы должны включить фрагмент B, исключить фрагмент A, а также иметь hashValue имущество