前回説明のハッシュ法(オープンアドレス法)は、ハッシュ衝突が発生した場合、別のハッシュ値を求めそこに格納する。配列で実装した場合であれば、ハッシュ表以上の データ件数を保存することはできない。
チェイン法
チェイン法は、同じハッシュ値のデータをグループ化して保存する方法。 同じハッシュ値のデータは、リスト構造とするのが一般的。
#define SIZE 100 int hash_func( int ph ) { return ph % SIZE ; } struct PhoneNameList { int phone ; char name[ 20 ] ; struct PhoneNameList* next ; } ; struct PhoneNameList* table[ SIZE ] ; // NULLで初期化 struct PhoneNameList* cons( int ph , char* nm , struct PhoneNameList* nx ) { struct PhoneNameList* ans ; ans = (struct PhoneNameList*)malloc( sizeof( struct PhoneNameList ) ) ; if ( ans != NULL ) { ans->phone = ph ; strcpy( ans->name , nm ) ; ans->next = nx ; } return ans ; } void entry( int phone , char* name ) { int idx = hash_func( phone ) ; hash[ idx ] = cons( phone , name , hash[ idx ] ) ; } char* search( int phone ) { int idx = hash_func( phone ) ; struct PhoneNameList* p ; for( p = hash[ idx ] ; p != NULL ; p = p->next ) { if ( p->phone == phone ) return p->name ; } return NULL ; }
文字列のハッシュ値
ここまでで説明した事例は、電話番号をキーとするものであり、余りを求めるだけといったような簡単な計算で、ハッシュ値が求められた。しかし、一般的には文字列といったような名前から、ハッシュ値が欲しいことが普通だろう。
ハッシュ値は、簡単な計算で、見た目デタラメな値が求まればいい。 (ただしく言えば、ハッシュ値の出現確率が極力一様であること)。一見規則性が解らない値として、文字であれば文字コードが考えられる。複数の文字で、これらの文字コードを加えるなどの計算をすれば、 偏りの少ない値を取り出すことができる。
int hash_func( char s[] ) { int sum = 0 ; for( int i = 0 ; s[i] != '¥0' ; i++ ) { sum = sum + s[i] ; } return sum % SIZE ; }
文字列順で異なる値となるように
前述のハッシュ関数は、”ABC”さんと”CBA”さんでは、同じハッシュ値が求まってしまう。文字列順で異なる値が求まるように改良してみる。
int hash_func( char s[] ) { int sum = 0 ; for( int i = 0 ; s[i] != '¥0' ; i++ ) { sum = sum*2 + s[i] ; // sum = (sum * 小さい素数 + s[i]) % 大きい素数 ; } return sum % SIZE ; }