今年度は校舎の改修と新型インフルエンザで、学校行事は特例ばかり。 しかし、ようやく本館の改修もひと段落で、電子情報棟の実験室を仮設教室にしていた 教室を、本来の教室に戻すお引越しの日。

担任の教室も本館に移動だけど、移動先も他クラスが今日いっぱい使うし、 出て行く教室にも、他実験室に移動していたクラスが戻ってくる。 ということで、原則教室内のものは、すべて持ち帰り。 HRで持ち帰りと伝えていた割りに、机やロッカーに大量に「教科書」などを蓄えている人も多い。 んで、「今日全部持ち帰りはムリ！」という学生さんがチラホラ。 さて、放課後の移動はスムーズに終わるかな….

昨夜より福井県の平野部でも、シーズン最初の本格的な雪。 我が家では車の上に、3cm ほどの積雪であった。 学校につくと、早々に学生さんより「雪で電車が遅れてます」との連絡多数。 1限目の授業にも影響が出た様子。 シーズン最初の雪だし、しかたがないか….

処理速度と関係して説明するアルゴリズムの最後？として、ハッシュ法を解説する。 例年どおりの『電話番号から名前を検索する』という例をもとに、 ハッシュ関数に電話番号末尾２桁をアドレスとする方法を説明する。 また、ハッシュ表サイズ100件に、40件を入れる場合ということで、 電話番号末尾2桁ではハッシュ衝突が発生する場合もあり、 その対応方法を説明。

ハッシュ関数の選び方としては、簡単に計算でき、異なるデータに対するハッシュ値の出現頻度が均一(一見デタラメな値)を選ぶことを説明する。 簡単な計算で、データの保存場所が一発で計算できることから、 一定時間でデータを参照できる。処理時間のオーダは、O(1)となることを説明する。

クローズドアドレス法

ハッシュ衝突が発生した場合の対応として、 「椅子取りゲームで椅子が先にとられている時に、１つ後ろの席に座る」 という対応を概念として説明し、簡単なコードを示す。 衝突してたら、空きが見つかるまで+1を繰り返し、途中でハッシュ表サイズに 達したときは先頭から…という方法を示す。

授業ではクローズハッシュと用語を説明したけれど、 正確にはクローズドハッシュ法(closed hash)であった…

チェイン法

クローズドアドレスハッシュ法は、データ件数がハッシュ表サイズに近づけば、 空椅子を何度も探す状態になり、処理時間がO(N)になってしまうし、データ件数が ハッシュ表サイズ(配列サイズ)を超えることができない。

このことから、同じハッシュ値を持つデータを、リスト構造で保存する方法をとる。 この方式は、オープンアドレスハッシュ法とかチェイン法とか呼ばれている。

文字データのハッシュ関数

電話番号から名前を調べる場合は、電話番号末尾は"100の余り"で簡単に計算できた。 しかし、名前から電話番号を検索したいといった場合は、前述の計算ができない。

文字列のデータからハッシュ値を求める場合、数値だけみればランダムに見えれば いいのだから、文字コードの合計といった方法がとられる。

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

文字列の順序違いで同じハッシュ値が求まるのが問題であれば、合計の計算部分を、 以下のようにする場合も多い。

s = ( s * (小さい素数) + str[ i ] ) % (大きい素数) ;