Set of hashable custom elements inserts equal elements-CodePudding

Setup:

I want to use a Set of the following struct:

struct NumberPair: Hashable {
    let n1: Int
    let n2: Int

    static func == (lhs: NumberPair, rhs: NumberPair) -> Bool {
        lhs.n1 == rhs.n1 && lhs.n2 == rhs.n2 ||
        lhs.n2 == rhs.n1 && lhs.n1 == rhs.n2
    }
    
    func hash(into hasher: inout Hasher) {
        hasher.combine(n1)
        hasher.combine(n2)
    }
}

I expected that inserting 2 elements that are equal (according to the function defined above) into an empty Set results in a Set with a single element:

    var pairs: Set<NumberPair> = []
//…
    pairs.insert(NumberPair(n1: 1, n2: 2))
    pairs.insert(NumberPair(n1: 2, n2: 1))

Problem:

However, at the 2nd insert I get an runtime error

Fatal error: Duplicate elements of type 'NumberPair' were found in a Set.
This usually means either that the type violates Hashable's requirements, or
that members of such a set were mutated after insertion.

When I set a breakpoint in the static func ==, this breakpoint is not hit.

Question:

Why is my custom equality function not called, and how to do it right?

CodePudding user response：

Your hash() method violates the most important requirement of the Hashable protocol:

Two instances that are equal must feed the same values to Hasher in hash(into:), in the same order.

Example:

let p1 = NumberPair(n1: 1, n2: 2)
let p2 = NumberPair(n1: 2, n2: 1)

print(p1 == p2) // true
print(p1.hashValue) // -386759992433315259
print(p2.hashValue) // -5091661336101841357

Here p1 and p2 are “equal” but produce different hash values.

The hash method must be implemented in a way that it produces the same result if n1 and n2 are exchanged, for example

func hash(into hasher: inout Hasher) {
    hasher.combine(min(n1, n2))
    hasher.combine(max(n1, n2))
}

func hash(into hasher: inout Hasher) {
    hasher.combine(n1 ^ n2)
}

Remark: The second one is simpler and perhaps faster, but more likely to cause hash collisions. struct Hasher and its combine(_:) method where introduced in Swift 4.2 (among other reasons) in order to get rid of “XOR hashing,” see SE-0206 SEHashable Enhancements.