Introductie van de TreeMap-collectie

Op een dag op de universiteit moest ik code schrijven om de achternamen van mijn klasgenoten, die dienden als sleutels tot hun persoonlijke gegevens, in oplopende volgorde te sorteren. Ik heb hier veel tijd aan besteed. Maar als ik destijds van de TreeMap- klasse had geweten , zou ik de taak veel sneller hebben voltooid.

Wat is een TreeMap ? Het is een woordenboekachtige gegevensstructuur die elementen opslaat als sleutel-waardeparen en ze op sleutel sorteert.

Waar en hoe kan het worden gebruikt? Het zou ideaal zijn geweest voor dezelfde opdracht met de achternamen van mijn klasgenoten. Als ik waarden in oplopende volgorde moet opslaan, in plaats van mijn eigen sorteeralgoritme te schrijven, hoef ik alleen maar een TreeMap te maken en de waarden erin te zetten.

Het sorteert typen zoals Integer en String in oplopende volgorde. Maar als u uw eigen aangepaste type in een TreeMap wilt plaatsen , moet uw klasse de Comparable- interface implementeren , zodat deze de methode CompareTo() implementeert , die aangeeft hoe instanties van uw klasse moeten worden gesorteerd.

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

Laten we de methode CompareTo() overschrijven , zodat deze de waarden sorteert op voornaam in omgekeerde alfabetische volgorde:

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

De waarden worden in de volgende volgorde opgeslagen:

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

De TreeMap- klasse implementeert de NavigableMap- interface, die op zijn beurt de SortedMap- interface uitbreidt. Hierdoor kan de klasse TreeMap bomen gebruiken om waarden in gesorteerde volgorde op te slaan.

Simpel gezegd: een rood-zwarte boom is een datastructuur die waarden opslaat in de rechter subboom als ze groter zijn dan de wortel, en in de linker subboom als ze kleiner zijn. Deze implementatie kan heel snel waarden opzoeken in de structuur.

Een rood-zwarte boom is zelfbalancerend, dus verandert hij van structuur bij elke nieuwe waarde die wordt ingevoegd. De eerst toegevoegde waarde wordt in eerste instantie beschouwd als de wortel, maar een andere waarde kan de wortel worden tijdens het balanceringsproces.

Nou, nu weet je wat TreeMap is en hoe het werkt.

Onthoud dat TreeMap alleen objecten kan opslaan waarvan de klasse de Comparable- interface implementeert en de methode CompareTo() overschrijft .

Maar wat als we klassen van derden gebruiken die uit verschillende bibliotheken zijn geladen en Comparable daarin niet kunnen implementeren? Daar is een oplossing voor: schrijf je eigen Comparator .

Comparator is een interface die een vergelijk() methode heeft. We kunnen het gebruiken om objecten te vergelijken en op te slaan in een 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);

In dit voorbeeld hebben we een aangepaste Comparator gemaakt en een TreeMap doorgegeven aan de klas.

Vanaf Java 8 kunnen we dit schrijven met een lambda-expressie:

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

Met andere woorden, om waarden in een TreeMap op te slaan , moet u specificeren hoe u ze wilt sorteren. Er zijn twee manieren om dit te doen: Comparable implementeren of uw eigen Comparator implementeren .

Maar wat als we null als sleutel in een TreeMap moeten plaatsen ? Met HashMap kunt u dit doen. Ja, maar hoe gaat TreeMap hiermee om?

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

Het uitvoeren van deze code geeft ons een foutmelding:

Het probleem is dat de klasse TreeMap intern waarden vergelijkt met behulp van de methode CompareTo() . U kunt zeker een null- waarde invoeren en de code wordt gecompileerd. Maar tijdens runtime krijg je een foutmelding, omdat de methode wordt aangeroepen op een null- waarde, waardoor een NullPointerException wordt gegenereerd.

Vergelijking van HashMap en TreeMap

In tegenstelling tot TreeMap kunt u met HashMap null als sleutel opslaan. De structuur heeft een specifieke plaats voor alle null- sleutels. HashMap kan null- sleutels opslaan omdat het bepaalt waar ze naartoe gaan op basis van hun hash-waarde, en het berekenen van de hash-waarde vereist geen vergelijkingen. Dus alle null- sleutels hebben hun plaats.

Daar heb je het - nu weet je wat je moet gebruiken als je waarden in gesorteerde volgorde moet opslaan en hoe je de regels voor sorteren moet instellen.