ハッシュの考え方、使用例を分かり易く教えてください。

基本情報処理の勉強をしていますが、ハッシュの考え方がいまいちわかりません。分かり易く教えていただけると幸いなのですが、どなたかご教授いただけませんでしょうか。どうぞよろしくお願い致します。

No.4 回答者： imogasi 回答日時： 2004/09/12 16:46

ハッシュ関数と言うのが考えられていて

http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83% …
にあるように
暗号化
誤り検出
改ざん検出
ハシュテーブル
などに使われます。
ハシュという時、どの関連を言っているかか注意しましょう。
データベース構成と検索に関連して述べてみます。
例えば口座番号が７桁あるとします。ディスクに１千万区画の記録区画を用意すれば、どんな口座番号が来ても、その数字番目の区画に記録できます。
しかし口座番号に空きがあって、実際は１００万口座しか使われてないとき、ディスクに１００万区画を用意しておき、ある口座番号が来た時に、もし１００万の中に散らばって、記録場所が決められれば、能率的です。
Ｆ（口座番号数字）＝数字　Ｆは何か計算すること（関数）を意味します。
特徴は口座番号数＞＞数字（＞＞は相当少ない意味）でないと意味を持ちません。
そして口座番号数字が色々変ってはいってきた場合、数字は別のものになることが望ましい。なぜなら重複する数字になると、後からの口座の記録場所がなくなるから。
さてそんな関数Ｆがあるかどうか。
http://ja.wikipedia.org/wiki/%E4%B8%80%E6%96%B9% …
にある一方向性関数と言うのが研究されています。
これの良いところは、計算で「数字」が出て、そこに記録されていることが決まっているから、そこだけを見に行けば良く、速く探しやすい。
目次インデックスを使うようなのは、何段もディスクをアクセスして辿らないと行けないのに比べて速い。
ディスクのファイルを読む時間＞＞場所を計算する時間。
http://www.db.is.kyushu-u.ac.jp/adp/ad/hash.pdf
の配列による探索とハッシュ法に当たります。
しかし衝突は避けられず、衝突するケースを５％とかに押さえて設計し、衝突すれば別の区画にお引取り願うように
設計する。
例えば１２３、３４５、２３１、３４５があるとしてそれぞれに何かの演算をして１，２，３，４の数字を出せれば
一番良いのですが。
長くなるので、一端を記してみました。
Ｈａｓｈは「肉を切り刻む」「メチャメチャにする」「（フランス古語の）斧」から来ておるそうです。
ＭＯＤ関数などを使って、出した結果の数が元の数・原型を窺えないところからでしょうか。

No.3 回答者： GoF 回答日時： 2004/09/11 22:21

教えるために、非常にシンプルに考えます。

例えば、以下の文章をハッシュにしてみます。
きょうは
いい天気
あしたも
いい天気
だといいな。
これを縦読みして、「きいあいだ」これがハッシュ値です。
縦読みを実装している関数をハッシュ関数といいます。
ちなみに、実際のハッシュ関数は戻り値は数値に変換
されていますし、もっと賢い関数ですのでご注意ください。

No.2 回答者： noname#30727 回答日時： 2004/09/09 02:22

ハッシュに進まれているということは、既に幾つかの探索やソートは知っていますよね。

探索やソートする為には比較が必要です。ところが、比較対象が大きいデータの場合、比較そのものに時間がかかってしまいます。例えば、1024バイトのオブジェクトの比較には、最大1024バイトの比較が必要です。

この大きなデータの比較を一意な整数の比較で済ませる事ができれば、比較時間を大幅に短縮できると考えた人がいます。これがハッシュという考え方の始まりです。文字列を取り扱うときによく使用されます。

以前に自作コンパイラのコンパイル速度の比較をしてみた時の事ですが、バイナリーサーチとハッシュ法の速度差は、前者で１分かかるものが、後者だと１秒以内に終わります。

不思議なことに、実利でこれほどの違いがあるにもかかわらず、ハッシュ法を理解している人はそれほど多くはいません。
試験の為という事ではなく、この辺をきちんと理解しておくと「出来る人」と扱われます。

No.1 回答者： tatsu99 回答日時： 2004/09/08 19:38

１．ハッシュとはある文字列からある数値（これをハッシュ値といいます）をある規則に従って作成する事です。

２．その場合、同じ文字列は必ず同じ数値（何時の場合でも）に変換されることが必要です。
３．この例を示します。話しを簡単にするために、文字列はA～Zだけで構成されていることにします。
AAA, ABB, AAADD, BAB, B これらの文字をハッシュ値に変換する為には、上記の２の条件を満足する変換の規則を決めれば良いわけです。
例えば、先頭の１文字だけに注目するとA～Zになります。
これをＡ－＞１、Ｚ－＞２７のように割り当てるとします。そうするとAAA->1,ABB->1,AAADD->1,BAB->2,B->2
のような値が作成されます。これは立派なハッシュ値になります。なぜなら、上記の２の条件を満足していますから。しかしながら例えば、現在の時刻（秒）をこの値に加えたものは、ハッシュ値にはなりません。（毎回同一の結果が得られないため）
４．実際のハッシュ値の作成方法は、これほど単純ではありません。例としては、以下のようにします。（但し、この方法が良く使われているわけではありません。あくまでも例です）
各文字を上記の数値に変換した結果を掛け合わせ、その値を10000で割った余りをハッシュ値とします。
AAA->1×1×１/10000の余り＝１
ABB->1×2×2/10000の余り＝4
のようになります。
この方法でも必ず、同一の文字列に対しては、同じ結果が得られます。尚、異なる文字から同じハッシュ値が生成された場合、これをシノニムと呼びます。
ABB->1×2×2/10000の余り＝4
ABBA->1×2×2×1/10000の余り＝4
はこの場合、シノニムが発生した状態となります。
４．以上がハッシュ値を作成する方法でした。
では、このハッシュ値をどのように利用するかということですが、文字列の検索を高速で行う場合に利用します。
５．文字列の検索方法は、以下の３通りがあります。
１）シーケンシャルサーチ
２）バイナリーサーチ
３）ハッシュ値による検索
上記の１）２）はここでは、説明を省略します。（判らないときは補足して下さい。そのときは改めて説明します）
例として、10000件のデータがあるときの検索回数は
１）シーケンシャルサーチは平均5000回の検索
（最良で１回、最悪で10000回）
２）バイナリーサーチの場合は、平均13～14回の検索
となります。
では、ハッシュの場合は、どうなるかということですが、それにはまず、ハッシュ検索がどのようなものかを知る必要があります。
５．ハッシュ検索の手順は、以下の手順で行います。
１）文字列からハッシュ値を作成する。
（先頭の１文字をA～Zを１～27にする方法とします）
２）そのハッシュ値が示す場所へその文字列を格納する。
例えば、AAA->1のハッシュ値の場合、１番目の配列にAAAを格納します。
BBB->2の場合、２番目の配列に格納します。
ABB->1は、シノニムですので、１番目に格納したいが、既にAAAが格納されているので、１番目のシノニムを格納する別のテーブルを作成し、そこに格納する。
そのようにして文字列をテーブルへ格納していきます。

３）検索は以下のように行います。
・検索対象の文字列からハッシュ値を求める。
・求めたハッシュ値に示されるテーブルの位置を検索する。
・そこに存在しなければ、シノニムを格納してあるテーブルを検索する。
・そこにも無ければ、該当文字はない。
６．以上がハッシュ値による検索です。
従って、ハッシュ値による検索時は、以下のことが大切になります。
１）ハッシュ値を求めた時に、シノニムの発生がすくないこと。（この数が多いと検索回数が増えます）
２）では、どうすればシノニムの発生が少なくなる方法で、ハッシュ値を作成するかということですが、これはデータの集団がどのようなデータ構成をしているかにも依存します。従って、これと言う切り札はありませんが、いろいろと工夫する必要があります。
７．理想的には１００００万件のデータから１～１００００のハッシュ値を作成し、シノニム無しであれば、１回の検索ですみます。A～Zを１～２７にする方法では、良くても10000/27=370のシノニムが発生し、約370/2回の検索回数となります。最悪は、（全てAから始まる文字列の場合）シーケンシャルサーチと同じ結果となります。