Dizionari

I dizionari sono una struttura di dati sofisticata che consente di accedere ad un elemento a partire dalla sua chiave. sono noti anche come tabelle di hash o mappe. La funzionalità principale di un dizionario è la ricerca veloce basata su chiavi. E' possibile anche aggiungere e rimuovere elementi, un può come List<t>, ma senza pagare il costo aggiuntivo di prestazioni legato allo scorrimento in memoria degli elementi successivi. Il Framework.NET offre la classe Dictionary<TKey, TValue>.

 

Tipo chiave

Un tipo utilizzato come chiave in un dizionario deve ridefinire il metodo GetHashCode() della classe Object. Ogni qual volta la classe dizionario ha la necessità di individuare un elemento, invoca il metodo GetHashCode(). Il valore int che viene ritornato da GetHashCode()è utilizzato dal dizionario per calcolare l'indice di posizione dell'elemento. Non entreremo in merito di questo argomento. Quello che il lettore dovrebbe sapere è che utilizza i numeri primi, quindi la capacità del dizionario è sempre un numero primo. L'implementazione del metodo GetHashCode() deve soddisfare i seguenti requisiti:

 

_ Lo stesso oggetto deve ritornare sempre lo stesso valore.

 

_ Oggetti diversi possono ritornare lo stesso valore.

 

_ Dovrebbe essere eseguito il più velocemente possibile; deve essere non costoso in termini computazionali.

 

_ Non deve sollevare eccezioni.

 

_ Deve impiegare almeno un campo dell'oggetto.

 

_ Il codice hash dovrebbe essere distribuito equamente attraverso l'intero intervallo di numeri memorizzabili da un int.

 

_ Sarebbe buona cosa che il codice hash non cambi durante il ciclo di vita dell'oggetto.

 

Le prestazioni del dizionario sono direttamente correlate alla qualità di implementazione del metodo GetHashCode().

 

Qual'è la ragione di volere i codici hash distribuiti equamente nell'intervallo dei numeri interi? Se due chiavi ritornano hash che puntano allo stesso indice, la classe dizionario deve iniziare a individuare la posizione libera più vicina per memorizzare il secondo elemento. In fase di recupero, dovrà inoltre eseguire una qualunque forma di ricerca. Questi aspetti incidono indubbiamente sulle prestazioni; se diverse chiavi tendono a fornire gli stessi indici di posizionamentoquesto tipo di situazione diventa maggiormente probabile. Il rischio è però minimizzato, grazie all'implementazione di Microsoft di questo algoritmo. Se i valori degli hash sono distribuiti uniformemente tra int.MinValue e int.MaxValue.

Oltre a disporre di un' implementazione di GetHashCode(), il tipo chiave deve anche implementare il metodo IEquality.Equals() o ridefinire il metodo Equals() della classe Object. Dato che chiavi diverse potrebbero riportare lo stesso codice hash, viene utilizzato il metodo Equals() per confrontare le chiavi. Il dizionario determina se le chiavi A e B sono uguali, eseguendo la chiamata a A.Equals(B). Quasto significa che se A.Equals(B) è true, allora A.GetHashCode() e B.GetHashCode() devono ritornare lo stesso codice hash. Questa potrebbe apparire come una quisquilia, invece è cruciale. Se si ha progettato di ridefinire questi metodi in modo che l'affermazione precedente venga valutata sempre vero, un dizionario che utilizzi istanze di questa classe come chiave semplicemente non funzionerebbe correttamente. Si vedranno infatti succedere cose strane. Per esempio si potrebbe inserire un oggetto nel dizionario , per poi scoprire di non essere in grado di recuperarlo, oppure al tentativo di recupero venga restituito un oggetto errato.

 

Per questa ragione il compilatore C# visualizza un avviso di compilazione se in una classe si implementa il metodo Equals() ma non il metodo GetHashCode().

 

La classe System.Object funziona correttamente: Equals() non ha fatto altro che confrontare i riferimenti che GetHashCode() ritornaun codice hash basato solamente sull'indirizzo dell'oggetto. Questo significa che quando si inserisce un oggetto nel dizionario si rimane vincolati ad utilizzare lo stesso oggetto chiave. Non è possibile semplicemente istanziare un altro oggetto chiave con lo stesso valore. Se infatti non si ridefinisce Sequals() e GetHashCode(), il tipo non è molto comodo per l'impiego con i dizionari. Incidentalmente, System.String implementa l'interfaccia IEquatable e ridefinisce GetHashCode() in modo appropriato. Equals() fornisce confronti di valore e GetHashCode() ritorna un hash basato sul valore del testo contenuto. Le stringe sono quindi adatte per essere utilizzate come chiavi nei dizionari.

Numeri come Int32 implementano inoltre all'interfaccia IEquatable e ridefiniscono GetHashCode(). Però, il codice hash ritornato da questi tipi non fa altro che mappare al valore. Se è necessario utilizzare un tipo chiave che non implementa IEquitable e ridefinisce GetHashCode() in accordo ai valori delle chiavi da memorizzare nel dizionario, è possibile creare un oggetto di confronto implementando l' interfaccia IEqualityComparer<T>. Questa definisce i metodi GetHashCode() e Equals() ch presentano un parametro in più, che l'oggetto da confrontare. In questo modo è possibile offrire un'implementazione differente rispetto a quella della classe dell'oggetto stesso. Il costruttore Disarcionar<Hockey, TValue> consente di passare un oggetto che implementa IEqualityComparer<T>. Nel caso si passi un oggetto di questo tipo al dizionario, verrà utilizzato questo per generare i codici hash e per confrontare le chiavi.

 

Esempio di dizionario

Questo programma di esempio crea un dizionario di impiegati. E' indicizzato tramite oggetti Employeeid e ciascun elemento è un oggetto Employee, che contiene i dettagli dell'impiegato.

La struttura Employeeid è implementata in modo da definire la chiave da utilizzare nel dizionario. I membri della classe sono un carattere di prefisso di prefisso e il numero dell'impiegato. Entrambe queste variabili sono in sola lettura e possono essere inizializzate solo nel costruttore, una chiave chiave all'interno del dizionario non dovrebbe cambiare, e in questo modo la si può garantire. I campi sono compilati nel costruttore . Il metodo ToString() è ridefinito per ottenere una rappresentazione testuale dell'ID dell'impiegato.

Come richiesto per i tipi chiave, EmployeeID implementa l'interfaccia IEquatable e ridefinisce il metodo GetHashCode()

 

[Serializable]

public struct Employeeid

{

private readonly char prefisso;

private readonly int numero;

 

public Employeeid(String id)

{

if (id == null)

throw new ArgumentException("id");

prefisso = id.ToUpper()[0];

int termine = id.Length - 1;

if (!int.TryParse(id.Substring(

1, termine > 6 ? 6 : termine), out numero))

numero = 0;

}

public override string ToString()

{

return string.Format("{0}{1,6:000000}",prefisso, numero);

}

public override int GetHashCode()

{

return (numero ^ numero << 16) * 0x15051505;

}

public bool Equals(Employeeid altro)

{

return (prefisso == altro.prefisso && numero == altro.numero);

}

}

 

Il metodo Equals() definito dall'interfaccia IEquatable<T> confronta i valoridi due oggetti EmployeeID e ritorna true se i valori sono uguali. Invece di implementare il metodo Equals() dell'interfaccia IEquatable<T> è anche possibile ridefinire il metodo Equals() della classe Object:

 

public bool Equals(Employeeid altro)

{

if(altro==null) return false;

return (prefisso == altro.prefisso &&

numero == altro.numero);

}

 

La variabile numerica memorizza il numero di impiegati, il cui valore può oscillare tra 1 e 190'000. Questo valore non riempie l'intervallo degili interi. L'algoritmo utilizzato dal metodo GetHashCode() scorre il numero di 16 bit a sinistra e quindi esegue uno XOR con il numero originale. Alla fine moltiplica il risultato per il valore esadecimale 15051505. In questo modo il valore viene meglio "spalmato" nell'intervallo degli interi.

 

public override int GetHashCode()

{

return (numero ^ numero << 16) * 0x15051505;

}

 

Su internet e possibile trivare numerosi algoritmi, più cmplessi, che consentono di ottenere una maggior distribuzione del valore nell'intervallo degi interi. Per ottenere un valore hash è anche possibile utilizzare il metodo GetHashCode() della stringa.

 

La classe Employee è una semplice entità che contiene il nome, il salario e l' ID dell'impiegato. Il costruttore inizializza tutti i valori e il metodo ToString() ritorna una rappresentazione testuale dell'oggetto. L'implementazione di questo metodoutilizza una stringa formattata per questioni di prestazioni.

 

[Serializable]

class Employee

{

private string nome;

private decimal salario;

private readonly Employeeid id;

 

public Employee(Employeeid id, string name,

decimal salary)

{

this.id = id;

nome = name;

salario = salary;

}

 

public override string ToString()

{

return String.Format("{0}: {1, -10} {2:C}",id.ToString(), nome, salario);

}

}

 

Nel metodo Main() dell' applicazione di esempio viene creato un nuovo oggetto di tipo Dictionary<TKey, TValue> dove la chiave è di tipo Employeid e il valore di tipo Employee. Il costruttore alloca una capacità di 31 elementi. Si ricordi, questo elementoè basato sui numeri primi. Però se si assenga un valore che non è un numeo primo, non è un problema. La classe Dictionary<TKey, TValue> si occupa automaticamente di ottenere il prossimo numero primo rispetto al' intero passato come parametro al costruttore.

Gli oggetti impiegato e relativi ID vengono creati e aggiunti al dizionario attraverso il metodo ADD(). Invece di utilizzare questo metodo è possibile utilizzare le parentesi quadre per lo stesso scopo, come mostrato per gli impiegati Carlo e Matteo:

 

static void Main(string[] args)

{

Dictionary<Employeeid, Employee> dipendente;

dipendente = new Dictionary<Employeeid, Employee>(31);

 

Employeeid idGiuseppe = new Employeeid("C7102");

Employee giuseppe = new Employee(idGiuseppe,

"Giuseppe", 5164580.00m);

dipendente.Add(idGiuseppe, giuseppe);

Console.WriteLine(giuseppe);

 

Employeeid idTony = new Employeeid("c7105");

Employee Tony = new Employee(idTony,

"Tony", 4814200m);

dipendente.Add(idTony, Tony);

Console.WriteLine(Tony);

 

Employeeid idDaniela = new Employeeid("C8011");

Employee Daniela = new Employee(idDaniela ,

"Daniela", 3718710.00m);

dipendente.Add(idDaniela, Daniela);

Console.WriteLine(Daniela);

 

Employeeid idCarlo = new Employeeid("F7908");

Employee Carlo = new Employee(idCarlo,

"Carlo",3285710.00m);

dipendente[idCarlo] = Carlo;

Console.WriteLine(Carlo);

 

Employeeid idMatteo = new Employeeid("F7203");

Employee Matteo = new Employee(idMatteo,

"Matteo", 450330.00m);

dipendente[idMatteo] = Matteo;

Console.WriteLine(Matteo);

 

Dopo che gli elementi sono stati aggiunti al dizionario, questi vengono letti attraverso un ciclo while. Viene chiesto all'utente di introdurre un numero di impiegato, che viene memorizzato nella variabile userInput. L'utente può terminare l' applicazione digitando X. Se la chiave è nel dizionario viene esaminata tramite il metodo TryGetValue() della classe Dictionary<TKey, TValue>. Questo ritorna true se la chiave viene trovata, false altrimenti. Se il valore non viene trovato, il dato associatoalla chiave viene memorizzatonella variavile impiegato, e quindi scritta su terminale.

 

while (true)

{

Console.Write("Introduci l'id dell'impiegato

(X per terminare) > ");

userInput = Console.ReadLine();

if (userInput.ToUpper() == "X") break;

 

Employeeid id = new Employeeid(userInput);

Employee ricercato;

if (!dipendente.TryGetValue(id, out ricercato))

{

Console.WriteLine("Il dipendente con id {0}

non esiste", id.ToString());

}

else

{

Console.WriteLine(ricercato.ToString());

}

}

 

Per accedere a un valore memorizzato nel dizionarioè anche possibile utilizzare le parentesi quadrate implementate da Dictionary<TKey, TValue> invece del metodo TryGetValue().Però, se la chiave non viene trovata l'indicizzazione con parentesi solleva un'eccezzione di tipo KeyNotFoundException.

 

Ricerca

La classe Dictionary<TKey, TValue> supporta solo un valore per ogni singola chiave La nuova classe Lookup<YKey, TElement>, assomiglia a Dictionary<TKey, TValue>, con la differenza che mappa le chiavi su collezioni di valori. Questa classe è implementata nell'assembly System.Core e definita nel namespace System.Linq. Le proprietà e i metodi di Lookup<YKey, TElement> sono descritti nella tabella seguente.

 

Proprietà e metodi di Lookup<TKey, TElement>	Descrizione
Count	La proprietà Count ritorna il numero di elementi nella collezione
Item	Attraverso le parentesi quadre è possibile accedere ai singoli elementi tramite la chiave. Dato che possono esistere valori multipli con la stessa chiave, questa proprietà ritorna una enumerazione
Contains()	Il mrtodo Contains() ritorna un risultato Boolean che indicase sono presenti elementi per la chiave indicata.
ApplyResultSelector()	ApplyResultSelector() ritorna una collezione trasformando ciascun elementotramite una funzione passata come parametro al metodo

 

 

Lookup<YKey, TElement> non può essere certo come un normale dizionario. E' necessario invece invocare il metodo ToLookup() disponibile in tutte le classi che implementano IEnumerable<T>.