ハッシュ関数2

 そして3連投目。
こんな長文の連投は初めてです。肩壊しちゃいますよｗ
まぁ、レポート書いてるだけだから全く時間はかかってないんですけどね。

こんな無駄なもの作っても、全く使い物になりませんがねorz

 まず、入力には以下の三種類を用意しました。

• A.txt ( 163kB )
• B.txt ( 4.33kB )
• C.txt ( 39.5MB )

次に、今回は、テーブルは3つにします。これは「勘」ですｗ厳密にはここも変えなくてはいけないのですが・・・可変のメンバが多すぎて、めんどっ・・・(ry
いや、しかし！ハッシュテーブルの長さは可変にします。長さの集合は以下の通りです。

{ 5, 17, 29, 37, 53, 67, 83, 97 }

基底ハッシュテーブル（二分木でいう根）と子ハッシュテーブル（基底以外のこと）で配列の長さを変えました。これは・・・気分ですｗ本当は、深くなるごとにサイズを大きくor小さくなどやろうとした残骸です。そこまで追及しなかったので、今回は基底のみ他と違うようにしてみました。
次に、ハッシュ関数ですが、今回は、二つ用意しました。h₁(x)は、単語の各文字のアスキーコードの和を参照するハッシュテーブルのスロット数割った余りを返す関数です。h₂(x)は、和をテーブルの数で割った余りを返すということは変わりないが、アスキーコードを取得し、奇数であったら、その数を2で割るという作業をする。基底ハッシュテーブルT→子ハッシュテーブルT₁はh₁(x)で、T₁から子ハッシュテーブルT₂はh₂(x)でそれぞれハッシュ値を取得しています。


それぞれの結果を以下に示します。

時間の短いのがサイズの小さいファイルです。
にしても、メモリの無駄遣いが明らかですねｗｗ（速度が一定になる）大体ですが、ハッシュテーブルが29ぐらいなら、速度的にも、メモリ効率的にもちょうどよいみたいです。本当なら、深さをより考慮すべきだとおもっ・・・(ry
まぁ若干予想通りといえば、予想通りの結果ですよね＾＾；でも自分はちょっとだけ疑問に思うところがあります。

「スロット数が多ければ、リストは短い（可能性が高い）から、単語の探査は短いはず。でも、ハッシュテーブルが29～100となると、さすがにリストの長さも変わるよね？ってか、リストの長さどうなってんの？」

ここは、内部ハッシュ法の恩恵が得られているかの問題です。いわゆる、複数のハッシュ関数のおかげで、どれだけ衝突の数が減り、どれだけ、均等なリストができているのか？です。
ちょっと見てみます。せっかくなんで、h₂(x)変えてみます。ハッシュ関数によって結構偏りが出るんじゃないかと。h₃(x)は、h₂(x)は「奇数であったら」ですが、この関数は「偶数であったら」に変えるだけです。データはc.txt( 39.5MB )です（だったと思います＾＾；）。
（GetHash2 = h₂(x) , GetHash3 = h₃(x) です。すみません・・・。）

結構違いますねー。今回はh₂(x)のほうが、データにあっているみたいですね。ハッシュ関数の性能は大切なのかなって思いますけど、これもデータ次第なんですよね。

ちなみに、今回、二分木探査を用いた英単語カウンタを作ってみました。結果はうれしいことに、容量が大きなデータほど、ハッシュに比べ遅かったです。これは結果的に、うれしかったですねｗｗ

今回、結果はかなりまとめづらい中途半端になってしまいましたが、今回はこんなところで。実際は、メモリ効率まで考察しました。が、ここでは省略します＾＾；ソースコードは・・・実験用にぐちゃぐちゃになっていて、修正も面倒なので、省略します＾＾；自分的にはお腹いっぱいですが、結局は、実際の役に立つものを作っていかなければ。。って思います。

ここまで読んでいただいてありがとうございます。
こんな感じに、自分なりにちょくちょく研究してみるのもいいかなって思いました。