Java の TreeMap の機能

この記事を読んでいるということは、 Mapインターフェイスとその使用法 についてよくご存じのことでしょう。そうでない場合は、こちらからどうぞ。今日は、TreeMap の実装機能、具体的にはHashMapとの違いと正しい使用方法について説明します。

TreeMap、HashMap、LinkedHashMap の比較

Mapインターフェースの最も一般的に使用される実装はHashMapです。使いやすく、データへの高速アクセスが保証されているため、ほとんどのタスクに最適です。ほとんどですが、すべてではありません。場合によっては、データを構造化された形式で保存し、データ内を移動できるようにする必要があります。この場合、Mapインターフェースの別の実装であるTreeMapが役に立ちます。 TreeMap はNavigableMapインターフェイスを実装します。これはSortedMapを継承し、SortedMap はMapインターフェイスを継承します。 NavigableMapインターフェイスとSortedMapインターフェイスを実装することにより、TreeMap はHashMapにはない追加機能を獲得しますが、これにはパフォーマンスの面で代償が伴います。LinkedHashMapクラスもあります。これを使用すると、データを特定の順序 (追加された順序) で保存できます。これら 3 つのクラスの違いを理解するには、次の表を参照してください。 ご覧のとおり、これらのクラスには多くの共通点がありますが、いくつかの違いもあります。このクラスはTreeMap最も多機能ですが、常にnullキーとして保存できるわけではありません。また、TreeMap 要素へのアクセス時間が最も長くなります。したがって、データを並べ替えた形式で保存する必要がない場合は、HashMapまたは を使用することをお勧めしますLinkedHashMap。

赤黒檀の木

おそらくお気づきかと思いますが、内部ではTreeMap赤黒ツリーと呼ばれるデータ構造が使用されています。この構造にデータを格納することで、データの格納順序が保証されます。この木は何ですか？考えてみましょう! 数値と文字列のペアを保存する必要があると想像してください。16、20、52、55、61、65、71、76、81、85、90、93、101の数字がキーになります。データを従来のリストに保存し、キー 101 の要素を検索する必要がある場合は、13 要素すべてを反復して検索する必要があります。13 個の要素の場合、これは重要ではありませんが、100 万個の要素を扱う場合は大きな問題が発生します。このような問題を解決するために、プログラマはもう少し複雑なデータ構造を使用します。そこで、赤黒の木に出会ってください！

https://algorithmtutor.com/Data-Structures/Tree/Red-Black-Trees/

必要な要素の検索はツリーのルート (この場合は 61) から始まります。次に、必要な値との比較が行われます。値が小さい場合は左に移動し、値が大きい場合は右に移動します。nullこれは、必要な値が見つかるか、値を持つ要素(木の葉)が見つかるまで発生します。赤と黒の色は、ツリーの移動とバランスをとりやすくするために使用されています。赤黒ツリーを構築する際には必ず従わなければならないルールがあります。

• 根元は黒く着色する必要があります。
• 木の葉は黒くなければなりません。
• 赤いノードには 2 つの黒い子ノードが必要です。
• 黒ノードは任意の子ノードを持つことができます。
• ノードからリーフまでのパスには、同じ数の黒いノードが含まれている必要があります。
• リーフの代わりに新しいノードが追加されます。

ルール 3、4、および 5 を一緒に見ると、ノードに色を付けるとツリー内のナビゲーションがどのように高速化されるかがわかります。黒いノードを通るパスは、赤いノードを通るパスよりも常に短くなります。したがって、ツリーの全体のサイズは黒いノードの数によって決まり、このサイズを「黒の高さ」と呼びます。赤黒ツリーはさまざまなプログラミング言語で実装されています。インターネット上には Java の実装がたくさんあるので、これについては長くは説明しませんが、機能については引き続き理解していきますTreeMap。

SortedMap インターフェイスおよび NavigableMap インターフェイスから派生したメソッド

同様にHashMap、TreeMapインターフェイスを実装します。これは、インターフェイスに必要なすべてのメソッドがあるMapことを意味します。ただし、さらに、インターフェイスとを実装し、そこから追加の機能を取得します。 —ソートされたデータセットに関連するメソッドを拡張および追加するインターフェース: TreeMapHashMapTreeMapSortedMapNavigableMapSortedMapMap

• firstKey(): マップの最初の要素のキーを返します。
• lastKey(): 最後の要素のキーを返します。
• headMap(K end): 先頭からキーを持つ要素まで、現在の要素のすべてを含むマップを返しますend。
• tailMap(K start): 現在の要素のすべての要素を含むマップを返します。その要素から始まりstart最後で終わります。
• subMap(K start, K end)start: 要素から始まり、 key を持つ要素で終わる、現在の要素のすべてを含むマップを返しますend。

NavigableMap— マップ要素間を移動するためのメソッドを拡張および追加するインターフェイスSortedMap:

• firstEntry(): 最初のキーと値のペアを返します。
• lastEntry(): 最後のキーと値のペアを返します。
• pollFirstEntry(): 最初のペアを返して削除します。
• pollLastEntry(): 最後のペアを返して削除します。
• ceilingKey(K obj): キー obj 以上の最小のキー k を返します。そのようなキーがない場合は null を返します。
• floorKey(K obj): キー obj 以下の最大のキー k を返します。そのようなキーがない場合は null を返します。
• lowerKey(K obj): キー obj より小さい最大のキー k を返します。そのようなキーがない場合は null を返します。
• higherKey(K obj): キー obj より大きい最小のキー k を返します。そのようなキーがない場合は null を返します。
• ceilingEntry(K obj): CeilingKey(K obj) メソッドに似ていますが、キーと値のペア (または null) を返します。
• floorEntry(K obj): FloorKey(K obj) メソッドに似ていますが、キーと値のペア (または null) を返します。
• lowerEntry(K obj): lowerKey(K obj) メソッドと似ていますが、キーと値のペア (または null) を返します。
• higherEntry(K obj):higherKey(K obj) メソッドと似ていますが、キーと値のペア (または null) を返します。
• descendingKeySet(): 逆順にソートされたすべてのキーを含む NavigableSet を返します。
• descendingMap(): 逆順にソートされたすべてのペアを含む NavigableMap を返します。
• navigableKeySet(): 格納順にすべてのキーを含む NavigableSet オブジェクトを返します。
• headMap(K upperBound, boolean incl): 先頭から upperBound 要素までのペアを含むマップを返します。incl 引数は、upperBound 要素を返されたマップに含めるかどうかを指定します。
• tailMap(K lowerBound, boolean incl): 機能は前のメソッドと似ており、 lowerBound から最後までのペアのみが返されます。
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): 前のメソッドと同様に、 lowerBound から upperBound までのペアが返され、引数 lowIncl と highIncl は、新しいマップに境界要素を含めるかどうかを示します。

実装自体ではTreeMap、私たちがよく知っているコンストラクターに加えて、コンパレーターのインスタンスを受け入れるコンストラクターがもう 1 つ追加されています。このコンパレータは、要素が格納される順序を決定します。

ツリーマップの使用例

このような豊富な追加メソッドは不必要に思えるかもしれませんが、多くの場合、最初に思ったよりもはるかに便利であることがわかります。この例を一緒に見てみましょう。私たちが大企業のマーケティング部門で働いており、広告を表示したい人々のデータベースがあると想像してください。これには 2 つのニュアンスがあります。

• 各ユーザーのインプレッション数を追跡する必要があります。
• 未成年者に広告を表示するアルゴリズムが異なります。

Person人物に関して利用可能なすべての情報を保存する クラスを作成しましょう。

public class Person {
   public String firstName;
   public String lastName;
   public int age;

   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
}

クラスにロジックを実装しますMain。

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Radion", "Pyatkin", 14), 0);
      map.put(new Person("Sergey", "Vashkevich", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map){}
   public static void showAdvertisementToAdult(Map map){}
}

Main作成する クラスではTreeMap、keyは特定の人物、 はvalue今月の広告インプレッション数です。コンストラクターでは、人々を年齢別に並べ替えるコンパレータを渡します。ランダムな値を入力しますmap。ここで、ミニ データ ストア内の最初の大人への参照を取得する必要があります。これは Stream API を使用して行います。この後、2 つの独立したマップを取得し、広告を表示するメソッドに渡します。この問題を解決できる方法はたくさんあります。このクラスのメソッドの武器を使用すると、TreeMapあらゆる好みに合わせたソリューションを発明できます。開発環境のドキュメントやヒントをいつでも使用できるため、すべてを覚える必要はありません。それだけです！TreeMapこのクラスの内容が理解でき、実際の問題を解決する際にこのクラスを正確に応用できるようになることを 願っています。