Vi introduserer TreeMap-samlingen

En dag på universitetet trengte jeg å skrive kode for å sortere klassekameratenes etternavn, som fungerte som nøkler til deres personlige data, i stigende rekkefølge. Jeg brukte mye tid på dette. Men hvis jeg hadde visst om TreeMap- klassen da, ville jeg ha fullført oppgaven mye raskere.

Hva er et trekart ? Det er en ordboklignende datastruktur som lagrer elementer som nøkkel-verdi-par, og sorterer dem etter nøkkel.

Hvor og hvordan kan det brukes? Vel, det hadde vært ideelt for den samme oppgaven med klassekameratenes etternavn. Hvis jeg trenger å lagre verdier i stigende rekkefølge, i stedet for å skrive min egen sorteringsalgoritme, er alt jeg trenger å gjøre å lage et TreeMap og legge verdiene i det.

Den sorterer typer som heltall og streng i stigende rekkefølge. Men hvis du vil sette inn din egen tilpassede type i et TreeMap , må klassen din implementere Comparable- grensesnittet, slik at den implementerer compareTo()- metoden, som indikerer hvordan du sorterer forekomster av klassen din.

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

La oss overstyre compareTo()- metoden slik at den sorterer verdiene etter fornavn i omvendt alfabetisk rekkefø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");

Verdiene vil bli lagret i følgende rekkefø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- grensesnittet, som igjen utvider SortedMap- grensesnittet. Dette lar TreeMap- klassen bruke trær til å lagre verdier i sortert rekkefølge.

For å si det enkelt, er et rød-svart tre en datastruktur som lagrer verdier i høyre undertre hvis de er større enn roten, og i venstre undertre hvis de er mindre. Denne implementeringen kan slå opp verdier i strukturen veldig raskt.

Et rød-svart tre er selvbalanserende, så det endrer struktur etter hvert som hver ny verdi settes inn. Verdien som tilføres først regnes i utgangspunktet som roten, men en annen verdi kan bli roten under balanseprosessen.

Vel, nå vet du hva TreeMap er og hvordan det fungerer.

Husk at TreeMap bare kan lagre objekter hvis klasse implementerer Comparable- grensesnittet og overstyrer compareTo()- metoden.

Men hva om vi bruker tredjepartsklasser lastet fra forskjellige biblioteker og ikke kan implementere Comparable i dem? Det finnes en løsning for dette: skriv din egen komparator .

Comparator er et grensesnitt som har en compare() metode. Vi kan bruke den til å sammenligne objekter og lagre 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 eksemplet opprettet vi en tilpasset komparator og ga et TreeMap til klassen.

Fra Java 8 kan vi skrive dette ved å bruke et lambda-uttrykk:

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

Med andre ord, for å lagre verdier i et TreeMap , må du spesifisere hvordan du sorterer dem. Det er to måter å gjøre dette på: implementer Comparable eller implementer din egen Comparator .

Men hva om vi trenger å sette null i et TreeMap som en nøkkel? HashMap lar deg gjøre dette. Ja, men hvordan håndterer TreeMap dette?

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

Å kjøre denne koden gir oss en feil:

Problemet er at internt sammenligner TreeMap- klassen verdier ved å bruke compareTo() -metoden. Du kan sikkert sende inn en nullverdi og koden vil kompilere. Men ved kjøretid vil du få en feil, fordi metoden vil bli kalt på en nullverdi , noe som forårsaker at en NullPointerException blir kastet.

Sammenligning av HashMap og TreeMap

I motsetning til TreeMap , lar HashMap deg lagre null som en nøkkel. Strukturen har et spesifikt sted for alle nullnøkler . HashMap er i stand til å lagre null- nøkler fordi det bestemmer hvor de går basert på deres hash-verdi, og å beregne hash-verdien krever ikke sammenligninger. Så alle nullnøkler har sin plass.

Der har du det — nå vet du hva du skal bruke når du skal lagre verdier i sortert rekkefølge, og hvordan du setter reglene for sortering.