How Does Dictionary Use the Equatable Protocol in Swift

How does Dictionary use the Equatable protocol in Swift?

Well, there's your answer:

https://bugs.swift.org/browse/SR-3330?focusedCommentId=19980&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-19980

What's actually happening:

• We hash a value only once on insertion.
• We don't use hashes for comparison of elements, only ==. Using hashes for comparison is only reasonable if you store the hashes, but
  that means more memory usage for every Dictionary. A compromise that
  needs evaluation.
• We try to insert the element before evaluating if the Dictionary can fit that element. This is because the element might already be in the
  Dictionary, in which case we don't need any more capacity.
• When we resize the Dictionary, we have to rehash everything, because we didn't store the hashes.

So what you're seeing is:

• one hash of the search key
• some =='s (searching for a space)
• hashes of every element in the collection (resize)
• one hash of the search key (actually totally wasteful, but not a big deal considering it only happens after an O reallocation)
• some =='s (searching for a space in the new buffer)

We all had it totally wrong. They don't use the hashes at all — only == — to decide whether this is a distinct key. And then there is a second round of calls in the situation where the collection is grown.

Swift: equatable dictionary cannot be passed to a generic function

This is currently a limitation of Swift's type system that is well-known and on the roadmap to fix. The specific feature being discussed to fix this is "conditional conformance" to protocols for generic types. In essence, the Dictionary type can't be universally declared Equatable, because you don't know up front how to compare every possible type of value it may hold (some of which might not themselves be Equatable).

Conditional conformance would allow you to create an extension that says that Dictionary sometimes conforms to Equatable, specifically under the condition when its Value type is Equatable. And in that case, Dictionary equality can be defined as a function that compares the equality of all keys and all values in both Dictionary instances being checked.

Here is a summary of this feature and others under consideration:

https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-

Until this type system upgrade is implemented though, there is unfortunately no way to treat any Dictionary as Equatable directly. You can however create Equatable-conforming wrapper types around Dictionaries, or overload your setEquatable function to also accept Dictionaries with Equatable values and handle accordingly.

Comparing dictionaries containing actually equatable types, based on non-equatable data structures

The == operator for dictionaries requires that both Key and Value
type conform to Equatable.

You have implemented a (restricted) == operator for SortedList<Element>.
But implementing a == operator for a type does not make that type
Equatable automatically. The conformance must be declared explicitly.

Unfortunately, it is (currently) not possible to make SortedList<Element> conform to Equatable only if Element
is Equatable. The same problem exists for arrays, compare
Why can't I make Array conform to Equatable? for a discussion
in the Apple developer forum.

The only solutions – as far as I know – are to make SortedList<Element>
conform to Equatable unconditionally (as in Cristik's answer), or to define
a custom comparison operator for dictionaries

func ==<Key : Equatable, T : Equatable>(lhs: [Key : SortedList<T>], rhs: [Key : SortedList<T>]) -> Bool {
    // ...
}

Extension for sequences of dictionaries where the values are Equatable

A [String: Equatable] is a mapping of strings to any Equatable type. There is no promise that each value be the same equatable type. That said, it's not actually possible to create such a dictionary (since Equatable has an associated type), so this extension cannot apply to any actual type in Swift. (The fact that you don't receive an error here is IMO a bug in the compiler.)

The feature you'd need to make this work is SE-0142, which is accepted, but not implemented. You currently cannot constrain an extension based on type constraints this way.

There are many ways to achieve what you're trying to do. One straightforward way is to pass your equality function:

extension Sequence {
    public func removeDoubles(with equal: (Iterator.Element, Iterator.Element) -> Bool) -> [Iterator.Element] {
        var noDoubles: [Iterator.Element] = []
        for item in self {
            if !noDoubles.contains(where: { equal($0, item) }) {
                noDoubles.append(item)
            }
        }
        return noDoubles
    }
}

let noDupes = dict.removeDoubles(with: { $0["name"] == $1["name"] })

This is slightly different than your code in how it behaves when name is missing, but slight tweaks could get what you want.

That said, the need for this strongly suggests an incorrect data model. If you have this sequence of dictionaries, and you're trying to build an extension on that, you almost certainly meant to have a sequence of structs. Then this becomes more straightforward. The point of a dictionary is an arbitrary mapping of keys to values. If you have a small set of known keys that are legal, that's really a struct.

Dictionary of a protocol Swift 4

This kind of mixing protocols with class inheritance is notoriously complicated. The answer to your specific issue is you can't directly, because if you make Playable conform to Hashable, you can't make an array of them.

The simplest solution is don't use a protocol here. Just make an abstract class. Swift isn't very good at abstract classes, but they will make most of these problems go away.

Given your specific case, I might also consider using an enum for Playable rather than a protocol. That would likely make things simpler.

From there, the solutions get a bit more complicated. For example, you could create a ClassDictionary along the lines of my ClassSet experiment. Or you can build a type-eraser. But it gets ugly.

You could also consider switching from a class to a struct, and getting rid of the Dictionary, and just using an Array. If the point of the Int is a count, then just have multiple copies of the struct. If the point of the Int is a parameter (like "how much damage"), then that should be inside the Damage struct, not in a dictionary.

(Unrelated note, your hash values are very strange. They'll work, but this isn't how hashes are meant to function.)

As an example of where I'm going with this, I'm seeing something like:

protocol Playable {
    func play(game: Game) -> Player
}

struct Damage: Playable {
    let amount: Int

    func play(game: Game) -> Player {
        // do stuff
        return game.activePlayer
    }
}

struct DrawACard: Playable {
    func play(game: Game) -> Player {
        // do stuff
        return game.activePlayer
    }
}

struct Card {
    let id: Int
    let name: String
    let cost: Int
    let description: String
    let cardType: CardType
    let target: Target
    let abilities: [Playable]
}

// A card that inflicts one damage
let card = Card(id: 1,
                name: "Strike",
                cost: 1,
                description: "Strike 'em",
                cardType: CardType(),
                target: Target(),
                abilities: [Damage(amount: 1)])

This switched everything to immutable structs on purpose; I believe everything you're describing here are really value types.

What is the use of Hashable and Equatable in Swift? When to use which?

When you conform to Hashable, you provide a method that returns the hash value of self.

When you conform to Equatable, you provide a method that returns whether the given object and self are equal.

They seem to serve two very different purposes, why does Hashable inherit Equatable? Because the hash values for two equal objects are equal!

What can and can't you do with Hashable and Equatable?

Equatable has more limited uses than Hashable. It can only compare the equality of two objects, and that's it.

For Hashable, because you can get a number that represents the object, you can kind of treat the objects as numbers. You can compare the objects: whether it is less than, greater than, or equal to another object, just like you do with numbers:

if objA.hashValue > objB.hashValue

This also means you can sort objects with Hashable.

Last but not least, you can use Hashable objects as keys for maps! this is because maps' keys cannot duplicate, so how can the system check whether you put a duplicate item in it? It uses the hash values of the keys!

---

Related Topics