HashMapが新しいノードが挿入されると内部ノードを再割り当てするのとは異なり、TreeMapは通常、新しいノードを追加するときにノードを再割り当てしません。違いは、 anArrayListと aの違いとして非常に大まかに説明できますLinkedList。最初のものはサイズ変更のために再割り当てされますが、2番目のものはそうではありません。そのため、 a の初期サイズを設定することは、 aTreeMapの初期サイズを設定しようとするのとほぼ同じくらい無意味LinkedListです。
速度の違いは、2 つのコンテナーの時間の複雑さが異なるためです。Nノードを a に挿入するのHashMapは is ですがO(n)、TreeMapit のO(N*LogN)場合は、1000000 ノードの場合、漸近的な差の約 20 倍になります。漸近的な複雑さの違いは、個々のアルゴリズムによって決定される定数が異なるため、タイミングの違いに直接変換されませんが、非常に大きな入力でどのアルゴリズムが高速になるかを判断する良い方法として機能します。
TreeMap の配列の初期サイズを設定できると仮定するのは間違っていますか?
はい、その仮定は正しくありません。ATreeMapには配列がありません。ATreeMapは、2 つの子を持つバイナリ ノードを使用します。
ツリー ノード内の子の数をパラメーターにすることを提案している場合は、それが検索時間にどのように影響するかを把握する必要があります。O(log2N)そして、検索時間をO(log2M * log2(N/M))どこから何まで回すと思いますか?Nは要素M数であり、ノードの子の平均数です。(そして、私はいくつかの楽観的な仮定をしています...) それは「勝利」ではありません。
それがとても遅いのは別の理由がありますか？
はい。TreeMap最適な状況下でa (大) が a (大) に比べて遅い理由はHashMap、N 個のエントリを持つバランスのとれた二分木を使用したルックアップでは、大まかlog2Nなツリー ノードを調べる必要があるためです。対照的に、最適なHashMapルックアップでは、1 つのハッシュコード計算とハッシュO(1)チェーン ノードの参照が含まれます。
ノート：
TreeMapバランスの取れたツリーを提供するバイナリ ツリー構成を使用するためO(log2N)、最悪の場合のルックアップ時間です。HashMapパフォーマンスは、ハッシュ関数とキー空間の衝突率に依存します。すべてのキーが同じハッシュ チェーンで終わる最悪のケースでは、HashMaphasO(N)ルックアップが発生します。HashMapとパフォーマンスが向上します。O(N)つまり、~2^31 エントリです。しかし、これHashMapほど大きな がある場合は、おそらくメモリ使用量とガベージ コレクションの特性が優れた代替マップの実装を検討する必要があります。ツリーマップは常にバランスが取れています。ツリーにノードを追加するたびに、提供されたコンパレーターによってノードがすべて順番に並べられていることを確認する必要があります。ツリーマップはスムーズにソートされたノードのグループとノードを簡単にトラバースするように設計されているため、サイズは指定されていません。
ハッシュマップには、そこに格納するもののために十分な量の空き領域が必要です。私の教授は、オブジェクトまたはそのハッシュマップに保存しているものの5倍のスペースが必要だといつも言っていました。したがって、ハッシュマップの最初の作成からサイズを指定すると、ハッシュマップの速度が向上します。そうしないと、予定よりも多くのオブジェクトがハッシュマップに入る場合、ハッシュマップを「サイズアップ」する必要があります。
（スペルのために編集されています）