🥇
SwiftのSetはハッシュ値がコンフリクトしたらEquatableで同値比較され、一意性が担保されている
結論
- タイトルの通り、
struct Set<Element> where Element : Hashable
のような要素にHashableが求められているコレクション型での重複判定は、まずはHashable
のhashValue
での判定が行われ、もしもhashValue
がコンフリクトしている場合にはEquatable
のfunc == (lhs:rhs:)
によって同値判定が行われる。これによってSetではハッシュ値がコンフリクトしても、同値判定によって一意性が担保されている。 - Hashableを自前で実装する場合には、以下の要件を満たす必要がある。
-
a == b
ならa.hashValue == b.hashValue
になる。 -
a.hashValue == b.hashValue
の場合には必ずしもa == b
になるとは限らない。- 異なる型同士でたまたまhashValueが同一になるケースがある。
-
検証内容
きっかけ
- Hashableへの準拠は、基本的にはSwift 4.1から導入されたSynthesize conformanceによって自動的にプロトコルに準拠できるので自前で実装しなければいけないケースはほぼないが、もしも自前で実装した場合にSetの重複判定処理の挙動がどうなるのかの疑問があったので調べた。
ドキュメント
A hash value is an Int value that’s the same for all objects that compare equally, such that if a == b, the hash value of a is equal to the hash value of b.
ハッシュ値とは、すべてのオブジェクトが同じように比較できるInt値のことで、a == bの場合、aのハッシュ値はbのハッシュ値と等しいです。
- 上記とその文脈から考えるに、Hashableに準拠する場合には以下を満たさなければいけない。
-
a == b
ならa.hashValue == b.hashValue
になる。 -
a.hashValue == b.hashValue
の場合には必ずしもa == b
になるとは限らない。- 異なる型同士でたまたまhashValueが同一になるケース。
- 参考: What is the use of Hashable and Equatable in Swift? When to use which?
-
検証
Hashableに手動で準拠
struct Model: Hashable {
let int: Int
let adjustment: Int
func hash(into hasher: inout Hasher) {
// adjustmentを考慮しない
hasher.combine(int)
}
}
// hashValueは同一
assert(
Model(int: 1, adjustment: 1).hashValue == Model(int: 1, adjustment: 2).hashValue // OK
)
// EquatableはSynthesize conformanceによって実装されているので同値判定される
assert(
Model(int: 1, adjustment: 1) == Model(int: 1, adjustment: 1) // OK
)
// hashValueが同一なので重複は除外される
assert(
Set([
Model(int: 1, adjustment: 1),
Model(int: 1, adjustment: 1)
]).count == 1 // OK
)
// hashValueは同一なのに除外されていない(`func == (lhs:rhs:)` では不一致の状態)
assert(
Set([
Model(int: 1, adjustment: 1),
Model(int: 1, adjustment: 2)
]).count == 2 // <- !!!
)
HashableとEquatableに手動で準拠
struct Model: Hashable {
let int: Int
let adjustment: Int
func hash(into hasher: inout Hasher) {
// adjustmentを考慮しない
hasher.combine(int)
}
static func == (lhs: Self, rhs: Self) -> Bool {
// adjustmentを考慮しない
lhs.int == rhs.int
}
}
// adjustmentが異なるが、除外される
assert(
Set([
Model(int: 1, adjustment: 1),
Model(int: 1, adjustment: 2)
]).count == 1 // OK
)
Discussion