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
}

Обратите внимание на глобальную функцию для перегрузки оператора равенства (==), чтобы соответствоватьРавноправный протокол, что требуется по Hashable протоколу.

Тонкий словарь ключевой проблемы

Если я создам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 всегда возвращать уникальное значение. Например,Мэтт Томпсон говорит,

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

И уважаемый ТАК пользователь@Gaffa говорит что один из способов справиться с хеш-коллизиями

Считайте хеш-коды неуникальными и используйте средство сравнения равенства для фактических данных, чтобы определить уникальность.

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

После прочтения СвифтаDictionary вопросКак обрабатываются коллизии хешей?Я предположил, что Swift автоматически обрабатывает хэш-столкновения сDictionary, Но, видимо, это не так, если я использую пользовательский класс или структуру.

Этот комментарий заставляет меня думать, что ответ в том, как реализован протокол Equatable, но я не уверен, как мне его изменить.

func ==(lhs: MyStructure, rhs: MyStructure) -> Bool {
    return lhs.hashValue == rhs.hashValue
}

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

Что я должен сделать, чтобы определить уникальность, когда (и только когда) происходит коллизия хешей?