Java HashMapのkeySetの償却分析が何であるか知っている人はいますか? O(1)?
それらを繰り返していますO(n)か？
質問する
2065 次
2 に答える
6
map.keySet()マップに格納されているキーセットへの参照を返すだけなので、明らかに O(1) 操作です。
反復はそのセットに対するループであり、それ自体がマップのバケットに対するループを内部的に使用するため、操作には n+m に比例する時間がかかります。ここで、n はキーセットのサイズ、m はマップの容量です。
そのため、マップの容量が非常に大きく、エントリが 1 つしかない場合、キーが 1 つしかない場合でも、keySet の反復はすべてのバケットをループします。
big-o表記でそれをどのように翻訳するかわかりません。
それぞれ 1 つのエントリを持つ 2 つのマップで簡単なテストを実行しました。1 つのマップの容量は 1,000 万で、もう 1 つのマップの容量は 1 です。キーセット (両方のケースで 1 つのアイテム) の反復には、大きなマップでは 3,500 倍の時間がかかります (18,843,092 ns 対 5434 ns)。
ps: HashSet の javadoc の内容に似ています。
このセットを反復処理するには、HashSet インスタンスのサイズ (要素の数) とバッキング HashMap インスタンスの「容量」 (バケットの数) の合計に比例する時間が必要です。したがって、反復のパフォーマンスが重要な場合は、初期容量を高く設定しすぎないようにする (または負荷係数を低く設定しすぎない) ことが非常に重要です。
于 2012-08-10T14:05:24.660 に答える
1
keySetのソース コードを確認できます。
Set の反復は、これに基づく O(n) です
于 2012-08-10T14:06:15.160 に答える