A TreeMap gyűjtemény bemutatása

Egyik nap az egyetemen kódot kellett írnom, hogy osztálytársaim vezetéknevét, amely a személyes adataik kulcsaként szolgált, növekvő sorrendbe rendezzem. Sok időt töltöttem ezzel. De ha akkoriban tudtam volna a TreeMap osztályról, sokkal gyorsabban végeztem volna a feladattal.

Mi az a TreeMap ? Ez egy szótárszerű adatstruktúra, amely kulcs-érték párokként tárolja az elemeket, kulcsok szerint rendezve azokat.

Hol és hogyan használható? Nos, ez ideális lett volna ugyanarra a feladatra az osztálytársaim vezetéknevével. Ha növekvő sorrendben kell tárolnom az értékeket, ahelyett, hogy saját rendezési algoritmust írnék, csak létrehoznom kell egy TreeMap-et , és bele kell raknom az értékeket.

Növekvő sorrendbe rendezi az olyan típusokat, mint az Integer és a String . De ha saját egyéni típusát szeretné elhelyezni egy TreeMap- ben , akkor az osztálynak meg kell valósítania az Összehasonlítható felületet, hogy megvalósítsa az összehasonlító() metódust, amely jelzi, hogyan kell rendezni az osztály példányait.

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 + '\'' +
                '}';
    }
}

Írjuk felül az összehasonlító() metódust, hogy az utónév szerint, fordított ábécé sorrendbe rendezze az értékeket:

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");

Az értékek tárolása a következő sorrendben történik:

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

A TreeMap osztály a NavigableMap felületet valósítja meg, ami viszont kiterjeszti a SortedMap felületet. Ez lehetővé teszi a TreeMap osztály számára, hogy fákat használjon az értékek rendezett sorrendben történő tárolására.

Egyszerűen fogalmazva, a piros-fekete fa olyan adatstruktúra, amely a jobb oldali részfában tárolja az értékeket, ha azok nagyobbak, mint a gyökér, és a bal részfában, ha kisebbek. Ez a megvalósítás nagyon gyorsan képes értékeket keresni a struktúrában.

A piros-fekete fa önkiegyensúlyozó, ezért minden új érték beszúrásakor megváltoztatja a szerkezetét. Kezdetben a hozzáadott érték számít gyökérnek, de a kiegyenlítési folyamat során egy másik érték is gyökérré válhat.

Nos, most már tudja, mi az a TreeMap , és hogyan működik.

Ne feledje, hogy a TreeMap csak olyan objektumokat tud tárolni, amelyek osztálya megvalósítja a Comparable interfészt, és felülírja az összehasonlító() metódust.

De mi van akkor, ha harmadik féltől származó osztályokat használunk, amelyeket különböző könyvtárakból töltenek be, és nem tudjuk megvalósítani bennük a Comparable-t ? Erre van megoldás: írd meg a saját Comparator- odat .

A Comparator egy olyan interfész, amely összehasonlítás() metódussal rendelkezik. Használhatjuk objektumok összehasonlítására és TreeMap- ben való tárolására .

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);

Ebben a példában létrehoztunk egy egyéni összehasonlítót , és egy TreeMap-et adtunk át az osztálynak.

A Java 8-tól kezdve ezt egy lambda kifejezéssel írhatjuk:

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

Más szóval, ahhoz, hogy értékeket TreeMap-ben tároljon , meg kell adnia, hogyan rendezze őket. Ennek két módja van: implementálja a Comparable-t , vagy implementálja a saját Comparator- ját .

De mi van akkor, ha nullát kell beírnunk egy TreeMapbe kulcsként? A HashMap segítségével ezt megteheti. Igen, de hogyan kezeli ezt a TreeMap ?

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

A kód futtatása hibát ad:

A probléma az, hogy belül a TreeMap osztály az összehasonlító() metódussal hasonlítja össze az értékeket. Biztosan megadhat null értéket, és a kód lefordítja. Futás közben azonban hibaüzenet jelenik meg, mivel a metódus null értékkel lesz meghívva, ami egy NullPointerException kivételt eredményez.

A HashMap és a TreeMap összehasonlítása

A TreeMap-től eltérően a HashMap lehetővé teszi a null kulcsként való tárolását . A szerkezetben van egy meghatározott hely az összes null kulcs számára. A HashMap képes null kulcsokat tárolni, mert a hash értéke alapján határozza meg, hogy hová menjenek, és a hash érték kiszámításához nincs szükség összehasonlításra. Tehát minden null kulcsnak megvan a maga helye.

Itt van – most már tudja, mit használjon, ha az értékeket rendezett sorrendben kell tárolnia, és hogyan állíthatja be a rendezési szabályokat.