Java は赤黒木を使用して TreeMap クラスを実装するため、put() と get() の効率は lg(N) です。ここで、N = 個別のキーの数、または N = 実行する予定の挿入/取得の数です。 ?
たとえば、
TreeMap<Integer, ArrayList<String>>
次のデータを保存します。
100 万の <1, "bob"> ペアと 100 万の <2, "jack"> ペア (文字列は、キーに対応する arraylist 値に挿入されます)
最終的なツリーマップには 2 つのキーがあり、それぞれが何百万もの "bob" または "jack" 文字列の配列リストを格納します。時間効率は lg(2mil) か lg(2) か? それが赤黒木がどのように機能するかなので、それは lg(2) だと推測していますが、確認したかっただけです。
2 つのペアを持つ TreeMap のパフォーマンスは、以前に行われた重複追加の数に関係なく、N=2 として動作します。余分な追加の「メモリ」がないため、オーバーヘッドが発生する可能性はありません。
そうです、時間効率は「log 2」であると非公式に仮定できます。
big-O表記は小さなサイズに関連するのではなく、漸近的な効率に関連することを意図しているため、かなり無意味ですが。O(N^3) アルゴリズムは、N=2 の場合、O(log N) アルゴリズムよりも簡単に高速になります。
この場合、ツリーマップはあなたが説明したlg(n)場所です。n=2マップには、1 つの arraylist と別の arraylist の 2 つの値しかありません。それらの中に何が含まれていても、マップは 2 つの値しか認識しません。
あなたの質問には直接関係ありませんが、これにはツリーマップを使用しないことを検討することをお勧めします...つまり、「ボブ」または「ジャック」リスト内に保存されているデータにどのようにアクセスする予定ですか? これらはO(n)、ある種のバイナリ検索または何かを使用しない限り、検索になりますn。ここでは100万です。最終目標について詳しく説明すれば、より包括的な解決策を達成できる可能性があります。