ハッシュ値の使い方について

モバイル基盤グループのヴァンサン(@vincentisambart)です。

先日以下のツイートを拝見しました。

Swift's stdlib moves to randomly seeded hashing: https://t.co/2T5oRYtD8B

— ericasadun (@ericasadun) 2018å¹´3月10æ—¥

この変更はSwift 4.1にはまだ入りませんが、4.2か5.0に入るはずです。コードレビューでこの変更が問題を起こそうなコードを指摘したことあるので、ハッシュ値のおさらいをする良いタイミングではないでしょうか。

Swiftのことを考えて書いていますが、多くのプログラミング言語にも当てはまります。ハッシュ値はSwiftではhashValueというプロパティが返しますが、多くの言語では単にhashというメソッド・関数が返します。

ハッシュマップ

ハッシュ値はハッシュマップ(別名ハッシュテーブル)に一番使われるのではないでしょうか。SwiftではDictionary、RubyではHash、C++ではunordered_map、RustではHashMapと呼ばれるものです。

ハッシュマップはマップの一種であって、マップというのはキーに値を結びつけるためのものです。1つのキーに1つの値しか結びつけない場合が多いです(値は配列を使えますが)。例えば漫画の連載開始の年のマップを作ると以下のようになります。

キー	値
ONE PIECE	1997
DRAGON BALL	1984
青の祓魔師	2009
Levius	2012
宇宙兄弟	2007

ハッシュマップは基本的にキーに順がない場合が多いです。キーが挿入された順で列挙されると保証する実装(例えばRubyのHash)もありますが。

ハッシュマップのキーに一番使われるのは文字列ですが、以下の2つの条件を満たせば何でも使えます。

• 2つのキーが等しいかどうか比較できる(SwiftではEquatableというプロトコルに準拠すること)
• キーからハッシュ値を計算できる(SwiftではHashableというプロトコルに準拠すること。比較できないとハッシュ値が使い物にならないのでHashableはEquatableに準拠している)

ハッシュマップは別のマップの種類に比べてどういうメリットあるかと言いますと、ハッシュ関数(ハッシュ値を計算する関数)が良ければ、キーが多くても値を早く取得できるところです。

ハッシュ値とそれを生成するハッシュ関数

ハッシュマップに使われるハッシュ値は基本的に32-bitか64-bitの整数です。ハッシュ値を元にキーと値がメモリ上どこに置かれるのか決まります。

ハッシュマップで使うには、ハッシュ値が以下の条件を満たす必要があります。

• プログラムが終了するまで、ハッシュ関数(ハッシュ値を計算する関数)に同じキーを渡すと必ず同じハッシュ値が返るべき
• ハッシュ値が違っていれば、ハッシュ関数に渡されたキーが異なるべき
• 違う2つのキーが同じハッシュ値を持っても良い。可変長の文字列から計算されるハッシュ値が固定長数バイトだけに収まるので、すべてのキーが違うハッシュ値を持つはずがありません。

上記の条件を満たす一番シンプルなハッシュ関数が固定値を返すだけです。それだとハッシュマップは一応動きますが、性能がすごく落ちて、ハッシュマップを使うメリットがなくなります。

ハッシュ値を計算するハッシュ関数なんですが、良いハッシュ関数はハッシュ値の計算が速くて、色んなキーを渡すとできるだけ違うハッシュ値を返してくれた方がハッシュマップの性能が出ます。良いハッシュ関数を作るのはすごく大変なので、既存の研究されたものが使われる場合が多いです。

気を付けるべきところ

ハッシュ値が満たすべき条件に「プログラムが終了するまで、ハッシュ関数に同じキーを渡すと必ず同じ値が返る」と書きましたが、「プログラムが終了するまで」が重要です。プログラムをまた実行すると変わる可能性があります。Rubyで試してみると分かりやすいと思います。

$ ruby -e 'p "abcd".hash'
-2478909447338366169
$ ruby -e 'p "abcd".hash'
3988221876519392566
$ ruby -e 'p "abcd".hash'
-771890369285024305

今までSwiftではプログラムを何回実行しても標準のhashValueが毎回同じハッシュ値を返していましたが、この記事の頭にリンクされていた変更でプログラムが実行される度にハッシュ値が変わるようになります。

どうして変わるようになったのかと言いますと、DoS攻撃のリスクを下がるためです。DoS攻撃というのは簡単にいうとマシンがやるべき処理に追いつけなくなることです。

ハッシュマップに同じハッシュ値を持つキーをたくさん入れると、性能がどんどんと落ちていきます。ハッシュ値を事前に予測できると同じハッシュ値を持つキーを大量用意できます。サーバーがハッシュマップのキーにしそうなもの(例えばリクエストの引数名)に用意された大量のキーを使わせてサーバーがやるべき処理に追いつかなくなります。

ハッシュ値がプログラムの実行ごとに変わると、ハッシュ値の予測がかなり困難になるのでリスクを減らせます。

ハッシュマップ

でもどうして同じハッシュ値が多いとハッシュマップの性能が落ちていくのでしょうか。理解するにはハッシュマップの仕組みをもっと細かく見る必要があります。

ハッシュマップのコアな部分が単なる配列です。配列の項目がバケット(bucket)と呼ばれています。

配列のサイズ(バケット数)に満たすべき条件が特にありませんが、基本的に項目が増えるともっと大きい配列が用意されて、以前の項目を新しい配列に移し替えます(新しい配列でバケットが変わる可能性あるので要注意)。

挿入されるキーと値がどこに入るのかはハッシュ値で決まります。バケット数がハッシュ値の数ほど多いわけではないので、モジュロ(剰余演算)を使ってバケット数以下にします。

let hashValue = key.hashValue
// 負のインデックスだと困るので絶対値を取る
let bucketIndex = abs(hashValue) % buckets.count
// ハッシュ値は後でまた計算できるけど、再計算を減らすために入れておく
buckets[bucketIndex] = Bucket(hashValue: hashValue, key: key, value: value)

0	1	2	3	4	5	6	7
空	空	空	空	空	空	空	空

ハッシュ値が-3272626601332557488のキー"ONE PIECE"を挿入すると、abs(hashValue) % 8が0なので以下のようになります。

0	1	2	3	4	5	6	7
"ONE PIECE" ↓ 1997	空	空	空	空	空	空	空

ハッシュ値が4799462990991072854のキー"青の祓魔師"を挿入すると、abs(hashValue) % 8が6なので以下のようになります。

0	1	2	3	4	5	6	7
"ONE PIECE" ↓ 1997	空	空	空	空	空	"青の祓魔師" ↓ 2009	空

ただし、それだと同じバケットに別のキーが入っていたら代入すると前のキーがなくなります。同じバケットに複数のキーが入るケースを衝突(collision)といいます。

衝突の扱いは様々あります。一番シンプルなのは連結リストや動的配列ですが、例えばキーを次に空いているバケットに入れることもあります。

ハッシュ値が4799462990991072854のキー"宇宙兄弟"を挿入すると、abs(hashValue) % 8が6なので以下のようになります。

0	1	2	3	4	5	6	7
"ONE PIECE" ↓ 1997	空	空	空	空	空	"青の祓魔師" ↓ 2009	空
						"宇宙兄弟" ↓ 2007

シンプルなハッシュマップを実装してみると以下のようになります。

import Foundation

struct SimpleDictionary<Key: Hashable, Value> {
    typealias HashValue = Int
    struct BucketElement {
        var hashValue: HashValue // キーから計算できるけど時間掛かるので残しておく
        var key: Key
        var value: Value
    }

    // 連結リストがよく使われるが、実装をもっと分かりやすくするため可変長の配列を使う
    typealias Bucket = [BucketElement]
    // 実質配列の配列
    var buckets: [Bucket]

    init() {
        // 分かりやすさのためバケット数を固定にしているが、普段キーが増えるとデータをもっと大きい配列に移し替える
        // 移し替える時、バケット数が変わってキーのバケットが変わる可能性があるのでハッシュ値を元に新しいバケットを再度計算する必要がある
        let bucketCount = 8
        buckets = Array<Bucket>(repeating: [], count: bucketCount)
    }

    subscript(key: Key) -> Value? {
        get {
            // ハッシュ値でバケットが決まる
            let hashValue = key.hashValue
            let bucketIndex = abs(hashValue) % buckets.count
            for element in buckets[bucketIndex] {
                // ハッシュ値の比較が早いのでまずハッシュ値を比較しておく
                if element.hashValue == hashValue && element.key == key {
                    return element.value
                }
            }
            return nil
        }
        set(newValue) {
            let hashValue = key.hashValue
            let bucketIndex = abs(hashValue) % buckets.count

            // キーが既に使わている場合、バケット内どのインデックスに入っているのか
            let indexInsideBucket = buckets[bucketIndex].index { element in
                element.hashValue == hashValue && element.key == key
            }

            if let nonNilNewValue = newValue {
                let newElement = BucketElement(
                    hashValue: hashValue,
                    key: key,
                    value: nonNilNewValue
                )
                if let nonNilIndexInsideBucket = indexInsideBucket {
                    // キーが既に入っているので置き換え
                    buckets[bucketIndex][nonNilIndexInsideBucket] = newElement
                } else {
                    // キーがまだ入っていなかったので、挿入
                    buckets[bucketIndex].append(newElement)
                }
            } else {
                // newValueがnilなので、削除
                if let nonNilIndexInsideBucket = indexInsideBucket {
                    buckets[bucketIndex].remove(at: nonNilIndexInsideBucket)
                }
            }
        }
    }
}

肝心なところは衝突の扱いです。同じバケットにキーが増えると、バケットに入っている項目のリストが少しずつ伸びます。項目が増えると読み込みも書き込みも比較が増えて処理が重くなります。バケットに項目が1つしかなかった場合、アクセスする時は行われるのはハッシュ値の計算1回と、ハッシュ値の比較1回と、キー自体の比較1回です。同じハッシュ値のキーが100個入っていると、全部同じバケットになるので、アクセスすると行われるのはハッシュ値の計算1回と、ハッシュ値の比較100回と、キー自体の比較100回です。100個目なので、前の99回分の挿入ももちろんあります。

逆にすべてのキーが別のバケットに入ると挿入する度に比較は各1回だけです。ですのでできるだけ多くのバケットが使われる方が性能が出ます。

コードレビューで気づいた間違い

この記事の冒頭でハッシュ値に関する間違いを指摘したと言いましたが、具体的にいうと大きい間違いが以下の2つでした。

• == の実装が hashValue を比較していただけ

struct Foo: Hashable {
    static func == (lhs: Foo, rhs: Foo) -> Bool {
        return lhs.hashValue == rhs.hashValue
    }
}

lhsとrhsが違っても、ハッシュ値が同じの可能性があります。ハッシュ値が違っていたらlhsとrhsが必ず違いますけど。

• hashValue が UserDefaults に保存されていた

UserDefaults.standard.integer(forKey: fooHashValueKey)
(...)
UserDefaults.standard.set(foo.hashValue, forKey: fooHashValueKey)

プログラムの次の実行でハッシュ値が変わる可能性があります。元からHashableの公式ドキュメントには明確に書いてありました。

Hash values are not guaranteed to be equal across different executions of your program. Do not save hash values to use in a future execution.

実際冒頭でリンクした変更がSwiftに入ったら、プログラムの次の実行でハッシュ値が変わっていない可能性が極めて低いです。

まとめ

ハッシュ値を扱っている場合、以下の項目を覚えておきましょう。

• ハッシュ値はプログラムの実行ごとに変わる可能性あるためディスクに保存してはいけない(別の実行でも同じ結果を返すハッシュ関数を意図的に使わない限り)
• 2つのキーのハッシュ値が違ったら、キーが必ず違う
• 2つのキーのハッシュ値はが同じだとしても、キーが同じだと限らない