Introduzione alla collezione TreeMap

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.

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.