「ハッシュ」を完全理解するための道とは

前回、エンジニアが常々お世話になる「連想配列」についてのあれこれを述べました。Rubyのシンタックスシュガーを使って、 配列を連想配列に魔改造することで、どんな性能の連想配列になるかを確かめる ことが前回の内容でした。

今回は、連想配列実装の正式な(?)方法、ハッシュテーブルを実際に作ってみよう という試みです。粗悪な性能の連想配列だけでなく、実用性の高い連想配列も、さほど長くないコードで実現できるんです。

Rubyでの実装を通じて「ハッシュ」を（なんとなくではなく）理解しよう、というのが本記事のゴールになります。

注釈 ハッシュの完全理解とは言いつつも、今回 暗号化の話には触れない ので、その旨ご注意頂ければ幸いです。 ただし、暗号化についても今回の話と基本は同一ですので、理解の助けになるはずです。

実装が理解への近道だ

筆者は学生時代にハッシュテーブルを自作して、その性能の良さ（要素へのアクセスの機敏さ）に感動した人間であることを 前回 述べました。

• Rubyの配列(Array)を魔改造して、連想配列として使ってみた

ハッシュテーブルについて書かれた（まともな）文献については、「ハッシュ」と名のつく用語が複数出てきます。ハッシュ関数、ハッシュ値、などなど。

その関連性については色々な喩えがあるものの、 keyの成績や身長などが引き合いに出され、 それ内部ロジックどーなってんのよ？ と言いたくなるような例が用いられたりしており、 「とりあえず」の理解の助けにはなるものの、エンジニアにとっては少し物足りない記述になっているように思えます。

本記事の内容は、下記の2つの項目について理解するにあたっては、なかなか良い内容なのではないかと自負しています。

1. ハッシュ関数は、文字列など仕様によって規定されるいかなるkeyも入力できる形式でなければならない
   • その役割はハッシュ値を発行し、メモリ上の要素の格納場所を決めることである
2. 異なるkeyに対するハッシュ値は、可能な限り重複がないことが望ましい
   • そのような性質を満たす「よい」ハッシュ関数のうち、極めてシンプルな実装のものも存在する（後述）

また、本記事では 下記３つの用語について、明確に区別すること をゴールとして、ハッシュテーブルの仕組みについてまとめていきます。

1. ハッシュ関数
2. ハッシュ値
3. ハッシュテーブル（ハッシュ）

最後に、ハッシュテーブルの性能について書かれた文献を読むと、たいてい 「定数時間O(1)で要素にアクセスできる（ゆえに早い、最高だ！）」 と書かれています。 一体これがどういうことなのかも、分かりやすい解説をあまり見かけたことがありません。この点にも、チャレンジしてみたいと思います。

ハッシュ関数の設計

ハッシュテーブルの実装に必要な 最重要のメソッド がハッシュ関数です。

ここでは、文字列をkeyとするハッシュテーブルをユースケースとして想定し、 ハッシュ関数をRubyのメソッドとして、一から実装してみたいと思います。

ハッシュ関数の役割 - メモリ上のどこに要素を格納するか決める

早速前回の内容を引くのですが、 配列を強引に連想配列化した MyAssociativeArrayの実装では、 「メモリ上のどこにkey, valueの組を格納するか？」という問題については触れてきませんでした。 ここで、前回実装した連想配列クラス、 MyAssociativeArrayにおける要素代入のメソッドを見直してみましょう。

ポイントは、MyAssociativeArrayクラスの継承元であるArrayクラスのpush関数を使ってkey, valueの組を格納している点です。 push関数は配列の末尾に要素を追加するメソッドなので、MyAssociativeArrayでは、新しく到着するkey, valueの組を既存要素の末尾に付け足していくという、ナイーブな方法でメモリ内に格納しています。

ハッシュテーブル実装の第一のポイントは、 メモリ内のどこに要素を格納するか？ について、もう少し計画的なやり方を用いることです。

その際に登場するのが、先述した ハッシュ関数 です。

ハッシュを噛ませた場合の実装イメージ（要素格納の方法）を上図に表してみました。

データ代入の手続き

1. あらかじめメモリ上の決まった広さの領域を確保しておく
   • 本記事ではテーブルサイズと呼ぶこととします
2. key, valueを受け取ったら、ハッシュ関数 にkeyを入力
3. ハッシュ値 を得て、1.で確保した領域のサイズTABLESIZEで割った値 offset を得ることで、メモリ上のどこに格納するかを決める

それぞれ、実際にハッシュテーブルを実装したコード（hashtable.rb）を参照しつつ、解説していきたいと思います。

今回、Arrayオブジェクトをインスタンス変数として持つMyHashTableクラスを実装することで、ハッシュテーブルの実装をしてみたいと思います。 まず、1.で述べた「決まった広さの領域を確保する」ことからです。今回は下記のように行います：

あらかじめ定めた定数 TABLESIZE の要素数をもつ配列（Arrayオブジェクト）を生成し、インスタンス変数 @arr として保持しているだけの単純なコードです。 これで、メモリ上にkey, valueの組を保持するための領域が確保されます。 （ TABLESIZEの適切な決め方については、後ほど触れたいと思います。）

次に、代入処理を見てみましょう。（上述した流れの2, 3にあたる部分です。） 代入処理ではまず、確保した配列領域のどの位置にkey, valueの組を格納するかを決定します。配列の先頭から要素いくつ分後ろに格納するかを表すoffset変数を用意し（０オリジン）、ここに数値を代入します。 （もちろん、 0 <= offset < TABLESIZEを満たすような値を与える必要があります。）

さて、肝心のoffsetの数値は下記コードで決定されています。

右辺のMyHashFunctionクラスのone_at_a_timeメソッドを呼び出し、引数としてk（key）を渡しています。それをTABLESIZEで割った値をoffsetとして採用しています。

ここで、このone_at_a_timeこそが ハッシュ関数 と呼ばれるものです。 One at a timeハッシュは、質の良いハッシュ関数について論じたJenkinsの文献（英語）に記載されている中で、もっとも古典的なハッシュ関数です。 シンプルなアルゴリズムで動作の理解が易しいこと、デモとしては十分な性能があることから、今回の目的にピッタリと判断しました。動作を理解するのに必要な知識は ビット演算のみ ですので、不慣れな方は、ビット演算に関する文献を片手に読めば十分理解できるのではないかと思います。

one_at_a_timeハッシュ関数の中身をみてみましょう。

ここで、上記コードは下記４つのステップで説明できます。

1. key文字列の先頭から1文字取り出し、文字コード化し、二進数化する（L7）
2. 1.で得られた値をhash変数に加える（L7）
3. hash変数の値をビット演算でいい感じにかき混ぜる（L8-L9）
4. 以下、文字列の末尾文字まで繰り返し
5. 得られた値を最後にもう一度かき混ぜて出力（L11-L14）

例えば、このハッシュ関数に"altus"というkeyを入力してみると、0x25746a3bという出力値が返されます。この数値を ハッシュ値 と呼びます。

ハッシュ値をTABLESIZEで割った値をoffsetとして採用することで、配列内のどの位置に要素を格納するかを決定します。

このようにしてoffsetを確定したら、その位置にkey, valueの組を格納します。 ただし、最初の実装と同様、「既にそのkeyをもつ要素が格納されていれば、値を上書きする」よう実装する必要がありますので、ロジックは若干長くなります。 下記コードのL21が、肝心の代入を行なっている箇所です。

ハッシュ関数に求められる２つの性質

1. 上記手続きには一切ランダム性がなく、同一のkeyを与えた時は必ず同じ出力値を返すこと（入力に対する出力の一意性）
2. 異なるkeyを与えたとき、同じ出力値を返す可能性が極めて低いこと

ハッシュテーブルにおける値の参照 - keyのハッシュ値で格納場所がわかる

代入の次は参照です。最初の実装では線形走査でkeyにヒットする要素を見つけていましたが、今回は代入の方法が変わったため、参照の方法が劇的に効率的になります。 ポイントは明快で、 参照にもkeyのハッシュ値を使えば良い のです。

今回、代入時の要素格納を、keyのハッシュ値に基づいて行うようロジックを変更しました。そのため、要素参照時にもハッシュ値を発行し、ハッシュ値の指す位置を調べることで、与えられたkeyをもつ要素が、既に連想配列内にあるかどうかを高速に調べることができるのです。 実装方針としては、下記の通りです。

1. keyに対応するハッシュ値からoffsetを求める
2. offsetの指す位置に、与えられたkeyを持つ要素が格納されているかどうかを調べる

「keyに対応するハッシュ値からoffsetを求める」コードは下記の通りで、代入の時と全く同一です。

「offsetの指す位置に、与えられたkeyを持つ要素が格納されているかどうかを調べる」コードは下記の通りです。

まとめると、ハッシュテーブルの実装上の工夫、およびその結果としての性能の良さ（高速さ）は、下記の文章で言い表すことができます。

• ハッシュテーブルでは、値の代入と参照を同じ手段（ハッシュ関数）を介して行うため、 １回 の等値判定で指定のkeyを持つ要素が見つかる
• 同様の理由から、指定のkeyをもつ要素が連想配列内に存在しない場合は、 １回 の等値判定でそのことがわかる
  • ただし、いずれも例外あり（後述する『衝突』が起きた場合）

このことが、 ハッシュテーブルは定数時間O(1)で値の参照/代入が可能である という文言の意味するところなのですね。

衝突(collision)とは？ - ハッシュテーブルの性能が劣化するケース

さて、上記ソースコードを載せつつさらりと流しましたが、性能に関して見過ごせない点があったことにお気づきだったでしょうか。 「ハッシュテーブルは１回の等値判定で参照/代入ができる！」などと言いつつ、 実は今回も、 参照/代入の実装において線形走査(each)を使っていた のですね。

代入

参照

さて、こちらは 衝突(collision)に対する処理 と呼ばれるもので、ハッシュテーブルに実装について書かれた文献であれば、必ず言及されている重要な処理です。

衝突とは、 相異なる複数の入力キーに対して、同じハッシュ値が発行されること、もしくは配列内の同じ位置（offset）が格納場所として指定されてしまうこと を指します。

One-at-a-timeハッシュは、古典的ながらもよく考慮されたハッシュ関数ですので、相異なる複数の入力キーに対して同じハッシュ値を発行してしまうことは稀ですが、 その出力値は 0以上2^31未満と幅が大きいことから、今回は実用上TABLESIZEを指定し、One-at-a-timeの出力値をTABLESIZEで割った値を用いることで、値を0以上TABLESIZE未満に補正して用います。

今回の実装では、TABLESIZEは52291を指定していましたので、ある程度大きな要素数になると、かなりの高確率で衝突が生じることになります。

ハッシュテーブルのサイズに関する余談

この時TABLESIZEを365と指定してみると、 有名な「誕生日のパラドックス」と同じ問題設定になります。 「何人集まれば、その中に誕生日が同一の2人（以上）がいる確率が、50%を超えるか?」という問題に対する答えを問うもので、 その答えは 「23人」 であるという、意外な結論が有名です。 この興味深い結果をハッシュ値の文脈に載せてみると、

前提：TABLESIZEを365に指定し、理想的なハッシュ関数を用いたとする

主張：keyについてランダムに要素を追加する場合、 要素数が「23」に達するまでに１回以上の衝突が起きる確率は50%以上 である

と読み換えることができ、誕生日のパラドックスは上記の主張が「正しい」ことを示す、技術的にもおもしろい（厄介な）帰結だということが分かります。

さて、話が逸れましたが、TABLESIZEをどんなに大きくした場合でも、衝突の起きる確率は０にはなりませんので、プログラム上はその際の処理を書いておく必要が生じます。 それが、先ほど挙げた参照/代入のロジックにおけるeach文の役割だったのですね。

以下、その内容を再掲・解説しておきますので、ご興味のある方はコードを解読してみてください。

代入における衝突対策ロジック

1. 新規のkeyに対するoffsetの位置に既存の要素が存在するかどうかを確かめる(L14)
2. 存在しない場合は単純に要素を格納すればOK
   • ただし、今後衝突が起きた時のため配列を作っておき、いま代入したいkey, valueはその先頭要素として格納しておく(L15)
3. 存在する場合は、既存keyの再入力（keyに対する値の上書き）か、異なるkeyに対するoffsetの重複（衝突）かを判定する(L18-L19)
4. keyに対する値の上書きの場合は、上書き処理を行う(L21)
5. 衝突の場合は、以前に入力されたkey, valueにおいて、上記2.の手続きで配列を準備してあるので、その末尾にいま入力したいkey, valueをpushする(L26)

参照における衝突対策ロジック

1. クエリとして投げられたkeyに対するoffsetの位置に要素が存在するかどうかを判定する(L39)
2. 存在しない場合、nilを返す
3. 存在する場合、@arr[offset]の要素に対して「クエリ」と「格納されているkey」との等値判定を行い、求める要素があるかどうかを調べる
   • ここで@arr[offset]内に複数要素が存在するのは、過去に衝突が起きた場合である。多くの場合、@arr[offset]の要素数は１であるため、eachループは１回しか回らない

まとめ

今回、コードを読みやすく、保守・拡張しやすくしてくれる「連想配列」について、その原理に迫ってみました。 定数時間O(1)で要素へのアクセスを可能にする実装の一つに「ハッシュテーブル」があり、その構成要素として「ハッシュ関数」が重要な役割を果たしていることを、Rubyで実際に連想配列を実装してみることでおさらいしてみました。 前回の冒頭で述べた「連想配列は配列ではない」という（物騒な）主張は、本記事でまとめた内容をゼミで学んで以来、実装と実験によって体感できた実体験に基づいています。 インタフェースが一見同じでも、内部の仕組みは随分違うし、そのことに助けられることがあるんだなぁ…と感動したことを覚えています。

普段ツールとして見ている/使っている実装について、 内部の仕組みがわかるといちいち感動できる 、そんな経験が広がっていけば、プログラミングはますます深く、楽しくなるのではないでしょうか。 （綺麗にまとめてみました！）

参考資料

• 本記事のソースコード（GitHub）