Zenn
🥇

SwiftのSetはハッシュ値がコンフリクトしたらEquatableで同値比較され、一意性が担保されている

2021/11/24に公開
iOS
Swift
tech

結論

  • タイトルの通り、 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に準拠する場合には以下を満たさなければいけない。

検証

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