ハッシュ関数1

 さぁ、調子に乗って2連投。
なんでか？やらなければいけない時に限って、こんなことがしたくなるんですorzなんにもやることがないときはボーっとしてるんですけどね。


・・・


これ投稿したら、ネタがなくなるなぁ・・・。


※WINAPIの状況はこの次になりますかね・・・。

 初めはよくわかりませんでした。っといっても、厳密には現在も理解はできていないと思います。
 ハッシュ関数はデータ構造の一種です。構造を簡単にいえば、

「あるデータから得られるキーを元に、データを格納していく」

ってな感じです。キーを得るためにはハッシュ関数という関数にデータを渡し、返ってくる値がいわゆる「キー」となります。このキーをハッシュ値と言います。キーを得たら、データを格納します。格納する入れ物をハッシュテーブルまたはハッシュ表といい、挿入先をスロットといいます。プログラミングでいう配列と考えれば早いですね。
ここでいきなり疑問が出ますね。

「キーが重なったらどうすればいいの？」


これを回避するにはいろいろありますが、以下の二つが代表的です。（らしいです。）

• 内部ハッシュ

ハッシュ値が衝突したら、もう一度ハッシュをかけ、次の要素を見に行く方法です。それを要素が空になるまで繰り返します。初回以降のハッシュ値の導出はユーザーが決めます。

• 外部ハッシュ

ハッシュ値が衝突したら、そのスロット内のリスト構造に挿入します。正直、これはかなりデータに左右されそうな気がします。もしかしたら、すべてのデータが同じリストにつながってしまうかもしれないですしね＾＾；


かなり詳細をハショリましたが＾＾；（あまり詳しく言うとぼろが出そうなので・・・。ってもう出てますね・・・。きっとorz）さて、これを踏まえたうえで、データをハッシュで管理してみようと思います。自分が考えたのは、

「内部ハッシュと外部ハッシュのいいとこを掻い摘んだらいいのでは？」

と思いました。外部ハッシュでは、スロットにいきなりリストがあり、リスト化しますが、そうではなく、またハッシュテーブルを持ったらどうでしょう？ハッシュテーブルに深さを持たせるのです。最後のハッシュテーブル（二分木でいう葉）にはリストを持たせるんです。一つハッシュ関数を通して、深さが１つ深くなる・・・これはどうだろうかと考えました。もちろん、ハッシュテーブル、深さ、ハッシュ関数はユーザーが決めることができるようにします。また、メモリを無駄に消費しないため、ハッシュテーブルは動的確保します。（挿入したいハッシュテーブルが存在しなければ確保）
以上の考え方を以下の図に示します。（わかりづらい・・・）

今回は、このデータ構造を用いて、テキスト内にでる英単語をカウントするプログラムを作ることを目的とします。大文字、小文字比較はしません。条件として、「'」、「-」でつながれた単語は一単語とみなします。それ以外の、数字、記号文字等は入力の段階ではじかれます。

こんな条件のもと、C言語を用いて、ハッシュをプログラム化しました。わかりづらいですかね＾＾；

さて、結果はどうなるのでしょうか。それは次に回します。
ここまで読んでいただきありがとうございました。
・・・でも大した結果は得られず終了しｔ・・・(ry