Using Dictionary with non-"primitive" keys with custom Hashable conformance

Using Swift
1

I have a custom Hashable type whose hashability is not semantically the same as its equality. e.g:

struct Key: Identifiable {

	let id: Int
	let string: String

}

//	Equality is determined element-wise:
extension Key: Equatable {

	static func == (_ lhs: Self, _ rhs: Self) -> Bool {
		lhs.id == rhs.id && lhs.string == rhs.string
	}

}

//	Hashability is determined only by id:
extension Key: Hashable {

	func hash(into hasher: inout Hasher) {
		hasher.combine(id)
	}

}

When I use this type as a dictionary key, I expect the value lookup to be based solely on the id of the key:

var dictionary: [Key: String] = [
	.init(id: 1, string: "foo"): "abc",
	.init(id: 2, string: "bar"): "xyz",
]
//	expecting "abc" since hash values of both keys are same,
//	but received nil since keys are unequal:
let value = dictionary[.init(id: 1, string: "baz")]

Is it wrong for hashability to be semantically different from equality?

2

To quote the Swift documentation:

Hashing a value means feeding its essential components into a hash function, represented by the Hasher type. Essential components are those that contribute to the type’s implementation of Equatable . Two instances that are equal must feed the same values to Hasher in hash(into:) , in the same order.

Said differently, for your implementation to behave correctly then two objects A, B where A == B, must also satisfy the constraint that A.hashValue == B.hashValue.

The reverse is not true, A.hashValue == B.hashValue does not guarantee that A == B.

4 Likes
3

So long as the EQ/hash invariant is not broken ("equal values -> must have equal hash") you are "good" to go, just beware of the consequences of poor hash function (e.g. algorithms which are O(1) are suddenly O(n) etc).

[
    Key(id: 1, string: "1"): "1",
    Key(id: 1, string: "2"): "2",
    Key(id: 1, string: "3"): "3",
    ...
    Key(id: 1, string: "1000_000"): "1000_000",
]

dictionary[Key(id: 1, string: "XXX")] // O(n) comparisons
1 Like
4

As you noticed, this is not how things work. When hashes are equal, then equality is used to confirm whether the keys are the same. It is done this way because there is generally no guarantee for hashes to be all unique.

5 Likes
5

As an extreme example:

extension Key: Hashable {
	func hash(into hasher: inout Hasher) {
		hasher.combine(0)
	}
}

This works, you can successfully find all your elements, but Dictionaries will degrade into their worst-case: only a single bucket, from which everything is found by linear search.

2 Likes