Javaのツリーマップ

この記事を読んでいるということは、Map インターフェイスと、どこに適切に適用できるかについてよくご存じであると思われます。そうでない場合は、ここに来てください。今日は、Java TreeMap の実装の特徴、具体的には HashMap との違いとその正しい使用方法について説明します。

TreeMap、HashMap、LinkedHashMap の比較

Map インターフェイスの最もよく使用される実装は HashMap です。使いやすく、データへの迅速なアクセスが保証されているため、ほとんどの問題を解決するための最良の候補です。ほとんどですが、すべてではありません。場合によっては、データを構造化された方法で保存し、データ内を移動できるようにする必要があります。この場合、Map インターフェイスの別の実装 (TreeMap) が役に立ちます。TreeMap はNavigableMapインターフェイスを実装しており、これはSortedMapを継承し、さらに SortedMap は Map インターフェイスを継承します。 NavigableMapインターフェイスとSortedMap ツリーマップの特徴 - 2

インターフェイスを実装することにより、TreeMap は HashMap では利用できない追加機能を受け取りますが、パフォーマンスの面で代償を支払います。LinkedHashMapもありますclass を使用すると、データを特定の順序 (マップに追加する順序) で保存することもできます。これら 3 つのクラスの違いを理解するには、次の表を参照してください。

	ハッシュマップ	リンクされたハッシュマップ	ツリーマップ
データの順序付け	ランダム。順序が長期間にわたって維持されるという保証はありません。	データ追加順	昇順または指定されたコンパレータに基づいて
時間計算量	○(1)	○(1)	O(log(n))
実装されたインターフェース	地図	地図	NavigableMap SortedMap マップ
データ構造	バケツ	バケツ	赤黒の木
Nullキーのサポート?	はい	はい	はい、コンパレータを使用する場合、null が許可されます
スレッドは安全ですか?	いいえ	いいえ	いいえ

ご覧のとおり、これらのクラスには多くの共通点がありますが、いくつかの違いもあります。TreeMap クラスは最も多用途ですが、常にnull をキーとして保存できるわけではありません。さらに、TreeMap の要素へのアクセスには最も長い時間がかかります。したがって、データをソートされた順序で保存する必要がない場合は、HashMapまたはLinkedHashMapを使用することをお勧めします。

赤黒の木

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

要素の検索はツリーのルート (この場合は 61) から始まります。次に、ノード値を探している値と比較します。値が小さい場合は左に進みます。それが大きい場合は、右に進みます。このプロセスは、目的の値が見つかるか、値がnullの要素(ツリーの葉)が見つかるまで繰り返されます。赤と黒の色は、ツリーの移動とバランスを簡単にするために使用されます。赤黒ツリーを構築する際には必ず遵守しなければならないルールがあります。

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

ルール 3、4、および 5 を一緒に検討すると、ノードの色によってツリー内をより迅速に移動できることが理解できます。黒いノードを通るパスは、赤いノードを通るパスよりも常に短くなります。したがって、ツリーの全体のサイズは、「黒の高さ」と呼ばれる黒いノードの数によって決まります。赤黒ツリーのデータ構造は、さまざまなプログラミング言語で実装されています。インターネット上には Java の実装がたくさんあるので、ここでは長々と説明しません。代わりに、TreeMap の機能について学び続けましょう。

SortedMap および NavigableMap インターフェイスからのメソッド

HashMap と同様に、TreeMap は Map インターフェイスを実装します。これは、TreeMap が HashMap に存在するすべてのメソッドを備えていることを意味します。ただし、TreeMap はSortedMapインターフェイスとNavigableMapインターフェイスも実装しているため、それらから追加の機能が得られます。SortedMapはMapを拡張し、並べ替えられたデータセットに関連するメソッドを追加するインターフェイスです。

firstKey() : マップ内の最初の要素のキーを返します。
lastKey() : 最後の要素のキーを返します。
headMap(K end) : 現在のマップの先頭からキー end を持つ要素までのすべての要素を含むマップを返します。
tailMap(K start) : 現在のマップの開始要素から終了までのすべての要素を含むマップを返します。
subMap(K start, K 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 を返します
lowerKey(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) のみを返します。
lowerEntry(K obj) : lowerKey(K obj) メソッドと同様、キーと値のペア (または null) のみを返します。
decendingKeySet() : 逆順にソートされたすべてのキーを含む NavigableSet を返します。
decendingMap() : 逆順にソートされたすべてのペアを含む 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 にはコンパレーターのインスタンスを受け入れる別のコンストラクターがあります。このコンパレータは、要素が格納される順序を決定します。

ツリーマップの例

この豊富な追加のメソッドは不必要に思えるかもしれませんが、一見したときよりもはるかに便利であることがわかります。次の例を一緒に見てみましょう。私たちが大企業のマーケティング部門で働いており、広告を表示したい人々のデータベースがあると想像してください。注意すべき点が 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("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 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 を作成します。人々を年齢ごとに分類するコンパレーターをコンストラクターに渡します。マップに任意の値を入力します。ここで、小さなデータリポジトリ内の最初の成人への参照を取得したいと考えています。これは Stream API を使用して行います。次に、2 つの別々のマップを取得し、広告を表示するメソッドに渡します。このタスクを達成できる方法はたくさんあります。TreeMap クラスのメソッドの武器を使用すると、あらゆるニーズに対応するカスタムソリューションを作成できます。IDE からいつでもドキュメントやヒントを使用できるため、すべてを覚える必要はありません。学んだことをさらに強化するには、Java コースのビデオレッスンを視聴することをお勧めします。

それは今のところすべてです！TreeMap クラスについて理解でき、実際のコーディングタスクを解決する際にそれを適切に適用できることを願っています。