10

C++ の挿入/削除/検索時間std::map O(log n)ですか? O(1)ハッシュテーブルを実装することは可能ですか?

4

3 に答える 3

18

C++ マップの挿入/削除/検索時間は O(log n) ですか?

はい。

O(1) ハッシュ テーブルを実装することは可能ですか?

絶対。標準ライブラリも として提供していstd::unordered_mapます。

于 2012-10-12T20:42:21.770 に答える
6

C++ にはunordered_map型があります。hash_mapC++ 標準ライブラリにはありませんが、STL にも型が含まれています。

ここで、少しアルゴリズム理論について説明します。完全な条件の下で O(1) ハッシュ テーブルを実装することは可能であり、技術的には、ハッシュ テーブルは O(1) 挿入およびルックアップです。この場合の完全な条件は、ハッシュ関数が完全でなければならず (つまり、衝突がない)、ストレージが無限にあることです。

実際には、ばかげたハッシュテーブルを見てみましょう。どの入力キーに対しても、1 を返します。この場合、衝突が発生すると (つまり、2 回目以降の挿入で)、空き領域を見つけるためにさらに連鎖する必要があります。次の保存場所に移動するか、リンクされたリストを使用できます。

いずれにせよ、最良のケースでは、はい、ハッシュ テーブルは O(1) です (もちろん、すべてのハッシュ値を使い果たすまで、無限の量の出力を持つハッシュ関数を持つことは実際的ではないため)。最悪の場合 (たとえば、私の完全に馬鹿げたハッシュ関数を使用した場合)、ハッシュ テーブルは O(n) です。これは、指定されたハッシュから実際の値を見つけるためにストレージをトラバースする必要があるためです。正しい値。

于 2012-10-12T20:45:25.720 に答える
1

の実装std::mapはツリーです。これは標準で直接指定されていませんが、いくつかの優れた本が言っているように: "It is difficult to imagine that it can be anything else". これは、マップの挿入/削除/検索時間がO(log n)であることを意味します。

従来のハッシュ テーブルのルックアップ時間はO(n/num_slots)です。テーブル内のアイテムの予想数がスロットの数と同等になると、saturated O(1)になります。

于 2012-10-12T20:45:09.790 に答える