ホーム » スタッフ » 斉藤徹 » 講義録 » 情報構造論 » ハッシュ法(2)

2012年11月
« 10月   12月 »
 123
45678910
11121314151617
18192021222324
252627282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

ハッシュ法(2)

授業進度が予定よりも早いため前半講義で、後半はまだ提出者の少ないことから 課題の時間とした。

前回のハッシュ法では、数値(電話番号)をキーとする検索であった。 このためハッシュ関数は、数値の不規則性の部分を取り出すだけでよかった。 それでは、文字をキーとしてデータを探す場合はどのようにすればよいか?

文字の場合は、文字コードを用いてハッシュ値を作れば良い。

int hash_func( char* s ) {
   int sum = 0 ;
   for( int i = 0 ; s[i] != '¥0' ; i++ )
      sum += s[i] ;
   return sum % HASE_SIZE ;
}

しかし、この方法では、文字の並び順が違うだけ(“ABC”,”CBA”,”BBB”)に対して、 同じハッシュ値となってしまう。 英文字の場合は文字数も限られ、文字コード的には末尾4bitが変化するだけであり、 上位ビットは文字数に左右されることになる。 この場合、同じような文字数であれば、末尾4bitの不規則性も平均化されて、 近いハッシュ値になることが懸念される。

そこで、文字コード的に変化のある部分が、数値的に全体に影響を及ぼし、 最終的な値が広く分布するように以下のような計算とする場合が多い。

// 積算部のみ
sum = ( sum * (小さめの素数) + s[i] ) % (大きめの素数) ;

このような考え方は、疑似乱数を生成する方式と近い部分が多い。