この記事を読んでいるということは、Map インターフェイスと、どこに適切に適用できるかについてよくご存じであると思われます。そうでない場合は、ここに来てください。今日は、Java TreeMap の実装の特徴、具体的には HashMap との違いとその正しい使用方法について説明します。
ご覧のとおり、これらのクラスには多くの共通点がありますが、いくつかの違いもあります。TreeMap クラスは最も多用途ですが、常にnull をキーとして保存できるわけではありません。さらに、TreeMap の要素へのアクセスには最も長い時間がかかります。したがって、データをソートされた順序で保存する必要がない場合は、HashMapまたはLinkedHashMapを使用することをお勧めします。
それは今のところすべてです!TreeMap クラスについて理解でき、実際のコーディング タスクを解決する際にそれを適切に適用できることを願っています。
TreeMap、HashMap、LinkedHashMap の比較
Map インターフェイスの最もよく使用される実装は HashMap です。使いやすく、データへの迅速なアクセスが保証されているため、ほとんどの問題を解決するための最良の候補です。ほとんどですが、すべてではありません。場合によっては、データを構造化された方法で保存し、データ内を移動できるようにする必要があります。この場合、Map インターフェイスの別の実装 (TreeMap) が役に立ちます。TreeMap はNavigableMapインターフェイスを実装しており、これはSortedMapを継承し、さらに SortedMap は Map インターフェイスを継承します。 NavigableMapインターフェイスとSortedMapインターフェイスを実装することにより、TreeMap は HashMap では利用できない追加機能を受け取りますが、パフォーマンスの面で代償を支払います。LinkedHashMapもありますclass を使用すると、データを特定の順序 (マップに追加する順序) で保存することもできます。これら 3 つのクラスの違いを理解するには、次の表を参照してください。ハッシュマップ | リンクされたハッシュマップ | ツリーマップ | |
---|---|---|---|
データの順序付け | ランダム。順序が長期間にわたって維持されるという保証はありません。 | データ追加順 | 昇順または指定されたコンパレータに基づいて |
時間計算量 | ○(1) | ○(1) | O(log(n)) |
実装されたインターフェース | 地図 | 地図 | NavigableMap SortedMap マップ |
データ構造 | バケツ | バケツ | 赤黒の木 |
Nullキーのサポート? | はい | はい | はい、コンパレータを使用する場合、null が許可されます |
スレッドは安全ですか? | いいえ | いいえ | いいえ |
赤黒の木
おそらく、TreeMap が内部で赤黒ツリーと呼ばれるデータ構造を使用していることに気づいたでしょう。この構造にデータを格納することにより、まさにデータの順序付けが行われます。それで、これは何の木ですか?考えてみましょう! 数値と文字列のペアを保存する必要があると想像してください。16、20、52、55、61、65、71、76、81、85、90、93、101 の数字がキーになります。従来のリストにデータを保存し、キー 101 の要素を見つける必要がある場合は、13 要素すべてをステップ実行して見つける必要があります。13 個の要素の場合、これは大した問題ではありませんが、100 万個の要素を扱う場合は大きな問題が発生します。これらの問題を解決するために、プログラマはもう少し複雑なデータ構造を使用します。ここで赤黒樹の登場です!要素の検索はツリーのルート (この場合は 61) から始まります。次に、ノード値を探している値と比較します。値が小さい場合は左に進みます。それが大きい場合は、右に進みます。このプロセスは、目的の値が見つかるか、値がnullの要素(ツリーの葉)が見つかるまで繰り返されます。赤と黒の色は、ツリーの移動とバランスを簡単にするために使用されます。赤黒ツリーを構築する際には必ず遵守しなければならないルールがあります。- 根元は黒でなければなりません。
- 木の葉は黒くなければなりません。
- 赤いノードには 2 つの黒い子ノードが必要です。
- 黒のノードは、任意の色の子ノードを持つことができます。
- ノードからリーフまでのパスには、同じ数の黒いノードが含まれている必要があります。
- 新しいノードがリーフに追加されます。
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) : 開始要素からキー終了の要素まで、現在のマップのすべての要素を含むマップを返します。
- 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 は、新しいマップに境界要素を含めるかどうかを示します。
ツリーマップの例
この豊富な追加のメソッドは不必要に思えるかもしれませんが、一見したときよりもはるかに便利であることがわかります。次の例を一緒に見てみましょう。私たちが大企業のマーケティング部門で働いており、広告を表示したい人々のデータベースがあると想像してください。注意すべき点が 2 つあります。- 各ユーザーのインプレッション数を追跡する必要がある
- 未成年者に広告を表示するアルゴリズムが異なります。
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 コースのビデオ レッスンを視聴することをお勧めします。
GO TO FULL VERSION