Hashable структура со сменными свойствами?

Question

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

Вот упрощенный пример, иллюстрирующий проблему:

struct MultiplicationQuestion {
    let leftOperand: Int
    let rightOperand: Int
    var answer: Int { return leftOperand * rightOperand }
}

Двумя важными свойствами для идентификации уникального MultiplicationQuestion являются leftOperand и rightOperand, но не имеет значения, в каком порядке они находятся, потому что «1 x 2» по сути тот же вопрос, что и «2 x» 1' . (По причинам, о которых я не буду здесь говорить, они должны храниться как отдельные свойства.)

Я попытался определить соответствие Hashable следующим образом, зная, что существует конфликт между равенством, как я определил его для ==, и тем, что собирается делать встроенный хэшер:

extension MultiplicationQuestion: Hashable {
    static func == (lhs: MultiplicationQuestion, rhs: MultiplicationQuestion) -> Bool {
        return (lhs.leftOperand == rhs.leftOperand && lhs.rightOperand == rhs.rightOperand) || (lhs.leftOperand == rhs.rightOperand && lhs.rightOperand == rhs.leftOperand)
    }
    func hash(into hasher: inout Hasher) {
        hasher.combine(leftOperand)
        hasher.combine(rightOperand)
    }
}

Я проверил это, создав два набора вопросов и выполнив над ними различные операции:

var oneTimesTables = Set<MultiplicationQuestion>()
var twoTimesTables = Set<MultiplicationQuestion>()
for i in 1...5 {
    oneTimesTables.insert( MultiplicationQuestion(leftOperand: 1, rightOperand: i) )
    twoTimesTables.insert( MultiplicationQuestion(leftOperand: 2, rightOperand: i) )
}

let commonQuestions = oneTimesTables.intersection(twoTimesTables)
let allQuestions = oneTimesTables.union(twoTimesTables)

Ожидаемый результат (желаемое за действительное) заключается в том, что commonQuestions содержит один вопрос (1 x 2), а allQuestions содержит девять вопросов, удалив дубликат.

Результат фактический , однако, непредсказуем. Если я бегу на игровую площадку несколько раз, я получаю разные результаты. В большинстве случаев commonQuestions.count равен 0, но иногда равен 1. И большую часть времени allQuestions.count равен 10, но иногда - 9. (Я не уверен, чего я ожидал, но это несоответствие было конечно сюрприз!)

Как я могу заставить метод hash(into:) генерировать один и тот же хеш для двух случаев, когда свойства одинаковы, но обращены?

Answer 1

Вот как работает Hasher

https://developer.apple.com/documentation/swift/hasher

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

Таким образом, проблема здесь в хеше (в :) func

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

    func hash(into hasher: inout Hasher) {
        hasher.combine(leftOperand & rightOperand)
    }

. Как указал @Martin R, чтобы было меньше столкновений, лучше использовать ^

    func hash(into hasher: inout Hasher) {
        hasher.combine(leftOperand ^ rightOperand)
    }

Answer 2

Ответ Тирана Ут (и комментарии) мне очень помог, и я пометил его как правильный.Тем не менее, я подумал, что стоит добавить еще один ответ, чтобы поделиться некоторыми вещами, которые я узнал, и представить другой способ решения проблемы.

Документация Apple hash(into:) гласит:

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

Это все хорошо, если это просто однозначноодно сравнение свойств (как показывают все примеры кода!), но что если ваш метод == имеет условную логику, подобную моей?Как вы переводите это в значение (или значения) для подачи хеша?

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

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

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

uniqueOperands = Set([leftOperand, rightOperand])

Сортированный массив тоже бы сработал, но Set казался более элегантным выбором.Поскольку в Set нет порядка, моя подробная условная логика для == (с использованием && и ||) уже аккуратно заключена в тип Set.

Теперь я могу просто использовать оченьТо же значение для проверки на равенство и для подачи хеша:

static func ==(lhs: MultiplicationQuestion, rhs: MultiplicationQuestion) -> Bool {
    return lhs.uniqueOperands == rhs.uniqueOperands
}

func hash(into hasher: inout Hasher) {
    hasher.combine(uniqueOperands)
}

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