[C++] Cosa sono le hashtable e i dizionari?

[lazzaroli.victor]

Salve mi trovo davanti a una richiesta di creare un dizionario per delle classi che ho implementato.
Il problema è in particolare il seguente:
scrivo codice con un framework per l'analisi scientifica che permette anche la costruzione di GUI per la gestione dei segnali tra oggetti, per far funzionare tale gestione dei segnali del programma in modalità standalone, cioè non attraverso l'interprete annesso al framework, c'è necessità che io crei un dizionario.
Quindi la domanda che vi pongo è: cos'è un dizionario? E perchè serve?
Già che ci sono vi chiedo anche di spiegarmi cosa si intende per hashtable.

Grazie

P.S. http://root.cern.ch/root/CintGenerator.html il link postato si riferisce alla spiegazione di come generare il dizionario suddetto. Sì c'è scritta la motivazione per cui creare un dizionario però non è per me esaustiva, ne vorrei una generale.

[^TiGeRShArK^]

Un hashtable è una struttura dati fondamentale che ti permette di mappare una coppia (chiave, valore) in memoria.
In pratica è utile perchè puoi accedere in O(1) ad un qualsiasi elemento avendone a disposizione la chiave.
Lo svantaggio è che utilizza ovviamente più memoria di un array, quindi se le chiavi sono di tipo numerico, con un range non troppo elevato, potrebbe essere conveniente utilizzare un'array.
Le hashtable possono anche essere utilizzate per eliminare alcuni if dal codice:

if (a == "pippo") {
out = pluto;
} else if (a == "ciccio") {
out = "zio paperone";
} else if (a == "nonna papera") {
out = "paperino";
} else if (a == "paperoga") {
out = "qui quo qua"
}

si può riscrivere come:

var map = new Dictionary<string, string>(){
{"pippo", "pluto"},
{"ciccio", "zio paperone"},
{"nonna papera", "paperino"},
{"paperoga", qui quo qua"}
};

out = map[a];

[Krywen]

Quindi la domanda che vi pongo è: cos'è un dizionario?


Quando devi gestire insiemi di oggetti serve un "qualcosa" che supporti le operazioni di:
inserisci un oggetto, elimina un oggetto, leggi un oggetto, verifica se è presente questo oggetto nell'insieme ecc. Un insieme dinamico che supporta queste operazioni è detto generalmente Dizionario (dinamico vuol dire che varia nel tempo, si ingrandisce, acquista e perde oggetti o li modifica, ecc).


Quindi la domanda che vi pongo è: cos'è un dizionario? E perchè serve?

Un dizionario serve perchè supporta queste operazioni. Non stò parlando di una struttura dati particolare, ma di qualcosa che ti permetta di inserire, rimuovere,... oggetti. Se devi svolgere queste operazioni su un insieme dinamico, allora per definizione userai un dizionario.


Già che ci sono vi chiedo anche di spiegarmi cosa si intende per hashtable.

Una tavola hash o hashtable è una particolare implementazione di un dizionario (cioè, un dizionario può anche essere gestito con un unico array e moltissime ispezioni lineari, ma è un processo lento).
Le hashtable utilizzano particolari strutture dati che permettono, sotto opportune ipotesi, di cercare gli elementi in tempo O(1) (cioè un tempo costante).
Cerco di spiegare a grandi linee il funzionamento:
I componenti fondamentali sono 2: l'array e la funzione hash.

L'array è preallocato in memoria; questo conterrà tutti gli oggetti da memorizzare (o i puntatori a tali oggetti). Tale array è presente in memoria, anche se vuoto, cioè anche se l'hashtable non ha oggetti, usa questa memoria comunque.

La funzione hash è una magia matematica: si tratta di una funzione hash opportunamente modificata in base alla dimensione dell'array preallocato.
Supponiamo che ogni elemento da memorizzare nel dizionario(la nostra hashtable) abbia una chiave univoca, ad esempio un numero o un nome. Tale chiave viene data in pasto alla funzione hash, che restituisce un indice all'interno dell'array preallocato. In quella posizione dell'array verrà memorizzato quell'elemento.
(La magia stà nel fatto che la funzione distribuisce bene gli elementi nell'array e minimizza le collisioni)

Dunque prima dai la chiave alla funzione hash, e ti restituisce un indice i. Memorizzi quindi l'elemento nella i-esima posizione nell'array.

Quando vuoi vedere se un particolare elemento è presente nel dizionario, dai la sua chiave alla funzione hash e ti restituisce l'indice nell'array in cui dovrebbe essere memorizzato l'elemento.

Se la chiave è univoca per tutti gli elementi, nonostante la funzione hash possa essere scritta bene, esistono fenomeni di collisione, ad esempio due elementi con chiave diversa potrebbero avere lo stesso indice, in questo caso esistono diverse techine per risolvere la questione (una semplice può essere usare tecnica di chaining o liste di trabocco: in pratica ogni elemento dell'array è una lista di oggetti invece che un puntatore ad un solo oggetto).

Poichè l'array è preallocato può essere vantaggioso usare un array se hai pochi elementi come ha detto ^TiGeRShArK^.


Concludo infine dicendo che se non vuoi reimplementare una hashtable, o non ne vuoi usare una tu, puoi implementare un dizionario in modo semplice ma poco efficente con un array o una lista, scrivendoti le tue funzioni di inserimento, eliminazione ecc.

Ciao, spero di esserti stato utile