Judge(AOJ)が提供している「アルゴリズムとデータ構造入門」(ALDS1)の4_C問題をC++で解いてみました。ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。ハッシュ(辞書)を学びます。Dictionary)問題はリンク先をご覧ください。Dictionaryハッシュについて学びます。コンテナを使ったプログラムを紹介します。用意します(8ー11行目)。用意します(13ー24行目)。コンテナを全探索します。Exceeded)判定となります。回のループが発生して、間に合わなくなります。コンテナに値を格納すると、値が存在しない場合にコンテナを最後まで走査します。コンテナに値を分けて格納すると、この問題は解決します。文字列と格納するコンテナを紐づけるためにハッシュ(ハッシュ値)を使います。「ハッシュ関数」には、「任意のデータから、別の(多くの場合は短い固定長の)値を得るための操作、または、その様な値を得るための関数のこと」とあります。値に紐づけるようなハッシュ関数を作ります。コンテナは、65536(=216)個用意します(7、8行目)。平均的に散らばるように線形合同法の乱数生成を参考にしました。紹介されている3番目の例を採用しました(10ー18行目)。文字列からハッシュを求めて、ハッシュを添え字とするコンテナに文字列を格納します(20-24行目)。文字列からハッシュを求めて、該当するコンテナが与えられた文字列を含むか判定します(26-38行目)。個のコンテナに分散して格納します。文字列とコンテナの紐づけが十分に散らばれば、コンテナの要素が平均化されて、結果的に少なくなります。ハッシュ関数に線形合同法を使いました。線形合同法を実際の乱数に使うには好ましくない場合があるので注意してください。ハッシュ関数に採用したのは、計算量が少ないためです。以下が、C++プログラムとなります。