1

私が理解しているように、JavaにはHashTableに新しいキーを挿入するオプションがあります。これは以下によって行われます:

 Hashtable<String,String> hashTable=new Hashtable<String,String>();
 hashTable.put("Donald", "Trump");

ドナルドが鍵で、トランプが価値です。値「TrumpY」を「Donald」に追加する場合は、同じ操作を使用します。

 hashTable.put("Donald", "TrumpY");

この操作の時間の複雑さについて質問があります。私が理解しているように、時間の複雑さはO(1). しかし、これは 1 回目と 2 回目の操作に関連していますか? 最初は新しいキーをハッシュ テーブルに追加する必要があり、2 つ目は既存のキーに値のみを追加する必要があるためです。

4

2 に答える 2

3

値を追加する必要があるスロットを見つけるには、マップはこのスロットの位置を見つける必要があります。これを行うには、キーのハッシュコードを使用します。基盤となる実装によっては、衝突処理（連鎖）が発生する場合があります。したがって、キーがすでに存在する場合、2番目の操作は通常、ハッシュ計算+ルックアップ+必要な値の設定に時間がかかります。

主題についてもっと読む：http：//en.wikipedia.org/wiki/Hash_table

于 2013-02-28T14:43:19.680 に答える
0

初めてキーを挿入すると、の新しいインスタンスを作成する必要があるため、時間がかかりますjava.util.Hashtable.Entry。

キーの既存の値を置き換える場合は、既存のインスタンスのvalue参照に新しい値を割り当てるだけで済みます。Entry

于 2013-02-28T14:55:08.820 に答える