実際のデータは「ハッシュ表(ハッシュテーブル)」と呼称される場所に格納されます。
さて。問題がありまして「ハッシュ関数通すと違うデータで同じハッシュ値が出てくる」事は、可能性として十分にありえます。１万のデータに対して100のグループで分けようとすれば、１グループあたり100のデータがあるはずですし。理想的なハッシュ関数であったとしても。
こーゆー「異なるデータでハッシュ値が一緒になる」事を、衝突(コリジョン:collision)って呼称しますが。
コレに対して「どんな風にデータを格納するか」ってのを考えなければいけません。
アバウトに２種類の方向性が存在しますので、簡単に。
連鎖法(チェイン法)
直接連鎖法とも呼称されるようです。
同じハッシュ値が生成された場合に連結リストを使って、ハッシュ表的に同じキー位置にデータを連結していきます。
あんまり一つのキーに対するチェインが長すぎるとハッシュにする意義が低くなります。まぁハッシュ法である以上共通に持ちうる問題点なのですが。
開番地法(オープンアドレス法)
同じハッシュ値が生成された場合に「次どこか探してみる〜」っていう手法です。
ここには更に二つの代表的(…だと思う)がありますので、順次ご紹介を。
線型操作法
キーに相当する格納場所が埋まってたら、キーの値をインクリメントして(デクリメントも…論理的にはありえるはず)、空き場所を探します。相手たらデータ突っ込みます。
２重ハッシュ法
キーに相当する格納場所が埋まってたら、別のハッシュ関数を用いて別のハッシュ値を算出、そのキーで格納をします。
…「二つのハッシュ関数で双方ともに衝突したら」…ど〜するんでしょ？
も一個些末な話を。
これも受け売りってか引用で検証はしていないのですが。
ハッシュ空間のサイズに対する言及：
ハッシュ表は，表に十分な空白があるときには，効率がよい．
おおよそ表の半分程度が空白であればいい．
シミュレイションによれば，そのくらい以上の空白があるとき，表の大きさによらず平均2回程度の比較で足りる．
ただし，ハッシュ関数がデータを均一にばらまくような性格をもっていないとうまくいかない．
ハッシュ空間の使用率に対する言及：
表の埋まりかたが70%以下なら，ハッシュ表は効率がよい．
しかしそれを越えるととたんに効率低下が生じる．
ハッシュ法における「簡単なハッシュ関数」への言及：
一般的なハッシュ関数としては，
名前の文字列を0と1のビット列として，32ビットごと(あるいは64ビットごと)に折り畳んで排他的論理和をとり，それを(先頭のビットを符号とみなさずに)正整数とみなして，表の大きさで割った余り+1を返すと，比較的よいものになる．
(1を加えた理由は表の添字が1から始まるとしたからで，C言語の配列のように添字が0から始まるなら+1は不要)．
