Java の TreeMap の内部動作

TreeMap は、NavigableMap インターフェイスを実装する Java Collection Framework のクラスです。マップの要素をツリー構造に格納し、キーと値のペアを並べ替えられた順序で格納するための効率的な代替手段を提供します。内部的に、TreeMap は赤色のブラック ツリー (自己均衡バイナリ検索ツリーです)。TreeMap は、要素の並べ替え順序を維持できるように、Comparable Interface またはカスタム Comparator を実装する必要があります。実装しないと、java.lang.ClassCastException が発生します。この記事の目的は、次のとおりです。 TreeMap が Java の内部でどのように動作するかを説明します。

Java の TreeMap の内部動作

TreeMap の内部動作を理解するには、赤黒ツリー アルゴリズムの概要を理解する必要があります。これは、TreeMap が要素の保存に赤黒ツリー アルゴリズムを使用するためです。

Red Black TreeとTreeMapの関係

赤黒ツリーは自己平衡二分探索ツリーであり、そのプロパティは次のとおりです:

• 各ノードには、赤または黒で表される追加ビットが含まれています。これらの色は、木のバランスを保つために使用されます。

• ルート ノードの色は常に黒です。

• 赤いノードは、隣接するノードと同じ色の別のノードを持つことはできません

• ルート ノードから空のノードまで、すべてのパス上の黒いノードの数は同じでなければなりません

次に、TreeMap の構造を見てみましょう。

TreeMap に要素を追加すると、最初のエントリが最初に追加され、2 番目の要素から、現在のエントリのキーが前のエントリより大きいか小さいかをチェックします。値は親エントリの左側に追加され、より大きい値が右側に追加されます。

ツリーマップのコンストラクター

プログラムで TreeMap コレクションを使用するには、まず TreeMap クラスのインスタンスを作成する必要があります。そのために、Java は次のコンストラクターを提供します。

• TreeMap(): 空の TreeMap コレクションを作成します。

• TreeMap(Map mapInstance): 別のマップのエントリを使用してツリー マップを作成できます

• TreeMap(Comparator comparatorInstance): コンパレータを使用して並べ替えられた空のツリー マップを作成できます。

• TreeMap(SortedMapsortedmapInstance): 並べ替えられたマップのエントリを使用してツリー マップを作成することもできます。

上で議論した点をよりよく理解するために、いくつかの例について説明しましょう。

＃＃＃例＃＃＃

次の例では、空の TreeMap を作成し、「put()」メソッドを使用していくつかの要素をそこに保存します。 for-each ループを使用して詳細を出力します。結果はソート順に表示されます。

rree

出力

import java.util.*;
public class Example1 {
   public static void main(String[] args) {
      // creating a TreeMap
      TreeMap<String, Integer> TrMap = new TreeMap<>();
      // Adding elements in the map
      TrMap.put("Kurti", 4000);
      TrMap.put("Shirt", 3000);
      TrMap.put("TShirt", 1500);
      TrMap.put("Watch", 2000);
      TrMap.put("Perfume", 2500);
      // printing the details of map 
      System.out.println("Elements of the map: ");
      // iterating through the map
      for (String unKey : TrMap.keySet()) {
         // printing details of each node
         System.out.println("Item: " + unKey + ", Price: " + 
TrMap.get(unKey));
      }
      String frstKey = TrMap.firstKey(); // accessing first key
      String lstKey = TrMap.lastKey(); // accessing last key
      System.out.println("Accessing name of first key in Map: " + 
frstKey);
      System.out.println("Accessing name of last key in Map: " + 
lstKey);
   }
}

＃＃＃結論は＃＃＃

この記事は TreeMap を定義することから始め、次のセクションでその内部の仕組みについて説明しました。 TreeMap は、自己平衡型二分探索ツリーである赤黒ツリーを使用して要素を保存します。さらに、TreeMap がどのように機能するかを示す例についても説明しました。

以上がJava の TreeMap の内部動作の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。