[解決済み] ハッシュテーブルの実行時の複雑さ (挿入、検索、削除)

質問

なぜ、ハッシュテーブル上のこれらの関数の実行時の複雑さが異なるのでしょうか?

wikiでは、検索と削除はO(n)です（ハッシュテーブルのポイントは一定のルックアップを持つことだと思ったので、検索がO(n)なら何の意味もないでしょう）。

少し前の講習会のノートを見ると、全てO(1)のものも含め、ある特定の詳細によって複雑さの幅があるようです。すべての O(1) が得られるなら、なぜ他の実装が使用されるのでしょうか?

C++やJavaのような言語で標準的なハッシュテーブルを使用している場合、時間の複雑さはどの程度になると予想されますか?

どのように解決するのですか？

ハッシュテーブル は O(1) 平均的で アモルファス のような複雑なケースもありますが O(n) 最悪の場合 時間の複雑さ [そして、ここがあなたの混乱するところだと思います]。

ハッシュテーブルの問題は O(n) 最悪の時間複雑性であり、その理由は2つあります。

1. あまりに多くの要素が同じキーにハッシュ化された場合：このキーの中を探すのに O(n) の時間がかかります。
2. ハッシュテーブルがその ロードバランス - を過ぎると、リハッシュ [新しい大きなテーブルを作成し、各要素をテーブルに再挿入すること] をしなければなりません。

とはいえ、言われているのは O(1) のため、平均的で償却された場合。

1. 多くのアイテムが同じキーにハッシュされることは非常に稀です [良いハッシュ関数を選択し、大きな負荷分散がない場合]。
2. リハッシュ操作である O(n) の後に起こる可能性があります。 n/2 の後に起こる可能性があります。 O(1) : したがって、opごとの平均時間を合計すると、: (n*O(1) + O(n)) / n) = O(1)

リハッシュの問題があるので注意 - リアルタイムのアプリケーションや低レベルのアプリケーションを必要とする レイテンシー - は、データ構造としてハッシュテーブルを使用すべきではありません。

EDITです。 ハッシュテーブルのもう一つの問題。 キャッシュ

大規模なハッシュ・テーブルで性能低下が見られるかもしれないもう一つの問題は、キャッシュの性能によるものです。 ハッシュテーブルのキャッシュ性能の問題 そのため、大規模なコレクションでは、テーブルの関連部分をメモリからキャッシュに再ロードする必要があるため、アクセス時間が長くなる可能性があります。