Vi presenterar TreeMap-samlingen

En dag på universitetet behövde jag skriva kod för att sortera mina klasskamraters efternamn, som fungerade som nycklar till deras personliga data, i stigande ordning. Jag tillbringade mycket tid på detta. Men om jag hade känt till TreeMap- klassen då, skulle jag ha slutfört uppgiften mycket snabbare.

Vad är en TreeMap ? Det är en ordboksliknande datastruktur som lagrar element som nyckel-värdepar och sorterar dem efter nyckel.

Var och hur kan den användas? Tja, det hade varit perfekt för samma uppgift med mina klasskamraters efternamn. Om jag behöver lagra värden i stigande ordning, istället för att skriva min egen sorteringsalgoritm, behöver jag bara skapa en TreeMap och lägga in värdena i den.

Den sorterar typer som heltal och sträng i stigande ordning. Men om du vill lägga in din egen anpassade typ i en TreeMap måste din klass implementera gränssnittet Comparable , så att den implementerar metoden compareTo() som anger hur instanser av din klass ska sorteras.

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

Låt oss åsidosätta compareTo() -metoden så att den sorterar värdena efter förnamn i omvänd alfabetisk ordning:

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

Värdena kommer att lagras i följande ordning:

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

TreeMap - klassen implementerar NavigableMap- gränssnittet, som i sin tur utökar SortedMap -gränssnittet. Detta låter TreeMap -klassen använda träd för att lagra värden i sorterad ordning.

För att uttrycka det enkelt, ett röd-svart träd är en datastruktur som lagrar värden i det högra underträdet om de är större än roten, och i det vänstra underträdet om de är mindre. Denna implementering kan slå upp värden i strukturen mycket snabbt.

Ett röd-svart träd är självbalanserande, så det ändrar sin struktur när varje nytt värde infogas. Förädlingsvärdet först anses initialt vara roten, men ett annat värde kan bli roten under balanseringsprocessen.

Nåväl, nu vet du vad TreeMap är och hur det fungerar.

Kom ihåg att TreeMap bara kan lagra objekt vars klass implementerar Comparable- gränssnittet och åsidosätter compareTo()- metoden.

Men vad händer om vi använder tredjepartsklasser laddade från olika bibliotek och inte kan implementera Comparable i dem? Det finns en lösning för detta: skriv din egen komparator .

Comparator är ett gränssnitt som har en compare()-metod. Vi kan använda den för att jämföra objekt och lagra dem i en 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);

I det här exemplet skapade vi en anpassad Comparator och skickade en TreeMap till klassen.

Med start i Java 8 kan vi skriva detta med ett lambda-uttryck:

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

Med andra ord, för att lagra värden i en TreeMap måste du ange hur du sorterar dem. Det finns två sätt att göra detta: implementera Comparable eller implementera din egen Comparator .

Men vad händer om vi behöver lägga in null i en TreeMap som en nyckel? HashMap låter dig göra detta. Ja, men hur hanterar TreeMap detta?

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

Att köra den här koden ger oss ett fel:

Problemet är att internt jämför TreeMap -klassen värden med metoden compareTo() . Du kan säkert skicka in ett nollvärde och koden kompileras. Men vid körning får du ett fel, eftersom metoden kommer att anropas på ett nullvärde , vilket gör att ett NullPointerException kastas.

Jämförelse av HashMap och TreeMap

Till skillnad från TreeMap låter HashMap dig lagra null som en nyckel . Strukturen har en specifik plats för alla null- nycklar. HashMap kan lagra null- nycklar eftersom det bestämmer vart de går baserat på deras hashvärde, och att beräkna hashvärdet kräver inte jämförelser. Så alla nollnycklar har sin plats.

Där har du det — nu vet du vad du ska använda när du behöver lagra värden i sorterad ordning, och hur du ställer in reglerna för sortering.