文字列のハッシュ値
ここまでで説明した事例は、電話番号をキーとするものであり、余りを求めるだけといったような簡単な計算で、ハッシュ値が求められた。しかし、一般的には文字列といったような名前から、ハッシュ値が欲しいことが普通だろう。
ハッシュ値は、簡単な計算で、見た目デタラメな値が求まればいい。 (ただしく言えば、ハッシュ値の出現確率が極力一様であること)。一見規則性が解らない値として、文字であれば文字コードが考えられる。複数の文字で、これらの文字コードを加えるなどの計算をすれば、 偏りの少ない値を取り出すことができる。
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 ; }
上記のプログラムの、sum = sum*2 + s[i] では、2倍していった数を最後に SIZE で割っているだけなので、文字が長い場合文字コードの値の違いが sum の中に残らない場合も考えられる。こういった場合には、以下のような方法も考えられる。大きな素数で割ることで、余りの中に、元の数の値の違いの影響が残る。これは、疑似乱数生成での剰余法(or 線形合同法)の考え方を取り入れた方法ともいえる。
#define PRIME_B 大きな素数 #define PRIME_A 小さな素数 int hash_func( char s[] ) { int sum = 0 ; for( int i = 0 ; s[i] != '¥0' ; i++ ) { sum = (sum * PRIME_A + s[i]) % PRIME_B ; } return sum % SIZE ; }