Ruby 天気予報編 (4) Hash の説明 その 2 【計算数学 I】

更新日時:

一般論としての Hash

情報科学としての Hash は「普通これ」というものがあるので、それを説明します。

プロ向けに最初にお断りしておきますが Ruby の Hash は相当工夫がされており、以下で述べる全体像とは一見大きくかけ離れています。具体的には、ハッシュの領域は逐次確保されますし、順序も保存します。計算数学の教材としては、この内容を知ることよりも、スタンダードなハッシュテーブル・ハッシュ関数の概要を知ることの方が意味があると思われます。ですから、Ruby 処理系に置ける正確な Hash の実装は置いておいて、「普通これ」を解説します。

あと、この記事を全部読んで理解しても、理解しなかった時と比べて、今回目標としているプログラムが書きやすくなることもありません。読むかどうかは受講生に任せます。

ざっくりいうと

  • ハッシュの実態は配列である
  • ハッシュ関数でキーを「添字」に変換する
  • ハッシュ関数や配列のサイズに工夫が必要である。

概要

用語: ハッシュ と単に書いた場合は、ハッシュというデータ構造の実態を指すものとします。正確にいうと、ハッシュテーブルのことです。Ruby でいう「Hash クラスのインスタンス」のことです。直後の段落で「ハッシュ関数」が出てきますがこれとは別物です。

ハッシュは、配列の「添字」を「文字列」やら「シンボル」やらにしたものだと説明しました。 これは、実装方法とはずれていないかなり良い理解です。 ハッシュは通常、実体としては配列として実装します(ここでいう「配列」は、Ruby の Array クラスのインスタンスとしての「配列」とは異なり、情報科学的な意味での配列です)。 添字の部分をどうするかというと、「文字列」や「シンボル」を、ハッシュ関数で「添字」に変更することで実現します。その証拠?に、ハッシュは 「連想配列」 と呼ばれることもあります。 前の記事で、キーとなれるのは「hash() というメソッドが定義されているクラスのインスタンス」と書きました。この hash() こそが、ハッシュ関数、すなわち「添字」を返すメソッドです。実際やってみると、以下のようになります(出力は個々人の環境で変化する可能性があります)。

irb(main):001:0> "elf".hash
=> 3771418711636640374
irb(main):002:0> :muramasa.hash
=> 3866969989039896310

ここから先は、ハッシュ関数の性質と、配列のサイズについてお話しします。

ハッシュ関数

一般的に、ハッシュ関数 $f \colon S \to \mathbb{N}$ は以下の性質をみたす関数です。

  1. $f$ は関数である。すなわち、「 $A = B \in S$ ならば、 $f(A) = f(B)$ 」が 必ず 成り立つ。
    • 当たり前のように思うかもしれませんが、これは重要なポイントです。この $A = B$ の意味は、 $A$ , $B $が所属するクラスによって違います。前回の記事で「文字列の場合、同じ文字列であっても、オブジェクトとしては区別されます」と書きました。すなわち、文字列として同じであれば、たとえオブジェクトとしては異なるものであるとしても、同じハッシュ値を返さねばなりません。
  2. $f$ は「ほぼ」単射である。すなわち、「 $A \neq B \in S$ ならば、 $f(A) \neq f(B)$ 」が なるべく多くの場合 成り立つように頑張って作っている。
    • $A, B \in S$ が $A \neq B \in S$ かつ $f(A) = f(B)$ をみたす時、$A, B \in S$ は 衝突 するといいます。衝突すると、異なるキーにハッシュ上同じ「添字」がつくことになりますので、値を取り出す時に困ります。なお、この「衝突」の定義は間違いではありませんが、「衝突」は別の場合も起こります。あとで補足します。
    • おいそれと衝突したりしませんが、しかしそれでも衝突するペアを作ることはできます。 $f$ は高速に計算できないとハッシュのアクセスが遅くなります。 $\mathbb{N}$ は可算無限個ありますが、計算機ではいくらでも大きい数字を使うわけにもいきません。その兼ね合いである程度の衝突を許容します。また用途にもよって強度を決めます。パスワードをハッシュ化する際は高い強度が要求されます。
    • ハッシュのデータ構造に戻って:ハッシュ値が衝突した際にどうするでしょうか。同じ添字に 2 つ以上のオブジェクトを許容するオープンハッシュ、許容せず再ハッシュ(または隣接する番号に遷移)するクローズドハッシュという方法に大別されます。
  3. $f \circ g = \mathrm{id}_{\mathbb{N}}$ をみたす $g \colon \mathbb{N} \to S$ を容易には計算できない。すなわち、ハッシュ値だけからもとの値を推測ことは容易にはできません。
    • 今回は必須ではありません。しかしパスワードをハッシュ化する際にはこの性質は重要です。ハッシュ値を得ることを「ハッシュ化する」といいます。

今は $f$ の返り値を自然数としていますが、実際は文字列とすることも多いです。

また Ruby の場合、ハッシュでは順序が保存されます( Ruby 1.9 以降)が、一般のデータ構造としての Hash では順序は保存されるとは限りません。

演習

通常のシステムではパスワード認証を以下のように行います。

  • パスワードを保存する際には、ハッシュ関数でパスワードをハッシュ化し、ハッシュ値だけ保存する。
  • パスワードを認証する際は、入力されたパスワードをハッシュ化して、保存してあるハッシュ値と比較し、一致していれば正しいパスワード、違っていれば間違ったパスワードであると認証する。

問題 1 : ハッシュ関数の 1. と 2. の性質は、それぞれ、パスワード認証の際にどのようなことを保証しているでしょうか。

問題 2 : なぜ生のパスワードではなく、ハッシュ値だけ保存しているのでしょうか。その根拠は何でしょうか。

問題 3 : 悪い人が、あなたのパスワードをどうしても知りたいと思っており、あなたのパスワードのハッシュ値と、あなたの使っているシステムのハッシュ関数を入手したと仮定します。このとき、悪い人はどのようなことをするのが最善でしょうか。また、この場合であってもあなたのパスワードが破られないための対策は、予めどうしておくことでしょうか。

配列のサイズについて

先ほどのサンプルで、 3771418711636640374 やら 3866969989039896310 やらと、やたらと大きな数字がハッシュ値になっていることに違和感を覚えた方もいらっしゃると思います。というのも、現在通常使われている計算機ではこんなに大きなサイズの配列をメモリ上確保すること自体困難(はっきり言って不可能)であるからです。例えば整数の配列だと、現在の計算機で「一瞬」で確保できるサイズは $10^6$ や $10^7$ 程度です。時間がかかっても良いとしても $10^{10}$ バイトが約 $10$ ギガバイトですから、これ以上のオーダーだとそもそもメモリの上に乗りません。

だからこの数字を「配列の添字」として直接採用しているわけがないということがわかります。ではどうしているのか? 普通どうするかというと、 ハッシュ値の配列のサイズでの剰余を取る ことが多いと思われます。サイズを以下では $M$ とおきます。

先ほどハッシュの衝突を定義しましたが、あとで補足をすると述べました。ハッシュ値が異なっていたとしても、剰余を取る動作の結果同じ「添字」になった場合も、やはり 衝突 であるというのが正確な理解です。

剰余をとった結果衝突するかどうかは、もはやハッシュ関数の責任ではありません。$M$ に依存します。当然のことですが、$M$ が大きければ大きいほど衝突は起こりにくくなります。しかし $M$ が大きすぎるとメモリを大量に消費しますし、メモリを確保する際に時間がかかります。だから $M$ は ほどほどに大きい のが良いということになります。

正確には Ruby の Hash はサイズを動的に調整しているので $M$ は固定ではありません。しかし、衝突を回避する基本的な考え方は変わりません。

ナビゲーション

この教材は、東京大学理学部数学科専門科目「計算数学 I」のために執筆されたものです。 このサイトに掲載する際に、記事を分けてあります。 他の回はRuby 天気予報編 一覧 #ks1-ruby-forecastから御覧ください。

Ruby 入門 (計算数学実習資料集)には他の TA が書いた教材があります。

コメントする