質問: **データの探索アルゴリズム**の一つに**「ハッシュ法」**という手法がありますが、 このハッシュ(探索)法とは **私自身の解釈として**、(おおまかでありますが、) 1. **探索したいデータをハッシュ関数で計算する** 2. **ハッシュ値(キー値。アドレスみたなもの?)を出力する。** 3. **出力したハッシュ値を元に、データ列にあるハッシュ表から直接該当するハッシュ値(キー値)にアクセス(探索)する。** このような感じであると私自身思いますが、つまり、「ハッシュ探索法」は **「出力したハッシュ値を元にデータ列にあるハッシュ表から直接アクセスしてデータを探索する」** ということなんでしょうか?(大雑把ですが・・・) 何か所々解釈が間違っていると思いますが、その解釈でいいのでしょうか? よろしくお願いします。 (ちなみに掲載されている図はあくまで例であることを御了承いただけばと思います。) ![ハッシュ値とデータを紐付けして格納](https://teratail-v2.storage.googleapis.com/uploads/contributed_images/532f5ef5af597d59f4355d21970aa568.jpeg) ![ハッシュ値を元に該当するデータを探索](https://teratail-v2.storage.googleapis.com/uploads/contributed_images/39b7422f9f1ce9b806c73d15bf3dd587.jpeg)
回答: 他の回答者も書いていますが「ハッシュ関数」の衝突を補足します。 **ハッシュ関数の出力は衝突する** 『世界標準MIT教科書 Python言語によるプログラミングイントロダクション第2版』近代科学社より引用。 『ハッシュ関数は大きな集合から小さな集合への写像である。ハッシュ関数を用いることで、大きな集合の属するキーを小さな集合に属する整数へと変換できる。ハッシュ関数の出力の集合は入力の集合に比べて小さいため、ハッシュ関数は、多対1写像 (many-to-one mapping) を生成する。2つの入力が同一の出力へ写像される場合を衝突 (collision) という。衝突がなるべく起きないようにするには、各出力が均等に発生するような一様分布 (uniform distribution) を作り出すハッシュ関数を考案しなければならない。』 * ハッシュ関数は、多対1写像 (many-to-one mapping) ミカンとリンゴを入力とすると、同じ値が出力されることがある。 * 2つの入力が同一の出力へ写像される場合を衝突 (collision) という。 一つの指定席に二人(以上)の人が座りたいということが起る。衝突をできるだけ回避するために出力を一様分布にしたい。 **ハッシュテーブルの実装** 衝突を考えると、配列に格納するために工夫が必要になります。 * 同じハッシュ値のエントリを隣に置く 本来隣は別のハッシュ値の指定席なので、どんどんずれる。空席に出会うまで衝突かどうか線形探索する必要がある。 * 指定席自体を配列や連結リストにして衝突を格納できる構造にする。 質問の図のような単純な配列ではなく、配列の配列や、結合リストの配列にする。 入力のビットの数を数えて偶数なら0奇数なら1というハッシュ関数をつくると出力値は2つ。大量の衝突が起きる。衝突の中からめざす値(リンゴかミカンか、...)を発見するのにリストをさらに線形探索する。このようにハッシュ関数が悪いと非効率。 **ハッシュ関数の実装** 上の本にはハッシュ関数の実装について書かれていません。以下の本を読んでください。 『世界標準MIT教科書 アルゴリズムインロダクション第3版 第1巻』近代科学社 衝突の起きるハッシュ関数だけでなく、衝突の起きない「完全ハッシュ法」も紹介されています。 **ハッシュ関数の応用** パスワード、電子署名など様々な分野で使われています。wikipediaを読んでみましょう。 ### 【追記(2019-04-28)】 **キーと値** ハッシュ値(配列の添字)が「キー」と思われているようですが間違いです。キーは「リンゴ」「ミカン」になります。英語の辞書に例えると、英単語が「キー」単語の説明が「値」に相当します。質問の例は「キー」と「値」が同じ辞書です。ハッシュテーブルを「辞書」「連想配列」「ハッシュ」と呼ぶことがあります。 **ハッシュテーブルのエントリ** 通常は(キー、値)のペアになります。理由は、衝突リストに格納されたエントリを識別するのにキーの同値判定が必要だから。