Mappe ordinate: TreeMap

10 luglio 2017

Abbiamo visto nei capitolo precedenti che HashMap ed HashTable rappresentano la soluzione maggiormente adottata per rappresentare mappe in Java.

In situazioni in cui è richiesto un ordinamento sulle chiavi possiamo considerare la classe TreeMap. Si tratta di una classe la cui complessità di tempo per le varie è operazioni è logaritmica nella dimensione della mappa. L’ordinamento è quindi una funzione in più che otteniamo, rispetto ad HashMap ed HashTable, perdendo qualcosa in termini di performance.

Nel caso di una TreeMap è importante evidenziare che le classi utilizzate come chiavi devono produrre oggetti confrontabili. Possiamo rispettare questo requisito facendo in modo che la classe che rappresenta le chiavi implementi l’interfaccia Comparable, oppure utilizzando un costruttore di TreeMap che accetti come input un oggetto di una classe che implementi l’interfaccia Comparator.

Vediamo un esempio, realizziamo una TreeMap che memorizzi le coppie cognome-nome di una persona ordinandole alfabeticamente sul cognome. Creiamo una classe applicativa, TreeMapApp, che al suo interno contenga la classe per rappresentare una chiave della TreeMap:

public class TreeMapApp {

	static class LastName implements Comparable<LastName> {

		private String value;

		public LastName(String lastName){
		  this.value = lastName;	
		}
		
		@Override
		public int compareTo(LastName lastName) {
			char[] chars1 = this.value.toCharArray();
			char[] chars2 = lastName.value.toCharArray();

			int size1 = chars1.length;
			int size2 = chars2.length;

			int min = size1 > size2 ? size1 : size2;

			for (int i = 0; i < min; i++) {
				int value = Character.compare(chars1[i], chars2[i]);
				if (value < 0) {
					return -1;
				} else if (value > 0) {
					return 1;
				}
			}
			return 0;
		}
		@Override
		public String toString(){
			return value;
		}
	}

	public static void main(String[] args) {
        ....
	}
}

 

La classe LastName implementa l’interfaccia Comparable specificando se stessa come tipo di comparazione. Comparable richiede di implementare il metodo compareTo() che nel nostro caso conterrà la logica per determinare quale cognome viene prima di un altro nell’ordinamento alfabetico. Successivamente nel metodo main creaimo una TreeMap inserendo le entry senza alcun ordinamento:

         TreeMap<LastName,String> rubrica = new TreeMap<>();
         
         rubrica.put(new LastName("Rossi"), "Mario");
         rubrica.put(new LastName("Gialli"), "Laura");
         rubrica.put(new LastName("Marrone"), "Laura");
         rubrica.put(new LastName("Verdi"), "Monica");
         rubrica.put(new LastName("Bianchi"), "Luigi");
         rubrica.put(new LastName("Magenta"), "Osvaldo");
         rubrica.put(new LastName("Neri"), "Luca");

Ed infine testiamo il comportamento della TreeMap per verificare con una stampa che il tutto funzioni correttamente:

        rubrica.forEach((lastName,firstName)->
        System.out.println(lastName+"-"+firstName));

Il risultato sulla console di output dovrebbe essere il seguente:

Bianchi-Luigi
Gialli-Laura
Magenta-Osvaldo
Marrone-Laura
Neri-Luca
Rossi-Mario
Verdi-Monica

Tutte le lezioni

1 ... 62 63 64 ... 117

Se vuoi aggiornamenti su Mappe ordinate: TreeMap inserisci la tua e-mail nel box qui sotto:
Tags:
 
X
Se vuoi aggiornamenti su Mappe ordinate: TreeMap

inserisci la tua e-mail nel box qui sotto:

Ho letto e acconsento l'informativa sulla privacy

Acconsento al trattamento di cui al punto 3 dell'informativa sulla privacy