ハッシュとはぐしゃぐしゃに混ぜること

今回は，参議院予算委員会でも取り上げられたハッシュ関数（hash function）を解説します。ハッシュとは英語で「ぐしゃぐしゃに混ぜる」ことですが，なぜぐしゃぐしゃに混ぜることが現代のコンピューティングにおいて最重要な課題の1つになったのでしょうか？

まずはハッシュ関数の用途を見てみましょう。大きく2つの用途に分かれます。

• a.データの効率的検索
• b.データの改竄検出

無関係というより正反対に見えます。それではハッシュ関数とはどんな関数なのでしょう？

1. あるデータを整数値に対応
2. データが同じなら，必ず同じ数値を返す
3. データが異なっている場合は，なるべく異なる数値を返す

これだけです。この定義どおりだとすると，

func identity<T:Numeric>(x:T)->T {
  return x
}

つまり受け取った数値をそのまま返す関数もハッシュ関数ということになります。とくに3.に関してはなるべくどころか必ず異なる数値を返すという意味で完璧です。しかし全然ハッシュしてないのにハッシュ関数とはこれいかに？

あまり混ぜない「.hashValue」

しかしこれが，言葉遊びではなく実際に使われています。もちろんSwiftでも。

SwiftにはHashableというプロトコルが用意されています。このプロトコルに準拠した型は，

var hashValue:Int

というComputed Property，つまりfunctionを必ず持っています。実際に試してみましょう。

42.hashValue // 42
Double.pi.hashValue // 4614256656552045848unsafeBitCast(Double.pi, to:Int.self) //
4614256656552045848

見てのとおり，1ビットも違わず一緒です。それが何の役に立つのか。連想配列（associative array）の実装に役立つのです。これさえあれば任意のデータ構造を作れるという意味で最も便利なこのデータ構造で，JavaScriptやPHPにいたっては連想抜きの配列さえ連想配列なのですが，その連想配列を実装する最もポピュラーな方法が，添字をハッシュ関数とする連想抜きの配列，すなわちハッシュテーブル（hash table）なのです。あまりにポピュラーなのでPerlとRubyはそれを単にハッシュ（hash）と呼んでいるのですが，筆者としては列車を全部電車と呼んでいるような違和感があります。ディーゼルカーだって蒸気機関車だってあるのに……。

それはとにかく，Swiftではこのデータ構造はPython同様Dictionaryと呼ばれています。しかしその内部実装がハッシュテーブルであることは，Hashableプロトコルが如実に示しています。

ということは，オレオレハッシュテーブルも作れるということになります。やってみましょう（リスト1⁠）⁠。

struct NaiveHT<K:Hashable, V> {
    var table:[(K,V)?]
    init(count:Int) {
        table = [(K,V)?](repeating:nil, count:count)
    }
    func index(_ key:K) -> Int {
        return key.hashValue % table.count
    }
    subscript(key:K) -> V? {
        get {
            return table[index(key)]?.1
        }
        set {
            table[index(key)] = (key, newValue!)
        }
    }
}

名前からわかるとおり，実にナイーブな実装ですが，確かにDictionaryっぽく動いています。

var h = NaiveHT<Int,Int>(count: 3)
h[0]    // nil
h[0] = 1    // 1
h[0]    // 1

しかし，簡単に破綻します。

h[1] = 3
h[2] = 5
h[3] = 7
h[0] // 7

h[0]には1を代入したはずなのに，なぜ上書きされてしまったのでしょう？ index()を見てみましょう。.hashValueをtableの要素数で割っていますが，0 % 3 == 1 % 3なのでh[3] = 7で上書きされちゃったわけです。要は衝突（collision）が起きたわけです。ハッシュテーブルの実装において，最も難しいのは衝突が起きたときにどうするかですが，最もナイーブな実装としてはハッシュテーブルを作りなおすというものがあります。たとえばこんなふうに（リスト2⁠）⁠。

    func collides(key:K)->Bool {
        if let kv = table[index(key)] {
            return kv.0 != key
        }
        return false
    }
    mutating func rehash() {
        var newHT = NaiveHT<K,V>(
            count:table.count * 2 + 1
        )
        for kv in table {
            if kv != nil {
                newHT[kv!.0] = kv!.1
            }
        }
        self = newHT
    }
    subscript(key:K) -> V? {
        get {
            return table[index(key)]?.1
        }
        set {
            if self.collides(key:key) { rehash() }
            table[index(key)] = (key, newValue!)
        }
    }

あるいははじめから衝突があり得ないぐらい大きな配列を用意しとくか。しかしそれではメモリがいくらあっても足りなくなってしまいます。しかも今回は添字がIntだからいいものの，Stringだとしたらindex()ではなく.hashValueそのものが同じ値を返すことも想定しなければなりません。Intはたかだか8バイト。それより長い文字列には必ず同じ.hashValueを返す別の文字列が存在することは鳩ノ巣原理で明らかなのですから。

幸い再発明をしなくても，Swiftには最初からDictionaryが組み込まれていますし，Hashableでなければならないのはキーだけで値はなんでもありなので，ハッシュ関数を自作する必要はあまりないでしょう。どうしても必要なときは.descriptionを実装してから.description.hashValueを返すという逃げもあります。