C言語-ハッシュ法6 ハッシュ法(hashing) 6.1 ハッシュ法 データxを0 <= h(x) < Mの範囲のなるべく一様に分布する整数に変換する関数h(x)をハッシュ関数という。簡単なハッシュ関数としては、データxを整数化して、Mで割り、その余りを関数値とする。 例 文字データA,B,C,1,2,3,AAAをハッシュテーブルに格納する。 ① データ個数分の配列t(7個)を用意する。 ② データAを整数化する。Aの文字コード65(0x41)を利用し、ハッシュテーブル(配列)の個数で割った余りを求める。 余り=2 ③ 求めた余りを配列の添字にして格納する。 ④ 同様にデータ2までの余りを求めると次のようになるので、該当する配列に格納していく。 B:3, C:4, 1:0, 2:1 ⑤ データ3の余りは2となり、t(2)にはすでにデータAが格納されており、これを衝突という。 このような場合は、適当な計算式
