ハッシュ法
ハッシュ法とは、探索アルゴリズムの1つです。
配列やリストのように複数のデータが格納されている入れ物の中から目的のデータを探し出すのが探索であり、このデータを探索する代表的なアルゴリズムの1つが「ハッシュ法」です。
ハッシュ法の探索例
ハッシュ法とは、ハッシュ関数と呼ばれる「一定の計算式」を用いて、データの格納位置（格納アドレス）を特定する方法です。
例えば、mod(x, 10) というハッシュ関数を用いて「12」というデータを配列に格納すると、次のように位置2の場所に値が格納されます。
modは余りが返ってくる関数です。mod(x, 10)は、xを10で割ったときの余りが返ってきます。
※ハッシュ関数の「mod(x, 10)」はあくまでも例です。本来はもっと複雑な計算方法によりハッシュ値を求めます。
それでは、ハッシュ法を使って配列の中から「12」を探索します。
格納したときと同じ計算式「mod(x, 10)」を使い、格納位置を特定して参照します。
ハッシュ法の衝突
ハッシュ法では、ハッシュ関数により求めた結果が同じになる場合があります。この現象を衝突（コリジョン） もしくは シノニムの発生といいます。
例えば、上記例と同じmod(x, 10)のハッシュ関数を用いて配列に「22」を格納する場合、ハッシュ値は「2」となり衝突が発生します。
衝突発生時の対応としては、次のような手法があります。
オープンアドレス法
オープンアドレス法とは、ハッシュ関数により求めたハッシュ値がすでに利用されている場合、再ハッシュを行う方法です。再ハッシュの値には「前回のハッシュ値 + 1」を用いることが多く、そこも利用されている場合は更に「+1」をして空いている個所を探します。
チェイン法
チェイン法とは、ハッシュ関数により求めたハッシュ値がすでに利用されている場合に、連結リストとして繋いでいく方式のことです。
