リスト構造から2分木と、高速の検索をする手法として説明したけど、 もっと高速なデータ検索として、ハッシュ法を示す。

メモリ無駄遣い

// 電話番号から名前を調べるために、電話番号自身を保存場所に使えばいい
// しかし、メモリが無駄遣い。
char phone[ 1000000 ][ 10 ] ;
strcpy( 272925 , "斉藤" ) ;

ハッシュ法(衝突無視の場合)

であれば、電話番号の末尾2桁なら、他の人とかぶらないのであれば、 以下の様にすれば、メモリの無駄遣いが防げる。 しかし、末尾2桁が偶然、他の人と同じ場合もありえる。こういう場合をハッシュ衝突と呼ぶ。

#define HASH_SIZE 100
int hash_func( int phone ) {   // ハッシュ関数
return phone % HASH_SIZE ;
}
char phone[ HASH_SIZE ][ 10 ] ;
strcpy( hash_func( 272925 ) , "斉藤" ) ;

クローズドハッシュ法

じゃあハッシュ衝突が発生したら、イス取りゲームの様に、使っていない次のイスに座ればいいじゃん…というのが、クローズドハッシュ法。 授業で説明したときは、うまく配列を定義していなかったので…

struct PhoneName {
int  phone ;       // 電話番号=0 なら「空き」と判定することにする。
char name[ 10 ] ;
} ;
struct PhoneName hash_table[ HASH_SIZE ] ; // hash_table[..].phone = 0 で初期化しておく
void entry( int tel , char name[] ) {
int index = hash_func( tel ) ;
// 空き席を探す                            // 説明の簡略化のため
while( hash_table[ index ].phone != 0 ) {  // 全部の席が埋まっていたときに
index = (index + 1) % HASH_SIZE ;       // 処理を抜ける対策を書かない...
}
// 空いていた席にデータを登録
hash_table[ index ].phone = tel ;
strcpy( hash_table[ index ].name , name ) ;
}
int find( int tel ) {
int index = hash_func( tel ) ;
for( ;; ) { // 説明を簡単にするため、無限ループ対策は書かない。
if ( hash_table[ index ].phone == 0 )
return -1 ;    // 空き席にたどりついた＝見つからない。
else if ( hash_table[ index ].phone == tel )
return index ; // 電話番号が一致したので見つかった
else
index = (index + 1) % HASH_SIZE ; // 次の席
}
}