[小ネタ]Swift4.2でのHashableの変更を整理する

Swift4.2でHashable EnhancementsというProposalが提案され、それに伴いHashableというprotocolに変更が加えられました。Hasbableをより高速に、安全に、シンプルにしたこの変更をテーマに記事を書きます。
2019.07.09

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

こんにちは。クラスメソッド福岡オフィスで iOS アプリケーションエンジニアとして働いている田辺です。

Swift4.2 でHashable Enhancementsという Proposal が提案され、それに伴い Hashable という protocol に変更が加えられました。様々な変更が Swift 4.2では加えられましたが、当面の自分のアプリ開発には影響がなさそうだったのでさらっと読んだだけで終わってしまったこの変更をきちんと腹落ちさせたいと思い、このテーマで記事を書くことにしました。

Hashable の概要

その型の値を元にハッシュ値が計算可能であることを表す型です。

ハッシュ値って何

元になるデータからある計算手順により求められた規則性のない固定長の値です。暗号や認証に使われていますが、データ構造にも応用されています。ハッシュテーブルやハッシュマップと呼ばれていて、Swift ではこれを用いて Dictionary を表現しています。

Dictionary 型

let dictionary: [String: Int] = [
    "first": 1,
    "second": 2,
    "third": 3
]

Dictionary、正確には Dictionary型で Key 型には制限があります。ハッシュテーブルにおいてキーの一意性を担保したり比較、探索ができることを保証するために Hashable に適合させています。

Swift4.1 以前、Swift4.1、Swift4.2 のHashable

Hashable protocol はより高速に、シンプルに、そしてよりセキュアになりました。

Swift4.1 以前は Hashable に conform することは面倒でした。Hashable の準拠にvar hashValue: Int { get }の実装が必要で、自前でハッシュ値を返すロジックを組まなければなりませんでした。それが Swift4.1 では Hashable に適合することで hashValue が暗黙的に実装されるようになりました。

// 4.1以前
struct Hoge: Hashable {
  var hoge: String
  var hashValue: Int {
    return // 自前でハッシュ値の計算が必要だった
  }
}

// 4.1以降
struct Hoge: Hashable {
  var hoge: String
}

ここまで hashValue のみを取り上げていましたが Hashable は Equatable(比較可能であることを表す protocol)にも準拠しているので==(_:_)の実装も必要なのですがこれも Swift4.1 以降は暗黙的に実装されます。

暗黙的に実装されるとはいえ、必要に応じて自前で実装すればそちらが優先されます。しかし自前のアルゴリズムでハッシュ値を計算してしまうとそれ自体が脆弱性になり得ます。ハッシュの衝突が起こってしまったり、良くないアルゴリズムでパフォーマンスを落としてしまうことが考えられます。

Swift4.2 からは Hashable には hash(into:)メソッドが追加されました。 そして標準のハッシュ合成関数を提供するためHasherという構造体が実装されました。 手動で実装する場合にもそれを使います。この実装により 4.2 以降は独自にハッシュ値生成を実装する時もハッシュ値生成のアルゴリズムを Swift に任せることができます。

struct User: Hashable {
    var firstName: String
    var lastName: String

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

let dictionary: [User: Int] = [
    tanabe: 1,
    konan: 2
]

また、Hasher はスタンドアロンなハッシュ値ジェネレータとしても使うことができます。

let tanabe = User(firstName: "Nobuyuki", lastName: "Tanabe")
let konan = User(firstName: "Konan", lastName: "Edogawa")

var hasher = Hasher()
hasher.combine(tanabe)
hasher.combine(konan)
let hash = hasher.finalize() // 7539258105485480683

余談ですが Swift4.2 ではswift-evolution/0202-random-unification.md at master · apple/swift-evolutionという Proposal が出されています。4.2 までの Swift ではランダム値を生成する機能を標準で持っていませんでした。arc4randomなどを持っている Foundation など、ランダム値を生成する機能を持ったモジュールを import して解決していました。4.2からは Swift がこのようなランダム値生成機能を標準で提供されました。Proposal を見ていると Swift のコアメンバーの方々がどいう意図で各言語機能を実装しているのかが垣間見えてワクワクします。本題とは逸れるのでコードは載せませんが気になる方は Proposal を参照してください。

Hasher がハッシュ値を生成する流れ

ドキュメントはHasher - Swift Standard Library | Apple Developer Documentationです。

Hasher はハッシュ値の予測可能性を低くするためランダムシード値を使用してハッシュ値を生成します。与えられたオブジェクトのハッシュ値はプログラムの実行の度に変わります。 Proposal にも以下のように記述されています。

public struct Hasher {
  public init()  // Uses a per-execution random seed value
}

Hasher はハッシュ関数の state を保存していて、combine メソッドでハッシュ関数に新しいデータを渡して、キャプチャしている state に混合します。

そして finalize()メソッドで state を確定させてハッシュ値を抽出します。このような流れで Hasher はハッシュ値を生成します。

まとめ

Swift4.1 以前、Swift4.1 以降、そして Swift4.2 と段階を踏んで変更が加えられてきた Hashable ですが比較して動かしてみると変更の理由や追加された構造体の使い方がすっきり頭に入ってきました。

Proposal には他にも Hasher を踏まえて Hashable の準拠の必要要件として hash(into:)の実装を要求する理由やどのように Hashable をより高速でシンプルな実装にしているのか詳細に解説がなされています。興味のある人はぜひ読んでみてください。