ハッシュ表
Hash table
データのハッシュ値を配列の添え字として使って、データをその配列に入れるという手法。 これにより、ハッシュ値の計算ができれば$ \Omicron(1)でデータを出し入れすることができる。
ハッシュ値が完全に衝突しないようにしようとすると、必然的に巨大な配列が必要になり、大半の部分が空になってしまう。
このためハッシュ値が衝突することが前提で、ある程度のサイズの配列に抑えるのが一般的。
ハッシュ値が衝突する場合、3つの対策方法がある。
内部ハッシュ法 (飽くまでハッシュ票の配列の中に収める)
実装
次以降の開いている要素に入れる。
さらに別のハッシュ関数等を使って異なる場所にする。(実際にはハッシュ関数を複数用意するのは難しいので、ハッシュ関数の入力または出力を部分的に変更する)
問題
配列のサイズが固定的なので、あらかじめ入れるデータの数を考慮する必要がある。
衝突が多くなると加速度的に遅くなる。非現実的になる。
入れるデータ量の数倍の領域がないとうまく動かない。
外部ハッシュ法