15/07/08 06:31:21.01 7qvaXLbV.net
>>143
グループAに数字が50個くらいあって、それぞれの値の範囲は0～99であることがわかっている。
新しく0～99の値xが与えられたとき、Aにxが含まれるかどうかを調べ、含まれない場合は追加する効率的な方法は?
簡単な方法としては、100要素のboolean配列A[100]を用意してA[x]を調べて
A[x]がfalseならtrueに変えればいい。
これがハッシュ表の基本的な考え方。実際には常にxをそのまま添え字に使えるわけではないので、
xを何らかのルール(ハッシュ関数)で手頃な範囲の数値に変換するわけ。
こうやって値を追加していったとき、Aにどういう順序で値が挿入されたか後で知る方法はないだろ?