8

Java HashMap負荷率がしきい値を超えた場合のサイズ変更の時間の複雑さはどうなるのだろうか? HashMap について私が理解している限り、テーブルのサイズは常に 2 の累乗の偶数であるため、テーブルのサイズを変更するたびに、すべてのキーを再ハッシュする必要はありません (間違っている場合は修正してください)。追加のスペースを割り当てずに古いテーブルからすべてのエントリをコピーすることです (JVM がそれを内部でどのように処理するかはよくわかりません)、正しいですか? 一方Hashtable、テーブル サイズとして素数を使用するため、テーブルのサイズを変更するたびにすべてのエントリを再ハッシュする必要があります。だから私の質問は、サイズ変更にまだ O(n) 線形時間がかかるのHashMapですか?

4

2 に答える 2

9

O(N)サイズ変更にはまだ時間がかかりHashMapますか？

基本的に、はい。

その結果、サイズ変更を引き起こす挿入操作には時間がかかりO(N)ます。しかし、それO(1/N)はすべての挿入で発生するため、(特定の仮定の下で)平均挿入時間はO(1).

良い負荷率がこのパフォーマンスに影響を与える可能性はありますか? より良くて速いのが好きO(N)ですか？

負荷係数の選択はパフォーマンスに影響しますが、複雑さには影響しません。

負荷率が大きい場合、ハッシュ関数とキー クラスタリングについて通常の想定を行うと、次のようになります。

  • 平均ハッシュ チェーンの長さは長くなりますが、それでもO(1)、
  • サイズ直しの頻度は減りましたが、まだまだO(1/N)です、
  • サイズ変更のコストはほぼ同じままで、複雑さは変わりませんO(N)。

...そのため、テーブルのサイズを変更するたびに、すべてのキーを再ハッシュする必要はありません (間違っている場合は修正してください。

実際には、すべてのキーを再ハッシュする必要があります。ハッシュ テーブルのサイズを 2 倍にすると、ハッシュ チェーンを分割する必要があります。これを行うには、すべてのキーのハッシュ値が 2 つのチェーンのどちらにマップされるかをテストする必要があります。(実際、ハッシュ テーブルにもオープンな組織がある場合は、同じことを行う必要があります。)

ただし、現在の世代のHashMap実装では、キーのハッシュコードを再計算する必要がないように、ハッシュコード値はチェーンされたエントリ オブジェクトにキャッシュされます。

1 つのコメントは、すべてのキーが同じハッシュコードにハッシュされる縮退のケースに言及しました。これは、ハッシュ関数の設計が不十分であるか、キーの分散が偏っているために発生する可能性があります。

これは、ルックアップ、挿入、およびその他の操作のパフォーマンスに影響しますが、サイズ変更のコストや頻度には影響しません。

于 2013-01-10T05:30:13.013 に答える
0

テーブルのサイズを変更すると、元のテーブルの内容全体を新しいテーブルにコピーする必要があるため、テーブルのサイズを変更するには O(n) の時間がかかります。ここで、n は元のテーブルの要素の数です。HashMap での操作の償却コスト (一様なハッシュの仮定を仮定) は O(1) ですが、1 回の挿入操作の最悪の場合のコストは O(n) です。

于 2013-01-10T05:37:07.217 に答える