Prezentarea colecției TreeMap

Într-o zi, la universitate, a trebuit să scriu cod pentru a sorta numele de familie ale colegilor mei, care serveau drept chei pentru datele lor personale, în ordine crescătoare. Am petrecut mult timp pe asta. Dar dacă aș fi știut despre clasa TreeMap pe atunci, aș fi terminat sarcina mult mai repede.

Ce este un TreeMap ? Este o structură de date asemănătoare dicționarului care stochează elementele ca perechi cheie-valoare, sortându-le după cheie.

Unde și cum poate fi folosit? Ei bine, ar fi fost ideal pentru aceeași temă cu numele de familie ale colegilor mei. Dacă trebuie să stochez valori în ordine crescătoare, în loc să scriu propriul algoritm de sortare, tot ce trebuie să fac este să creez un TreeMap și să pun valorile în el.

Sortează tipuri precum Integer și String în ordine crescătoare. Dar dacă doriți să puneți propriul tip personalizat într-un TreeMap , atunci clasa dvs. trebuie să implementeze interfața Comparable , astfel încât să implementeze metoda compareTo() , care indică cum să sortați instanțe ale clasei dvs.

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

Să suprascriem metoda compareTo() astfel încât să sorteze valorile după prenume în ordine alfabetică inversă:

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

Valorile vor fi stocate în următoarea ordine:

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

Clasa TreeMap implementează interfața NavigableMap , care la rândul său extinde interfața SortedMap . Aceasta permite clasei TreeMap să folosească arbori pentru a stoca valorile în ordine sortată.

Pentru a pune asta în termeni simpli, un arbore roșu-negru este o structură de date care stochează valori în subarborele din dreapta dacă sunt mai mari decât rădăcina și în subarborele din stânga dacă sunt mai mici. Această implementare poate căuta valori în structură foarte rapid.

Un arbore roșu-negru se auto-echilibrează, așa că își schimbă structura pe măsură ce fiecare valoare nouă este inserată. Prima valoare adăugată este considerată inițial rădăcină, dar o altă valoare poate deveni rădăcină în timpul procesului de echilibrare.

Ei bine, acum știi ce este TreeMap și cum funcționează.

Amintiți-vă că TreeMap poate stoca doar obiecte a căror clasă implementează interfața Comparable și suprascrie metoda compareTo() .

Dar ce se întâmplă dacă folosim clase terțe încărcate din diferite biblioteci și nu putem implementa Comparable în ele? Există o soluție pentru aceasta: scrieți propriul Comparator .

Comparatorul este o interfață care are o metodă compare(). Îl putem folosi pentru a compara obiecte și pentru a le stoca într-un 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);

În acest exemplu, am creat un comparator personalizat și am transmis un TreeMap clasei.

Începând cu Java 8, putem scrie asta folosind o expresie lambda:

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

Cu alte cuvinte, pentru a stoca valori într-un TreeMap , trebuie să specificați cum să le sortați. Există două moduri de a face acest lucru: implementați Comparabil sau implementați propriul dvs. Comparator .

Dar dacă trebuie să punem null într-un TreeMap ca cheie? HashMap vă permite să faceți acest lucru. Da, dar cum gestionează TreeMap asta?

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

Rularea acestui cod ne dă o eroare:

Problema este că în interior clasa TreeMap compară valori folosind metoda compareTo() . Cu siguranță puteți trece o valoare nulă și codul se va compila. Dar în timpul execuției veți primi o eroare, deoarece metoda va fi apelată pe o valoare nulă , determinând o excepție NullPointerException .

Comparație între HashMap și TreeMap

Spre deosebire de TreeMap , HashMap vă permite să stocați null ca cheie. Structura are un loc specific pentru toate cheile nule . HashMap este capabil să stocheze cheile nule , deoarece determină unde se duc pe baza valorii lor hash, iar calcularea valorii hash nu necesită comparații. Deci toate cheile nule au locul lor.

Iată-l - acum știți ce să utilizați atunci când trebuie să stocați valorile în ordine sortată și cum să setați regulile de sortare.