Hashable struct with interchangeable properties?

Question

I need to make a custom struct conform to Hashable so that I can use it as a Dictionary key type. The challenge though, is that two of the struct's properties are interchangeable for the purpose of identifying a unique instance.

Here's a simplified example to illustrate the problem:

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

The two important properties for identifying a unique MultiplicationQuestion are leftOperand and rightOperand, but it doesn't matter what order they are in, because '1 x 2' is essentially the same question as '2 x 1'. (For reasons I won't go into here, they need to be kept as separate properties.)

I tried defining Hashable conformance as follows, knowing that there is a conflict between equality as I've defined it for == and what the built-in Hasher is going to do:

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)
    }
}

I tested this by creating two Sets of questions and performing various operations on them:

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)

The hoped-for result (wishful thinking) is that commonQuestions contains one question (1 x 2), while allQuestions contains nine questions, having removed the duplicate.

The actual result however is unpredictable. If I run the playground multiple times, I get different results. Most of the time, commonQuestions.count is 0, but sometimes it is 1. And most of the time, allQuestions.count is 10, but sometimes it is 9. (I'm not sure what I was expecting, but this inconsistency was certainly a surprise!)

How can I make the hash(into:) method generate the same hash for two instances where the properties are the same but reversed?

Answer 1

This is how Hasher works

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

However, the underlying hash algorithm is designed to exhibit avalanche effects: slight changes to the seed or the input byte sequence will typically produce drastic changes in the generated hash value.

So the problem here in hash(into:) func

Since the sequence matters combine operation is not commutative. You should find some other function to be a hash for this struct. In your case the best option is

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

As @Martin R pointed out to have less collisions it's better to use ^

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