Un giorno all'università, avevo bisogno di scrivere un codice per ordinare in ordine crescente i cognomi dei miei compagni di classe, che fungevano da chiavi per i loro dati personali. Ho passato molto tempo su questo. Ma se allora avessi saputo della classe TreeMap , avrei terminato l'attività molto più velocemente.
Che cos'è una mappa ad albero ? È una struttura dati simile a un dizionario che memorizza gli elementi come coppie chiave-valore, ordinandoli per chiave.
Dove e come può essere utilizzato? Beh, sarebbe stato l'ideale per lo stesso compito con i cognomi dei miei compagni di classe. Se devo memorizzare i valori in ordine crescente, invece di scrivere il mio algoritmo di ordinamento, tutto ciò che devo fare è creare una TreeMap e inserirvi i valori.
Ordina tipi come Integer e String in ordine crescente. Ma se vuoi inserire il tuo tipo personalizzato in un TreeMap , allora la tua classe deve implementare l' interfaccia Comparable , in modo che implementi il metodo compareTo() , che indica come ordinare le istanze della tua classe.
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 + '\'' +
'}';
}
}
Sovrascriviamo il metodo compareTo() in modo che ordini i valori per nome in ordine alfabetico inverso:
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");
I valori verranno memorizzati nel seguente ordine:
Person{firstName='DD', lastName='BB'}
Person{firstName='CC', lastName='BB'}
Person{firstName='BB', lastName='BB'}
Person{firstName='AA', lastName='BB'}
La classe TreeMap implementa l' interfaccia NavigableMap , che a sua volta estende l' interfaccia SortedMap . Ciò consente alla classe TreeMap di utilizzare gli alberi per archiviare i valori in ordine ordinato.
Come dice Wikipedia, un albero è una struttura di ricerca binaria autobilanciata che memorizza i dati nei suoi nodi dopo aver prima confrontato i valori. |
Per dirla in termini semplici, un albero rosso-nero è una struttura dati che memorizza i valori nel sottoalbero di destra se sono maggiori della radice e nel sottoalbero di sinistra se sono minori. Questa implementazione può cercare i valori nella struttura molto rapidamente.
Un albero rosso-nero è autobilanciato, quindi cambia la sua struttura ogni volta che viene inserito un nuovo valore. Il valore aggiunto per primo è inizialmente considerato la radice, ma un altro valore può diventare la radice durante il processo di bilanciamento.

Bene, ora sai cos'è TreeMap e come funziona.
Ricorda che TreeMap può memorizzare solo oggetti la cui classe implementa l' interfaccia Comparable e sovrascrive il metodo compareTo() .
Ma cosa succede se utilizziamo classi di terze parti caricate da varie librerie e non possiamo implementare Comparable in esse? C'è una soluzione per questo: scrivi il tuo Comparator .
Comparator è un'interfaccia che ha un metodo compare(). Possiamo usarlo per confrontare oggetti e memorizzarli in una 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 questo esempio, abbiamo creato un Comparator personalizzato e passato una TreeMap alla classe.
A partire da Java 8, possiamo scriverlo usando un'espressione lambda:
TreeMap map = new TreeMap<Person, String>((Person person1, Person person2) -> person1.getFirstName().compareTo(person2.getFirstName()));
In altre parole, per memorizzare i valori in una TreeMap , è necessario specificare come ordinarli. Ci sono due modi per farlo: implementare Comparable o implementare il tuo Comparator .
Ma cosa succede se dobbiamo inserire null in una TreeMap come chiave? HashMap ti consente di farlo. Sì, ma come gestisce TreeMap questo?
TreeMap map = new TreeMap<Person, String>();
map.put (null, "Person");
L'esecuzione di questo codice ci dà un errore:
Il problema è che internamente la classe TreeMap confronta i valori utilizzando il metodo compareTo() . Puoi certamente passare un valore nullo e il codice verrà compilato. Ma in fase di esecuzione riceverai un errore, perché il metodo verrà chiamato su un valore nullo , causando la generazione di un'eccezione NullPointerException .
Confronto tra HashMap e TreeMap
A differenza di TreeMap , HashMap ti consente di memorizzare null come chiave. La struttura ha un posto specifico per tutte le chiavi nulle . HashMap è in grado di memorizzare chiavi nulle perché determina dove vanno in base al loro valore hash e il calcolo del valore hash non richiede confronti. Quindi tutte le chiavi nulle hanno il loro posto.
Ecco fatto: ora sai cosa usare quando devi archiviare i valori in ordine ordinato e come impostare le regole per l'ordinamento.
GO TO FULL VERSION