Swift Digest
SE-0206 | Swift Evolution↗

Hashable Enhancements

Proposal
SE-0206↗
Authors
Karoy Lorentey, Vincent Esche
Review Manager
Joe Groff
Status
Implemented (Swift 4.2)

01 何が問題だったのか

Swift 4.1 までの Hashable プロトコルは、Equatable に加えて hashValue: Int という1つのプロパティだけを要求していました。

struct GridPoint {
    var x: Int
    var y: Int
}

extension GridPoint: Hashable {
    var hashValue: Int {
        return x.hashValue ^ y.hashValue &* 16777619
    }

    static func == (lhs: GridPoint, rhs: GridPoint) -> Bool {
        return lhs.x == rhs.x && lhs.y == rhs.y
    }
}

一見シンプルですが、hashValue を適切に実装するのは難しく、プロトコルに適合するたびに「どの構成要素をハッシュに含めるか」を決めるだけでなく、それらを1つの Int にまとめ上げるためのハッシュ関数を毎回自前で設計する必要がありました。

この実装スタイルには、次のような深刻な問題がありました。

ハッシュ関数の自作が難しい

上の GridPoint の例はSwift 4.1のドキュメントからそのまま持ってきたものですが、x と y が小さな整数で信頼できる値源から来るなら問題ない一方で、次のような弱点があります。

  • ビット演算の意味や 16777619 のような定数の根拠が不透明で、利用者にコプライム数・ビット演算・オーバーフローといった知識を要求してしまいます。
  • 等しくないのにハッシュ値が衝突する値の組を容易に作れてしまい、信頼できない入力が与えられるケースでは衝突攻撃の標的になりえます。
  • 入力ビットの攪拌が弱く、ハッシュ値が連続的にクラスタ化してハッシュテーブルの性能を落とすことがあります。

Set / Dictionary の性能が hashValue 実装の良し悪しに依存する

Set や Dictionary はハッシュテーブルに基づくため、要素が十分にばらけるハッシュ関数が前提です。品質の悪い hashValue 実装を与えられると、本来は平均定数時間で済む操作が要素数に比例する時間に悪化してしまいます。テーブルが大きくなると、ハッシュ衝突が原因でアプリケーションやネットワークサービスが一時的に応答しなくなるような深刻な性能問題にもつながります。

標準ライブラリ側はこれに備えてハッシュ値を追加で後処理していましたが、この後処理オーバーヘッドは本来不要なコストです。

SE-0185 の自動合成で品質の高いハッシュ関数が必要になった

SE-0185 により、Swift 4.1 では条件を満たす型に対して Hashable 適合が自動合成されるようになりました。このためコンパイラと標準ライブラリは、要素数や分布によらず品質を保てる汎用ハッシュ関数を内部的に実装せざるを得ません。一方で同じ高品質なハッシュ関数を、手書きで Hashable に適合させたい利用者が再利用する手段はありませんでした。

複合型で hashValue を組み合わせると無駄が多い

hashValue は型ごとに完結した「最終的な Int」を返す契約になっているため、複合型ではサブコンポーネントの hashValue をさらに混ぜ合わせる必要があります。ハッシュ関数の「仕上げ（finalization）」処理は相対的にコストが高いため、構成要素ごとに初期化と仕上げを繰り返すと本来不要な計算が積み重なります。

以上のように、hashValue という設計は、利用者に過剰な実装責任を課しながら、標準ライブラリ側にも不要な後処理を強いるという二重の問題を抱えていました。

02 どのように解決されるのか

解決のアイデアは2つです。第1に、標準ライブラリが内部で持っている高品質な汎用ハッシュ関数を Hasher という公開型として切り出します。第2に、Hashable の要件を「完成したハッシュ値を返す hashValue」から「Hasher に構成要素を流し込む hash(into:)」へと置き換えます。

Hasher 型

Hasher は標準ライブラリが提供する汎用ハッシュ関数を表すstructで、次の3つの操作を持ちます。

public struct Hasher {
    public init() // 実行ごとにランダムなシードで初期化される

    public mutating func combine<H: Hashable>(_ value: H)
    public mutating func combine(bytes buffer: UnsafeRawBufferPointer)

    public __consuming func finalize() -> Int
}

init() で空の状態を作り、combine(_:) や combine(bytes:) でバイト列を混ぜ込み、最後に finalize() でハッシュ値を取り出します。単体では次のように使えます。

var hasher = Hasher()
hasher.combine(23)
hasher.combine(42)
print(hasher.finalize())

同じ実行中であれば、同じバイト列を同じ順序で流し込めば同じハッシュ値が返ります（順序は有意で、23 と 42 を入れ替えるとまったく違うハッシュ値になります）。ただし Hasher はプロセス起動時にランダムなシードで初期化されるため、別の実行では同じ入力でも違うハッシュ値になります。これはハッシュ値を攻撃者に予測させないための重要な性質です（従来から Hashable のドキュメントで「ハッシュ値は実行を跨いで保存するな」と明記されていた動作の延長です）。

採用されているハッシュ関数の種類や状態サイズは標準ライブラリの実装詳細であり、将来のリリースで変更される可能性があります（Swift 4.2 時点では320ビット状態のSipHash-1-3）。決定性のある動作が必要な場合は、環境変数 SWIFT_DETERMINISTIC_HASHING=1 を設定するとシードのランダム化を無効化できます。

hash(into:) 要件

Hashable プロトコルには新しい要件 hash(into:) が追加され、hashValue は非推奨になります。

public protocol Hashable: Equatable {
    var hashValue: Int { get }
    func hash(into hasher: inout Hasher)
}

新しい書き方では、型に適合する側は Hasher を自前で初期化・仕上げする必要がなく、「等価性に寄与する構成要素」を順に combine に渡すだけで済みます。

extension GridPoint: Hashable {
    func hash(into hasher: inout Hasher) {
        hasher.combine(x)
        hasher.combine(y)
    }

    static func == (lhs: GridPoint, rhs: GridPoint) -> Bool {
        return lhs.x == rhs.x && lhs.y == rhs.y
    }
}

Equatable で比較している要素と同じものを hash(into:) に渡すだけ、というシンプルな規則に収まります。

hash(into:) によるメリット

  • 発見しやすさ: 関数シグネチャに Hasher が現れるため、利用者は自然に Hasher の存在に気づけます。hashValue のように「Hasher を知っている人だけが使える」という状態になりません。
  • 攪拌品質の保証: 構成要素は常に標準ライブラリのハッシュ関数を通るため、Set / Dictionary 側が品質の悪いハッシュ値をリカバーするための後処理を省けます。
  • Hasher のカスタマイズ余地: Hasher の初期化と仕上げがハッシュ表側に移るので、たとえば Set や Dictionary のインスタンスごとに異なるシードを使って衝突攻撃耐性や性能を改善する、といった最適化がコレクション側で可能になります。
  • 性能: 複合型でも1回の初期化と1回の仕上げで済みます。たとえば GridPoint 2つからなる GridRectangle を考えると、hashValue 版は構成要素ごとに仕上げを繰り返すため合計15回分のcombine相当のコストがかかりますが、hash(into:) 版は4回のcombineと1回の仕上げの計7回分で済みます。
struct GridRectangle: Hashable {
    let topLeft: GridPoint
    let bottomRight: GridPoint

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

ソース互換性

hash(into:) の追加はプロトコル要件の追加なので、そのままでは既存コードを壊します。このため SE-0185 の自動合成が拡張され、片方だけが実装されている場合にもう片方を自動で合成するようになりました。

  • Swift 4.1 以前に書かれた hashValue のみの実装は、コンパイラが hash(into:) を hasher.combine(self.hashValue) として自動的に埋めます（Swift 4.2 モードではdeprecation warningが出ます）。
  • Swift 4.2 以降で hash(into:) のみを書いた場合は、コンパイラが hashValue を「Hasher を作って hash(into:) を呼んで finalize() する」形で自動合成します。
  • SE-0185 の自動合成要件を満たす型（stored propertyがすべて Hashable な struct、associated valueがすべて Hashable な enum など）は、どちらの実装も書かずに Hashable と書くだけで済みます。

既存コードを Swift 4.2 に移行する際は、可能なら hashValue を削除してコンパイラの自動合成に任せ、手書きが必要な場合は hash(into:) 形式へ書き換えるのが推奨されます。