チェイン法の説明を行う。

前回説明のハッシュ法は、ハッシュ衝突が発生した場合、べつのハッシュ値を そこに格納する。しかし、配列で実装した場合であれば、ハッシュ表以上の データ件数を保存することはできない。

チェイン法

チェイン法は、同じハッシュ値の物をまとめて保存する方法。 このため、同じハッシュ値のデータは、リスト構造とするのが一般的。

#define SIZE 100
int hash_func( int ph ) { return ph % SIZE ; }
struct List {
int phone ;
struct List* next ;
} ;
struct List* table[ SIZE ] ; // NULLで初期化
void entry( int ph ) {
int idx = hash_func( ph ) ;
hash[ idx ] = cons( ph , hash[ idx ] ) ;
}
int search( int ph ) {
int idx = hash_func( ph ) ;
struct List* p ;
for( p = hash[ idx ] ; p != NULL ; p = p->next ) {
if ( p->phone == ph )
return 1 ;
}
return 0 ;
}

文字列をハッシュ値に

ここまでで説明した事例は、電話番号をキーとするものであり、 余りを求めるだけといったような簡単な計算で、ハッシュ値が求められた。 しかし、一般的には文字列といったような名前から、ハッシュ値が欲しいことが普通。

ハッシュ値は、簡単な計算で、見た目デタラメな値が求まればいい。 (ただしく言えば、ハッシュ値の出現確率が一様)。 一見規則性が解らない値として、文字であれば文字コードが考えられる。 複数の文字で、これらの文字コードを加えるなどの計算をすれば、 偏りの少ない値を取り出すことができる。

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

実際には、幅広い値が求まり、文字列順序で違う値が求まるように、工夫をすることが多い。

  sum = sum + s[i] ; // 基本
sum = (sum*2 + s[i]) ; // 幅広い値で文字順序に依存
sum = ( sum*A + s[i] ) % B ; // A:小さい素数、B:巨大な素数