Dictionary.Keys equatable conformance is unreliable

I've noticed some very troubling inconsistencies when creating a case insensitive dictionary key. Here is a simple implementation:

struct HTTPHeaderField: Hashable, ExpressibleByStringLiteral {

    static func == (lhs: Self, rhs: Self) -> Bool {
        lhs.value.compare(rhs.value, options: .caseInsensitive) == .orderedSame
    }
    
    var value: String

    ...
}

typealias HTTPHeaders = [HTTPHeaderField: String]

Now I wanted to make sure this work so I loaded up a Playground. Keep in mind I've left out some routine initialisers.

let a: HTTPHeaders = ["max_id": "3"]
let b: HTTPHeaders = ["max_ID": "3"]

print(a == b) // sometimes true, sometimes false 🤷🏼‍♂️

It's very bizarre. I can run it multiple times in the Playground without changing any code or string literals and I get different answers. I've tried simply forwarding the Hashable conformance to value with the same results.

I added some simple print statements to better understand what is happening and occasionally, the custom implementation of == is not called and false is returned by some other function. How can this be inconsistent?

This kind of unreliable behaviour across executions seems very troubling, almost too troubling to the point I'm thinking I'm the source of the error. Is there something I've overlooked in my simple implementation?

Did you also implement hash(into:), which is a requirement for Hashable?

5 Likes

Yup. I've tried both the default compiler generated implementation and also forwarding hash(into:) to value:

func hash(into hasher: inout Hasher) {
    value.hash(into: &hasher)
}

Same results though.

You need to canonicalize the representation before hashing it, possibly by converting the text to all-lowercase or all-uppercase:

(value as NSString).lowercased.hash(into: &hasher)

Otherwise you'll have two equal instances with different hashes, which breaks the Hashable contract. Since you use NSString.compare, I use NSString.lowercased instead of String.lowercased for good measure.

8 Likes

Just hit Run about 15 times using value.lowercased().hash(into: &hasher) and it's consistently correct. I was really confused by the inconsistencies, thanks for the assistance.

1 Like

Dictionary requires that Key is Hashable. That's why breaking Hashable contract results in unexpected/undefined behaviour.

PS

Maybe this should be moved to Using Swift?

Ya, I read more than I post so I'm a little unfamiliar with how filing works here. I'll see what I can do about that :wink:

I wrote a little post recently the explains how dictionaries are implemented, how equatable and hashable are used, and the kinds of errors can happen if they're improperly implemented. You might find it interesting.

Check it out:

The last section isn't entirely accurate. Equal objects must have equal hashes, but unequal objects don't necessarily have different hashes. It's OK if the properties used in the hashing procedure is a strict subset of the ones used for equality. (But definitely not the other way around; the hashed properties can't be a strict superset of the equality-checking ones.)

2 Likes

Good catch! Darn I tried so hard not to mix these up. I'll take that section down until I fix it.