CODEWITHSUNDEEP
swiftsethashable
onmyway133
onmyway133

Reputation: 48085

How does Set ensure equatability in Swift?

I'm reading Set

You use a set instead of an array when you need to test efficiently for membership and you aren’t concerned with the order of the elements in the collection, or when you need to ensure that each element appears only once in a collection.

Basically Set ensures uniqueness, it has some methods and relies on Hashable

Use the contains(_:) method to test whether a set contains a specific element.

Use the subtracting(_:) method to create a new set with the elements of a set that are not also in another set or sequence

But 2 different objects can have the same hashValue, like in this post Swift Hashable

Do not assume that two instances of a type with the same hash value are equal. Depending on how we compute the hash value we can get collisions where two different instances share the same hash value. The Hashable protocol only needs the reverse - two equal instances have the same hash value.

So what if 2 objects have the same hashValue, and Set only saves 1, then we have the problem?

Upvotes: 6

Views: 3169

Answers (2)

Maxim Golovlev
Maxim Golovlev

Reputation: 117

In order to avoid the fact that Set uses static func == to compare elements it can be done this way

extension Array where Element: Hashable {
    func subtracting(array: [Element]) -> [Element] {
        
        let hash1 = array.map({ $0.hashValue })
        let hash2 = self.map({ $0.hashValue })

        let resultSet = Set(hash2).subtracting(Set(hash1))

        let items = resultSet.compactMap({ item in self.first(where: { $0.hashValue == item }) })
        
        return items
    }
}

struct User: Hashable {
    var name: String
    var id: Int
    
    func hash(into hasher: inout Hasher) {
        hasher.combine(name)
    }
}

let array1 = [User(name: "Bob", id: 1), User(name: "John", id: 2)]
let array2 = [User(name: "Bob", id: 1), User(name: "John", id: 2), User(name: "Bob", id: 2), User(name: "Marc", id: 6), User(name: "Brian", id: 7)]

let users = array2.subtracting(array: array1)

[User(name: "Brian", id: 7), User(name: "Marc", id: 6)]

Upvotes: 0

vacawama
vacawama

Reputation: 154583

An object that conforms to Hashable must also be Equatable. Set uses == to test for equality, it doesn't depend only on the hashValue.

From Apple's documentation on Hashable:

Conforming to the Hashable Protocol

To use your own custom type in a set or as the key type of a dictionary, add Hashable conformance to your type by providing a hashValue property. The Hashable protocol inherits from the Equatable protocol, so you must also add an equal-to operator (==) function for your custom type.

The documentation goes on to say:

Set and dictionary performance depends on hash values that minimize collisions for their associated element and key types, respectively.

So, the hashValue is just used a first test for uniqueness; if the hashValues match then Set will use the more computationally expensive == to test for uniqueness.

Upvotes: 15

Related Questions