Introduktion til TreeMap-samlingen

En dag på universitetet skulle jeg skrive kode for at sortere mine klassekammeraters efternavne, som fungerede som nøgler til deres personlige data, i stigende rækkefølge. Jeg brugte meget tid på det her. Men hvis jeg havde kendt til TreeMap- klassen dengang, ville jeg have afsluttet opgaven meget hurtigere.

Hvad er et trækort ? Det er en ordbogslignende datastruktur, der gemmer elementer som et nøgle-værdi-par og sorterer dem efter nøgle.

Hvor og hvordan kan det bruges? Nå, det ville have været ideelt til den samme opgave med mine klassekammeraters efternavne. Hvis jeg har brug for at gemme værdier i stigende rækkefølge, i stedet for at skrive min egen sorteringsalgoritme, skal jeg kun lave et TreeMap og sætte værdierne i det.

Den sorterer typer såsom heltal og streng i stigende rækkefølge. Men hvis du vil indsætte din egen brugerdefinerede type i et TreeMap , så skal din klasse implementere Comparable- grænsefladen, så den implementerer compareTo()- metoden, som angiver, hvordan du sorterer forekomster af din klasse.

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

Lad os tilsidesætte compareTo()- metoden, så den sorterer værdierne efter fornavn i omvendt alfabetisk rækkefølge:

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ærdierne vil blive gemt i følgende rækkefølge:

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

TreeMap - klassen implementerer NavigableMap- grænsefladen, som igen udvider SortedMap- grænsefladen. Dette lader TreeMap- klassen bruge træer til at gemme værdier i sorteret rækkefølge.

For at sige det enkelt, er et rød-sort træ en datastruktur, der gemmer værdier i det højre undertræ, hvis de er større end roden, og i det venstre undertræ, hvis de er mindre. Denne implementering kan meget hurtigt slå værdier op i strukturen.

Et rød-sort træ er selvbalancerende, så det ændrer sin struktur, efterhånden som hver ny værdi indsættes. Den værdi, der tilføjes først, betragtes i første omgang som roden, men en anden værdi kan blive roden under afbalanceringsprocessen.

Nå, nu ved du, hvad TreeMap er, og hvordan det virker.

Husk, at TreeMap kun kan gemme objekter, hvis klasse implementerer Comparable- grænsefladen og tilsidesætter compareTo()- metoden.

Men hvad nu hvis vi bruger tredjepartsklasser indlæst fra forskellige biblioteker og ikke kan implementere Comparable i dem? Der er en løsning på dette: skriv din egen komparator .

Comparator er en grænseflade, der har en compare() metode. Vi kan bruge det til at sammenligne objekter og gemme dem i et 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 dette eksempel oprettede vi en brugerdefineret komparator og sendte et trækort til klassen.

Startende i Java 8 kan vi skrive dette ved hjælp af et lambda-udtryk:

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

Med andre ord, for at gemme værdier i et TreeMap , skal du angive, hvordan du sorterer dem. Der er to måder at gøre dette på: implementer Comparable eller implementer din egen Comparator .

Men hvad nu hvis vi skal sætte null i et TreeMap som en nøgle? HashMap lader dig gøre dette. Ja, men hvordan håndterer TreeMap dette?

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

At køre denne kode giver os en fejl:

Problemet er, at TreeMap- klassen internt sammenligner værdier ved hjælp af compareTo() -metoden. Du kan helt sikkert indtaste en null- værdi, og koden vil kompilere. Men ved kørsel får du en fejl, fordi metoden vil blive kaldt på en null- værdi, hvilket forårsager, at en NullPointerException bliver kastet.

Sammenligning af HashMap og TreeMap

I modsætning til TreeMap lader HashMap dig gemme null som en nøgle. Strukturen har et specifikt sted for alle null- nøgler. HashMap er i stand til at gemme null- nøgler, fordi det bestemmer, hvor de går, baseret på deres hashværdi, og beregning af hashværdien kræver ikke sammenligninger. Så alle nul- nøgler har deres plads.

Der har du det - nu ved du, hvad du skal bruge, når du skal gemme værdier i sorteret rækkefølge, og hvordan du sætter reglerne for sortering.