既知のサイズnのキーの配列またはリストがあります。このリストに一意のキーがいくつあるかは不明です。0からnまでの可能性があります。キーは特定の順序ではなく、実際にはそうすることはできません。これらのキーには、等しいまたは不等式のみの、より大きいまたはより小さいという概念がないためです。ハッシュマップと言う前に、そのアイデアにレンチを投げると思うもう1つの条件があります。各キーの値はプライベートです。キーについて取得できる唯一の情報は、それが別のキーと等しいかどうかです。だから基本的に：
class key{
private:
T data;
...
public:
...
bool operator==(const key &k){return data==k.data}
bool operator!=(const key &k){return data!=k.data}
};
key array[n];
さて、配列内のキーの半分以上が線形時間で同じキーであるかどうかを判断できるアルゴリズムはありますか？そうでない場合は、O（n * log（n））はどうですか？たとえば、配列に3つの一意のキーしかないとします。配列の60％には、key.data == foo、30％key.data == bar、および10％key.data==derpのキーが入力されています。アルゴリズムは、50％を超えるキーが同じ種類（data == fooのキー）であると判断し、それらのキーの1つを返すだけで済みます。
私の教授によると、それはO（n）時間で実行できますが、O（n * log（n））時間で実行できるものを見つけるだけでよいと彼は言います。