授業を前にひとまず、話のネタを整理しながらメモ。 授業が終わったら、加筆しまーす。 んで、今日はハッシュ法について説明を行う。 テスト前が今日を含め2回なので、説明は終わるだろう。 後期中間試験後は、参照カウンタなどのネタから説明の予定。

ハッシュ法

リスト構造や2分木などを今までの授業で解説してきたが、 O(N)やO(log N)の検索時間がかかる処理。 さらなる高速化にはハッシュ法が取られる。

電話番号でデータベースを作る場合、電話番号自身を配列の添字にすれば、 検索時も添字でアクセスするだけで、検索時間も一定でありO(1)にできる。

// 電話番号XX-XXXXの6桁で名前を検索
char name[ 1000000 ][ 20 ] ;
strcpy( 272925 , "t-saitoh" ) ;

しかしながら、この方法では大量のメモリ空間が必要となる。 ハッシュ法では、データの一部を配列の添字とする方式。 データの保存場所はハッシュ値、ハッシュ値を取り出す関数をハッシュ関数と呼ぶ。 データの一部を取り出すことから、異なるデータなのに同じハッシュ値となる場合がある。 これをハッシュ衝突と呼ぶ。

実際には、ハッシュ衝突の対策が問題となる。 例として、電話番号が使われているのかチェックする処理を考える。

#define SIZE 100
int  table[ SIZE ] ; // ハッシュ表には電話番号を保存
int hash_func( int tel ) { return tel % SIZE ; }
int idx = hash_func( 272925 ) ;
table[ idx ] = 272925 ;

上記のような処理でデータを扱う場合、ハッシュ衝突対策の例は以下のようになる。

void entry( int tel ) {
int idx = hash_func( tel ) ;
while( table[ idx ] != 0 ) {  // 先着データがあれば+1に保存
idx = ( idx + 1 ) % SIZE ;
}
table[ idx ] = tel ;
}
int search( int tel ) {
int idx = hash_func( tel ) ;
while( table[ idx ] == 0 ) {
if ( table[ idx ] == tel )  // 見つかった
return tel ;
idx = ( idx + 1 ) % SIZE ;
}
return 0 ; // 見つからない
}

ただし上記のプログラムでは、ハッシュ表がすべて埋まったら無限ループになってしまうので、その対処を追加する必要がある。