ハッシュについて
ゼミの準備のためにいろいろと調べているハッシュについて、とりあえずドンドン書いていきます。
もしどこかおかしなところなんかがあると教えていただけると幸いです。
用語の確認
- ハッシュ
- 辞書（単一の集合D と、データx に対して、member(x,D), insert(x,D), delete(x,D) の3 つ
の操作を実現するデータ構造。 - ハッシュ関数
- ハッシュを実現するために用いる関数。もとのデータからある一定の長さを持った数値（文字
列）を生成するための関数。ハッシュ関数f : x ⇒ f(x) - ハッシュ値
- ハッシュ関数から得られる値で、この値に基づいてデータの格納場所を決める。
- 衝突（コリジョン・シノニム）
- ハッシュ関数f と格納したい２つのデータx1, x2(x1 ≠ x2) に対して、f(x1) = f(x2) となり、
異なるデータを同一の場所に格納しよう、とする状態である。
ハッシュ関数の理想と現実
理想的なハッシュ関数とは
異なるデータからは、常に異なるハッシュ値が得られるような関数が理想的である。
現実にもどるとハッシュ関数は。。。
一般にハッシュ値の値域は一定であり、キーとなる値の変域は無限である、と考えられるので、
ハッシュ関数をうまく定めても、上のような理想的なハッシュ関数を実現することはできない。つまり、衝突が発生する可能性がある。
そのため、できるだけ理想的なハッシュ関数に近いものを考え、さらに衝突が発生した際にどのような挙動を取るかを考える必要がある。
衝突回避法
外部ハッシュ法
衝突が起こった際に、そのデータの格納場所からの連結リストとして次のデータを格納する。
内部ハッシュ法
衝突が起こった際に、格納場所をそのハッシュ値からある演算により得られる値を新しいハッ
シュ値として利用する。
計算量
上で示した３つの操作に対する計算量は、すべてハッシュ関数の計算量O(f)、衝突回避のため
のある演算の計算量O(ある演算) の多項式で表されている。
よって、これらの２つの計算量を小さくすれば小さくしただけ全体の計算量も小さくすることが
できる。この結果、O(f) = O(1) となるハッシュ関数f とO(ある演算) = O(1) となる「ある演
算」を定めることにより、３つの操作に対する計算量は、O(1) で実現できる。
ハッシュのメリット・デメリット
メリット
- 検索が早くO(1) で可能となる
- 2 分木に比べ、文字列の検索が行いやすい
デメリット
- ハッシュを構築する際に利用したキーによる検索しかできない。
- 悪いハッシュ関数（衝突が発生しやすいハッシュ関数）を利用すると、member(x,D),insert(x,D), delete(x,D)の操作をO(1) で実現できなくなる。
- データの格納率が増えるにつれて、効率が悪くなる。
- ヒープや二分木などのデータ構造に比べて、ソートに対する操作が格段に遅い。
ハッシュ・ハッシュ関数の実際の利用例
高速な検索（データ構造としてのハッシュ）
高速な検索については、データベース（MySQL など）の高速化のためのインデックス化処理に使われている。
データの検証（ハッシュ関数として）
データの検証としては、パスワードの管理に使われることもある。Web サイトなどでパスワー
ドが必要なページを開いた際に出てくることがあるウィンドウである。このパスワードは、MD5というハッシュアルゴリズムを使ってハッシュ化している。また、Linux,UNIX でもパスワードはハッシュ化されたデータで管理している。これは、パスワードを元の平文のまま管理すると、盗聴などの際に危険であること、ハッシュ関数は一方向性がありハッシュ値を見てももとの平文が予測できないことが関係している。
また、データの検証の別の例としては、Web サイトなどからソフトウェアをダウンロードする際にも使われる。これはダウンロードが完全に行われているか？途中で別のデータに置き換えられていないか？などを検証するために、これもmd5 というハッシュ関数などを使っている。この場合、Web サイト上に正しいファイルのハッシュ値を掲載しておいて、それをユーザーがダウンロードしたファイルのハッシュ値と見比べる、といったように使うことができる。
ハッシュ関数の代表例
- MD3
- MD4
- MD5
- SHA-1
など。
関連記事
[PR]
トラックバック
http://yamablo.com/2008/11/15-002600.php/trackback
![t ]E](http://www.affiliate-b.com/upload_image/984-1198556658-3.gif)