Role of `Equatable` conformance when inserting element inside a `Set`

Using Swift
, , ,
1

Hi all,

I am playing around with this sample code inside a Playground:

import Foundation

struct Operation: Hashable {
    let subject: String
    let type: OperationType
    
    init(subject: String, type: OperationType) {
        self.subject = subject
        self.type = type
    }
    
    static func == (lhs: Operation, rhs: Operation) -> Bool {
        lhs.subject == rhs.subject
    }
    
    enum OperationType: Hashable {
        case insert
        case update
        case delete
    }
}

var pendingOperations: Set<Operation> = []

let insertSubject1 = Operation(subject: "1", type: .insert)
insertSubject1.hashValue

let updateSubject1 = Operation(subject: "1", type: .update)
updateSubject1.hashValue

insertSubject1 == updateSubject1

pendingOperations.insert(insertSubject1)
pendingOperations.count

pendingOperations.insert(updateSubject1)
pendingOperations.count

and I noticed that sometimes the second insertion succeed (returning (inserted: true, memberAfterInsert: Operation)) and sometimes not.

If I remove the explicit Equatable conformance, or I define it in a more appropriate way like:

    static func == (lhs: Operation, rhs: Operation) -> Bool {
        lhs.subject == rhs.subject && lhs.type == rhs.type
    }

the second insertion always succeed as expected.

This led up to my questions:

  • Why is the behavior inconsistent when Equatable considers only a subset of the properties considered by Hashable ?

  • What is the role of Equatable and why is apparently not always honoured?

2

Your Equatable must match Hashable to not break the hash invariant ("equal contents → equal hash"). As you've overridden EQ you must also override hash:

    static func == (lhs: Operation, rhs: Operation) -> Bool {
        lhs.subject == rhs.subject
    }
    func hash(into hasher: inout Hasher) {
        hasher.combine(subject)
    }
3 Likes
3

Yes correct, but why, if I break the hash invariant, sometimes it behaves correctly and sometimes not?

I expected it to always behaves in the same way.

4

The Hasher instance has a different seed every time you run the program. What you’re observing could be that sometimes the hashes collide and sometimes they don’t, depending on the hash seed.

4 Likes
5

If I look at the values printed by insertSubject1.hashValue and updateSubject1.hashValue they are always different. Even when the second insertion fails.

Screenshot 2024-01-15 alle 16.53.16
Screenshot 2024-01-15 alle 16.53.162352×544 118 KB

6

Even with different hash values, the two items may end up in the same bucket of the set (= a hash collision). When that happens, Set will use == to compare the existing item(s) in that bucket with the one to be inserted. If it finds a match, it won't insert the new item.

7 Likes
7

Makes sense, thank you :slight_smile:

2 Likes