処理速度と関係して説明するアルゴリズムの最後？として、ハッシュ法を解説する。 例年どおりの『電話番号から名前を検索する』という例をもとに、 ハッシュ関数に電話番号末尾２桁をアドレスとする方法を説明する。 また、ハッシュ表サイズ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 ] ) % (大きい素数) ;