最近、面接の質問で不安を感じます。
TreeMap と HashMap の get() メソッドのパフォーマンスは?
a) 平均: 定数 (n に依存しない) 最悪: 定数 (n に依存しない)
b) 平均: 定数 (n に依存しない) 最悪: log(n) に比例
c) 平均: 定数 (n に依存しない) 最悪: (n) に比例
d) 平均: log(n) に比例 最悪: (n) に比例
どちらが正しい？
6910 次
2 に答える
8
この実装は、ハッシュ関数が要素をバケット間で適切に分散すると仮定すると、基本操作 (get および put) に対して一定時間のパフォーマンスを提供します。
ただし、負荷係数(デフォルト値 = 0.75) を変更すると、 の一部の操作のコストに影響する可能性があることに注意してくださいHashMap。
原則として、デフォルトの負荷係数 (.75) は、時間とスペースのコストの適切なトレードオフを提供します。値を大きくすると、領域のオーバーヘッドは減少しますが、ルックアップ コストが増加します (get や put を含む HashMap クラスのほとんどの操作に反映されます)。
オーバーロードされたコンストラクターの 1 つを使用して、異なる値の負荷係数を適用できます。
この実装では、containsKey、get、put、remove 操作の保証された log(n) 時間コストが提供されます。
于 2013-03-03T17:20:34.890 に答える
0
答えはdです
ツリーマップは赤黒木で実装されているため、の平均的なケースはo（log n）です。
ハッシュマップは最悪の場合o（n）を取ります
于 2013-03-03T17:27:26.670 に答える