Java の TreeMap の内部動作-＆＃＆チュートリアル-php.cn

Java の TreeMap の内部動作

WBOY

リリース： 2023-08-26 11:41:16

転載

645 人が閲覧しました

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

Java の TreeMap の内部動作

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

Red Black TreeとTreeMapの関係

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

各ノードには、赤または黒で表される追加ビットが含まれています。これらの色は、木のバランスを保つために使用されます。
ルートノードの色は常に黒です。
赤いノードは、隣接するノードと同じ色の別のノードを持つことはできません
ルートノードから空のノードまで、すべてのパス上の黒いノードの数は同じでなければなりません

Java の TreeMap の内部動作

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

Java の 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);
   }
}

ログイン後にコピー

＃＃＃結論は＃＃＃