TreeMap コレクションの紹介

大学のある日、個人データのキーとなるクラスメートの姓を昇順に並べ替えるコードを記述する必要がありました。これには多くの時間を費やしました。しかし、当時TreeMapクラスについて知っていたら、もっと早くタスクを完了できたでしょう。

ツリーマップとは何ですか? これは、要素をキーと値のペアとして保存し、キーごとに並べ替える辞書のようなデータ構造です。

どこで、どのように使用できますか? まあ、クラスメートの姓で同じ課題を行うのが理想的でした。値を昇順で保存する必要がある場合、独自の並べ替えアルゴリズムを作成する代わりに、 TreeMapを作成してそこに値を入れるだけで済みます。

IntegerやStringなどの型を昇順に並べ替えます。ただし、独自のカスタム タイプをTreeMapに配置する場合は、クラスでComparableインターフェイスを実装する必要があります。これにより、クラスのインスタンスを並べ替える方法を示すCompareTo()メソッドが実装されます。

public class Person implements Comparable<Person> {

    private String firstName;
    private String lastName;

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

    public String getFirstName() {
        return firstName;
    }

    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }

  …

    @Override
    public int compareTo(Person person) {
        return person.getFirstName().compareTo(firstName);
    }

    @Override
    public String toString() {
        return "Person{" +
                "firstName='" + firstName + '\'' +
                ", lastName='" + lastName + '\'' +
                '}';
    }
}

値を名前の逆アルファベット順に並べ替えるように、compareTo()メソッドをオーバーライドしましょう。

TreeMap map = new TreeMap<Person, String>();

map.put(new Person("AA","BB"), "aa");
map.put(new Person("BB","BB"), "aa");
map.put(new Person("DD","BB"), "aa");
map.put(new Person("CC","BB"), "aa");

値は次の順序で保存されます。

Person{firstName='DD', lastName='BB'}
Person{firstName='CC', lastName='BB'}
Person{firstName='BB', lastName='BB'}
Person{firstName='AA', lastName='BB'}

TreeMapクラスはNavigableMapインターフェイスを実装し、これによりSortedMapインターフェイスが拡張されます。これにより、TreeMapクラスはツリーを使用して値を並べ替えられた順序で保存できるようになります。

簡単に言うと、赤黒ツリーは、値がルートより大きい場合は右側のサブツリーに、小さい場合は左側のサブツリーに値を格納するデータ構造です。この実装では、構造内の値を非常に迅速に検索できます。

赤黒ツリーは自己バランスをとるため、新しい値が挿入されるたびに構造が変化します。最初に追加された値が最初はルートとみなされますが、バランシング プロセス中に別の値がルートになる可能性があります。

さて、TreeMapとは何か、そしてそれがどのように機能するかがわかりました。

TreeMap は、クラスがComparableインターフェイスを実装し、 compareTo()メソッドをオーバーライドするオブジェクトのみを格納できることに注意してください。

しかし、さまざまなライブラリからロードされたサードパーティ クラスを使用していて、そのクラスにComparable を実装できない場合はどうなるでしょうか? これには解決策があります。独自のComparatorを作成します。

Comparatorは、compare() メソッドを持つインターフェイスです。これを使用してオブジェクトを比較し、 TreeMapに保存できます。

Comparator<Person> comparator = new Comparator<Person>() {

    @Override
    public int compare(Person person1, Person person2) {
        return person1.getFirstName().compareTo(person2.getFirstName());
    }
};


TreeMap map = new TreeMap<Person, String>(comparator);

この例では、カスタムComparatorを作成し、TreeMapをクラスに渡しました。

Java 8 以降では、ラムダ式を使用してこれを記述できます。

TreeMap map = new TreeMap<Person, String>((Person person1, Person person2) -> person1.getFirstName().compareTo(person2.getFirstName()));

つまり、TreeMapに値を格納するには、値を並べ替える方法を指定する必要があります。これを行うには 2 つの方法があります。Comparableを実装するか、独自のComparatorを実装します。

しかし、 TreeMapにnull をキーとして入れる必要がある場合はどうすればよいでしょうか? HashMap を使用するとこれが可能になります。はい、しかしTreeMap はこれをどのように処理しますか?

TreeMap map = new TreeMap<Person, String>();
map.put (null, "Person");

このコードを実行すると、次のエラーが発生します。

問題は、TreeMapクラスが内部的にCompareTo()メソッドを使用して値を比較することです。確かにnull値を渡すことができ、コードはコンパイルされます。ただし、実行時にメソッドがnull値で呼び出され、NullPointerExceptionがスローされるため、エラーが発生します。

ハッシュマップとツリーマップの比較

TreeMapとは異なり、HashMap ではnull をキーとして保存できます。この構造には、すべてのNullキーを格納する特定の場所があります。HashMap は、ハッシュ値に基づいてヌルキーの保存先を決定し、ハッシュ値の計算には比較が必要ないため、ヌル キーを保存できます。したがって、すべてのNullキーにはそれぞれの場所があります。

これで、値をソートされた順序で保存する必要がある場合に何を使用するか、およびソートのルールを設定する方法がわかりました。