ハッシュテーブル操作の時間複雑度はO（1）またはO（N）ですか？

Question

データ構造アルゴリズムの質問に答えるときに、Hashtable（Javaのコレクションフレームワークの中の1つ）を使って問題を解くと、Hashtableの複雑さを考えなければならないか、O（1）と安全に考えることができますか？

私はO（1）として扱われている多くの記事を見てきましたが、Javaで実行された特定のキーの値を取得するために実行されるハッシングアルゴリズムのような、

Answer 1

質問に答えるには、実際にハッシュテーブルがどのように機能するかを考慮する必要があります。 HashTablesは基本的にキーをその値にマップする配列です。配列内の各キーの位置は、ハッシュ関数に依存します（ハッシュ関数は、入力を単一の出力値にマッピングします）。ハッシュ関数がO（1）であると仮定しましょう。

は値を挿入：我々はそれを格納する場所を見つけるためにキーにハッシュ関数（F）を使用してハッシュテーブルに何かを挿入したい場合は

は、その後、我々は値を格納しますその場所で配列に何かを挿入するたびに、ハッシュ関数がO（1）なので、O（1）時間かかるでしょう。ハッシュテーブルの値を検索する場合も同様です。ハッシュテーブル内私たちXの場所を教えてくれます、我々はf（x）がために解決しなければならない値のxを検索したい場合は

：値の検索

。これは、ハッシュテーブルを検索することもO（1）であることを意味します。

根底にある複雑さを認識し：上記

答えが真であるが、ハッシュ関数は決して（達成することが困難であることができる）任意の入力に対して同じ出力を生成しない場合にのみ。これは、ハッシュ関数がそのような衝突を避けるために代替メソッドを使用することがあることを意味します。これらの代替方法は、多くの場合、最初の場所に到着するためにO（1）になりますが、空の場所を見つけるために追加の操作（線形検索など）が必要になります。

本質的にハッシュテーブル操作（挿入と検索）はO（1）ですが、テーブル内に衝突がある場合（複数のキーが同じ場所を指している場合）、これらの操作に少し時間がかかります。