(X,Y) ペアが特定の Z 値に対応するルックアップ関数を作成する必要があります。これに対する主な要件の 1 つは、できる限り O(1) に近い複雑さで実行する必要があることです。私の計画は、unordered_map を使用することです。
ルックアップ時間は私にとって重要ではなかったので、私は通常、ルックアップにハッシュ テーブルを使用しません。衝突なしで unordered_map を構築している限り、ルックアップ時間は O(1) になると考えているのは正しいですか?
私の懸念は、順序付けられていないマップにキーが存在しない場合、複雑さがどうなるかです。たとえば、unordered_map::find(): を使用してハッシュ テーブルにキーが存在するかどうかを判断すると、どのように答えが得られるのでしょうか? 実際にすべてのキーを反復処理しますか?
大変助かります。
標準では、多かれ少なかれ衝突解決のためにバケットを使用する必要があります。つまり、実際のルックアップ時間は、要素が存在するかどうかに関係なく、バケット内の要素の数に対しておそらく線形になります。O(lg N) にすることも可能ですが、ハッシュテーブルを正しく使えばバケツの要素数は少ないはずなので、通常はそうはいきません。
バケット内の要素数を少なくするには、ハッシュ関数が有効であることを確認する必要があります。有効な手段は、ハッシュされる型と値によって異なります。(MS の実装では、FNV が使用されます。これは、最も優れた一般的なハッシュの 1 つですが、実際に表示されるデータについて特別な知識があれば、より適切に処理できる可能性があります。) 数を減らすのに役立つ別の方法バケットあたりの要素の数は、より多くのバケットを強制するか、より小さい負荷係数を使用することです。最初に、バケットの最小初期数を引数としてコンストラクターに渡すことができます。マップに含まれる要素の総数がわかっている場合は、この方法で負荷率を制御できます。を呼び出して、テーブルがいっぱいになったら、バケットの最小数を強制することもできます
rehash。それ以外の場合は、機能があります
std::unordered_map<>::max_load_factorあなたが使用できる。何かを行うことが保証されているわけではありませんが、合理的な実装では、そうします。すでに入力されている で使用する場合unordered_mapは、おそらく後で呼び出す必要が
あることに注意してくださいunordered_map<>::rehash。
(標準の unordered_map について理解できないことがいくつかあります。負荷係数がfloatではなく である
double理由、効果が必要でない理由、自動的に呼び出さrehashれない理由などです。)
ハッシュテーブルと同様に、最悪の場合は常に線形の複雑さです (編集: 元の投稿で述べたように衝突なしでマップを作成した場合、このケースは表示されません):
http://www.cplusplus.com/reference/unordered_map/unordered_map/find/
複雑さ 平均的なケース: 定数。最悪の場合: コンテナー サイズに比例します。
戻り値 指定されたキー値が見つかった場合は要素へのイテレータ、コンテナ内に指定されたキーが見つからない場合は unordered_map::end。
ただし、 unordered_map には一意のキーのみを含めることができるため、一定時間の平均的な複雑さが表示されます (コンテナーは最初にハッシュ インデックスをチェックし、次にそのインデックスの値を反復処理します)。
unordered_map::count関数のドキュメントはより有益だと思います:
キーが k である要素のコンテナを検索し、見つかった要素の数を返します。unordered_map コンテナーは重複キーを許可しないため、コンテナー内にそのキーを持つ要素が存在する場合、関数は実際には 1 を返し、それ以外の場合は 0 を返します。
ハッシュされたデータ構造で衝突が発生しないようにすることは非常に困難です（特定のハッシュ関数やあらゆる種類のデータで不可能ではないにしても）。また、キーの数と正確に等しいテーブルサイズが必要になります。いいえ、それほど厳密である必要はありません。ハッシュ関数が比較的均一な方法で値を分散する限り、O(1)ルックアップは複雑になります。
ハッシュテーブルは通常、衝突を処理するリンクリストを備えた単なる配列です（これは連鎖方法です。他の方法もありますが、衝突を処理するための最も利用されている方法である可能性があります）。したがって、値がバケット内に含まれているかどうかを確認するには、そのバケット内のすべての値を（潜在的に）反復処理する必要があります。したがって、ハッシュ関数が一様分布を提供し、Nバケットと合計M値がある場合、バケットごとに（平均して）値が存在するはずM/Nです。この値が大きすぎない限り、これによりO(1)ルックアップが可能になります。
したがって、あなたの質問に対する少し長い答えとして、ハッシュ関数が合理的である限り、O(1)ルックアップを取得し、（平均して）O(M/N)キーを反復して「否定的な」結果を得る必要があります。