Java

JavaTreeMapソースコード分析



Java Treemap Source Code Analysis



まず、ソースコード（ 署名 ）。

ソースコードは次のように分析されます。



パブリッククラスTreeMap

AbstractMapを拡張します



NavigableMap、Cloneable、java.io.Serializableを実装します

HashMapと比較して、TreeMapはインターフェイスNavigableMapを継承していることがわかります。これは、TreeMapとHashMapの違いを決定するインターフェイスです。 HashMap の キー 乱れている、 TreeMap の キー 整然とした

第二に、インターフェース NavigableMap



NavigableMap定義：

パブリックインターフェイスNavigableMapはSortedMapを拡張します

NavigableMapがSortedMapを継承していることがわかり、SortedMapの定義を確認します。

パブリックインターフェイスSortedMapはMapを拡張します

SortedMapはその名前に似ており、マップが順序付けられていることを示します。この順序は通常、Comparableインターフェイスによって提供されるキーの自然な順序を指します。または、SortedMapインスタンスを作成するときにComparatorを指定することで決定できます。コレクションビュー（entrySet、keySet、valuesメソッドによっても提供されるHashMapなど）を使用してSortedMapインスタンスを反復処理すると、キーの順序が反映されます。 ComparableとComparatorの違いは次のとおりです（ここを参照）。

Comparableは通常、Studentクラスの定義など、クラスの自然な順序を表します。学生番号がデフォルトの順序です。

コンパレータは通常、特定の状況におけるクラスの特別な分類を表し、カスタムソートが必要です。たとえば、Studentクラスの年齢で並べ替えたいと思います。

SortedMapにキーを挿入するクラスクラスは、Comparableクラスを継承する（またはコンパレータを指定する）必要があり、2つのキーを（k1.compareTo（k2）またはcomparator.compare（k1、k2）を介して）比較する方法を決定します。それ以外の場合、挿入すると、ClassCastExceptionの例外が報告されます。したがって、SortedMapのキーの順序は、equalsメソッドと一致している必要があります。つまり、k1.compareTo（k2）またはcomparator.compare（k1、k2）が真の場合、k1.equals（k2）も真である必要があります。 SortedMapを紹介した後、NavigableMapに戻ってください。 NavigableMapはJDK1.6の新機能です。 SortedMapに基づいて、検索ターゲットに最も近い要素を返すために、いくつかの「ナビゲーションメソッド」が追加されました。たとえば、次の方法です。

lowerEntryは、指定されたMap.Entryよりも小さいすべての要素を返します

floorEntryは、指定されたMap.Entry以下のすべての要素を返します。

ceilingEntryは、指定されたMap.Entry以上のすべての要素を返します。

highEntryは、指定されたMap.Entryより大きいすべての要素を返します

第三に、デザインコンセプト（ デザインのコンセプト ）。

TreeMapは、二分探索木である赤黒木に基づいています。二分探索木のいくつかの特性を思い出してみましょう。

二分探索木

二分探索木（BST）を最初に見ると、次のようになりますか？ 。

私は誰もがこの絵に精通していると信じています、重要なポイントは次のとおりです：

左側のサブツリーの値はルートノードよりも小さく、右側のサブツリーの値はルートノードよりも大きくなっています。

二分探索木の利点は、問題が判断されるたびに問題のサイズを半分に減らすことができることです。したがって、二分探索木がバランスしている場合、要素を見つける時間の複雑さはlog（n）であり、これは高さです。木の。ここで深刻な問題を考えています。二分探索木が問題のサイズを半分に減らした場合、三叉神経探索木は問題のサイズを3分の2に減らしません。これは良くありません、など、私たちはまだクワッドサーチツリー、5プロングサーチツリーがある可能性があります...より一般的なケースの場合：

Kツリー探索木のn個の要素Kの効率はどれくらいですか？ K = 2はいつですか？

Kフォーク探索木

上記の私の分析に従うと、誤解に陥る可能性があります。

三叉探索木が問題のサイズを3分の2に縮小すると、必要な比較操作の数は2倍になります（二分探索木は問題のサイズを半分に縮小し、1回の比較操作のみが必要です）。

より一般的なケースでは、これらを2回無視することはできません。

n個の要素の場合、Kツリー検索ツリーに必要な比較の平均数はk * log（n / k）です。

極端な場合k = nの場合、Kフォークツリーは線形テーブルに変換され、複雑さもO（n）になります。問題が数学的に解決される場合、それは次と同等です。

nが固定値の場合、kをとると、k * log（n / k）の値が最小になりますか？

K * log（n / k）は、対数の法則に従ってln（n）* k / ln（k）に変換できます。また、ln（n）は定数であるため、kの最小値を取ることと同じです。 / ln（k）。 。この質問は、多くのことを学んでいるだけの人にとっては簡単です。ここで直接結果を見てみましょう。

k = eの場合、k / ln（k）は最小値を取ります。

自然数eの値は約2.718です。二分木が基本的に最適解であることがわかります。 NodejsのREPLで次のことを行います

function foo（k）{return k / Math.log（k）}

> foo（2）

2.8853900817779268

> foo（3）

2.730717679880512

> foo（4）

2.8853900817779268

> foo（5）

3.1066746727980594

k = 3はk = 2よりも小さいように見えます。つまり、三叉探索木は二分探索木よりも優れているはずですが、なぜ二分木が人気があるのでしょうか。後で私は全能のstackoverflowで答えを見つけました。主なアイデアは次のとおりです。

今日のCPUは、バイナリロジックコード用に最適化でき、トリプルロジックは複数のダブルロジックに分割されます。

これはおそらく、比較操作のために問題のサイズを最大半分に減らすことができるため、二分木が非常に人気がある理由を理解するでしょう。さて、少し遠いです。赤い木に戻りましょう。

4、赤黒木の自然

まず、赤黒木の外観を見てください。

リーフノードは、上の図のNILノードです。いくつかの国内教科書にはいくつかのNILノードがあります。描画時にこれらのNILノードを省略することがありますが、明確にする必要があります。リーフノードとは、これらのNILノードを指します。

赤黒木は、ツリーが次の5つのルールによってバランスが取れていることを保証します。

ツリーのノードは赤と黒のみです。

ルートノードは黒です

葉の節は黒です

赤いノードのバイトポイントは黒でなければなりません

任意のノードから、後続のリーフノードのパスまで、黒いノードの数は同じです。

上記の5つの条件を満たすと、ルートノードからリーフノードまでの最長パスが、ルートノードからリーフの最短パスまでの2倍を超えないことが保証されます。実際、これは非常によく理解されており、主に4と5の性質を使用して、次の簡単な説明があります。

ルートノードからリーフノードへの最短パスでブラックノードの数がBであるとすると、プロパティ5によれば、ルートノードからリーフノードへの最長パスもブラックノードの数であり、最長のケースは、2つの黒いノードごとの中央です。赤のノード（つまり、赤と黒の場合）があるため、赤のノードは最大でB-1になります。これは上記の結論を証明します。

5、赤黒木操作

赤黒木の挿入、削除、左利き、右利きの操作は、視覚化するのが一番いいと思いますし、文字表現もやや面倒です。私は醜さを提供するためにここにいるのではありません。私はv_July_vのようにもっとオンラインで見つけることができますあなたは赤黒木を完全に理解しています。ここでswfの説明ビデオをお勧めします（ビデオは英語です、恐れることはありません、焦点は写真にありますか??）、約7分、あなたは参照することができます。インタラクティブな赤黒木視覚化ページもあり、上に移動して操作したり、いくつかのノードを挿入したり、いくつかのノードを削除して再生したり、左利きの右利きの再生方法を確認したりできます。

概要

TreeMapのキーが注文されます。操作の追加、削除、および変更の時間計算量はO（log（n））です。赤と黒の木のバランスを保つために、必要に応じて回転します。

HashMapのキーは順序付けられていません。操作の追加、削除、および変更の時間計算量はO（1）です。動的な拡張を実現するために、必要に応じてサイズ変更が実行されます。

このチュートリアルは、Shangsi Valley Education Big Data ResearchInstituteによって作成されています。再版が必要な場合は、出典を明記してください。