Newsgroup: it.comp.lang.c++
Titolo: Codice hash

Leggendo "Il linguaggio C++" di B. Stroustrup, mi sono bloccato all'esempio
della calcolatrice, nel punto in cui parla della ricerca nella tabella dei
nomi usando un codice hash: a parte che non ho la minima idea di cosa sia un
codice hash, non ho capito a cosa serve il seguente pezzo di codice:
name *look(const char*p, int ins=1) {
int ii=0;
const char *pp = p;
while (*pp) ii = ii << 1 ^ *pp++;
if (ii<0) ii = -ii;
ii%=TBLSZ;
...
}
dove erano state fatte precedentemente le seguenti posizioni:
struct name {
    char *string;
    name *next;
    double value;
};
const TBLSZ = 23;
name *table[TBLSZ];
Mi pare di aver capito che il ciclo while serva ad identificare in qualche
modo la stringa passata alla funzione, per poi confrontarla con gli elementi
della tabella (cosa che viene fatta nella parte che ho omesso), ma non
capisco per quale motivo faccia cosě: non era piů semplice ricercare nella
tabella usando il campo string come chiave? Grazie,
Cecco

 tabella usando il campo string come chiave?
Da quello che scrivi di fatto hai capito come funziona l'hashing anche se non
sei arrivato a trarne le conclusioni e quindi ti sfugge una parte del
meccanismo.
Provo spiegarti la cosa brevemente (se cerchi un buon reference sugli algoritmi
e le strutture dati puoi approfondire meglio).
Il concetto e' questo. Supponiamo di avere una funzione che applicando un
qualche algoritmo non meglio specificato calcola, dato un qualunque elemento del
container, un valore numerico 'breve' (per esempio un int). Gli elementi del
container possono essere strutture semplici come una coppia di coordinate (due
double) o una stringa (di lunghezza variabile) oppure complesse (un record con
molti field). Supponiamo di lavorare con delle stringhe. Se lavoriamo con
stringe la funzione di hash calcolerà un int a partire da una stringa.
Domanda: che possibilità ci da il codice hash nella gestione di un container di
stringhe?
Supponiamo di dover scrivere un generico container di stringhe dove non e'
possibile inserire due volte la stessa stringa (o due stringhe uguali, se
preferisci), e' possibile inserire e rimuovere stringhe, e' possibile iterare le
stringhe contenute, e' possibile verificare se una stringa e' contenuta o meno.
In altre parole una funzionalita' simile a std::set<string> salvo che non ci
importa che le stringhe siano mantenute in ordine alfabetico. Nota: per un set
abbiamo bisogno di una funzione d'ordine stretto (per default std::set usa
operator<) mentre nel caso di un container ad hash questa funzione non e'
necessaria. Pero' e' necessaria una funzione di hash! Entrambe richiedono una
funzione di paragone (operator==).
Senza funzione di hash e senza funzione d'ordine abbiamo una sola possibilità:
un contenitore in cui ad ogni operazione di accesso scorriamo tutti gli elementi
verificando se l'elemento che vogliamo inserire (o eliminare o cercare) esiste o
meno. Questo significa che ogni operazione e' O(n).
Con una funzione d'ordine abbiamo un'alternativa: mantenere il container
ordinato. Con un albero binario e gli algoritmi che lo mantengono bilanciato
(per esempio RB tree) possiamo arrivare a O(log n) per ogni operazione.
Con una funzione di hashing, purche' la funzione sia fatta nel modo giusto,
possiamo arrivare a O(k), ovvero un tempo costante e indipendente dal numero di
elementi presenti nel container.
Nota due cose:
1) la funzione di hash deve essere appropriata
2) O(n), O(log n) e O(k) indicano come CRESCE il tempo di esecuzione al crescere
del numero di elementi. Quindi se gli elementi sono pochi non e' detto che un
algoritmo O(log n) sia migliore di uno O(n) e persino un O(k) puo' essere
all'inizio piu' lento di un O(n).
Vediamo come possiamo implementare, a grandi linee, un container che sfrutta
l'hashing.
Facciamo un caso banale: la funzione di hashing ritorna un numero fra 0 e 10000.
Noi manteniamo un vettore di 10000 puntatori a stringa. Ad ogni operazione
calcoliamo il valore di hashing della stringa da inserire/rimuovere/cercare e lo
usiamo come indice del vettore. Il puntatore punta alla stringa se esiste oppure
e' null se non esiste.
Questa e' l'idea di base. Semplice ed efficace. E soprattutto veloce (anche se
ci sono già MOLTI elementi nel container.
A questo punto passiamo alle obiezioni e ai casi particolari:
Cosa succede se due stringhe diverse hanno lo stesso valore di hashing?
Risposta: la funzione di hashing ideale e' tale che questo non accade. In realtà
questo e' impossibile (non puoi mettere in n bit tutti i casi possibili di k bit
con k>n). Quindi dobbiamo gestire la cosa verificando che la stringa trovata sia
effettivamente quella giusta (con operator==) e decidendo cosa fare se non lo
e'. Le alternative in caso di "hash collision" sono principalmente:
1) aumentare la dimensione della tavola (per esempio passare da 10000 elementi a
50000). Questo puo' essere piu' o meno scomodo e prevede che la funzione di
hashing venga modificata di conseguenza, cosa che in runtime puo' essere
difficile.
2) utilizzare la tecnica del rehashing. Ovvero usare una seconda funzione di
hash in caso di collisione, aggiungere il valore di hash in coda alla stringa e
calcolare un nuovo hash con la stringa modificata o altre cose simili.
Naturalmente questa tecnica potrebbe spostare il problema o diminuire le
performance (al punto che non sono piu' O(k) nei casi degeneri).
3) invece che un puntatore alla stringa, ogni 'slot' del container contiene un
puntatore ... ad un container di stringhe. Se le collisioni sono poche anche una
lista e' sufficiente (poi controlli sequenzialmente le stringhe nella lista in
O(M) dove M e' il numero di collisioni avvenute). In alternativa se esiste una
funzione d'ordine puoi usare un RB Tree (tipo std::set con O(log M) per
l'accesso) o anche un vettore mantenuto ordinato con ricerca dicotomica O(log M)
e insert in media proporzionale a M/2.
Dal punto di vista del "vettore principale" ovviamente puo' non essere un
vettore. La struttura di base e' comunque ad accesso diretto con indice un
numero intero (l'output della funzione di hash). Questo puo' avere una
dimensione prefissata ma potrebbe anche averne una "dinamica". Ovvero una volta
raggiunto un certo % di riempimento puo' convenire aumentarne la dimensione per
diminuire le collisioni. Un meccanismo "semplice" e' quello di lavorare per
frazioni della dimensione massima (dimensione di hash ovvero il numero piu'
grosso generato dalla funzione di hashing che chiameremo H). Per esempio puoi
partire con un 'vettore' lungo H/16 per poi quadruplicarlo fino a due volte man
mano che cresce. Per accedere al vettore quando non ha la dimensione massima
puoi usare il codice di hash modulo la dimensione del 'vettore' (di fatto stai
creando un meccanismo che ti permette di modificare a runtime la funzione di
hashing imponendo che l'ultima operazione di tale funzione sia un modulo).
Quindi anche H, la dimensione iniziale del contenitore, a che percentuale di
riempimento questo cresce e di quanto, sono tutte variabili da decidere.
Come vedi ci sono molte possibili variabili, e in vari ambiti, che possono (o
meno) influire sulle prestazioni reali.
L'ultima considerazione (che poi e' la parte piu' difficile e importante) e':
come deve essere fatta la funzione di hashing?
Idealmente ha questa caratteristica: distribuzione casuale nel range 0-H. Ovvero
tutti i valori sono equiprobabili. Nota che il concetto di equiprobabilità in
teoria dipende da cosa inserisci. Parlando genericamente di stringhe ASCII
(l'ACSII a 7 bit) si potrebbe dire che il primo carattere e' equiprobabile fra 0
e 127. Se pero' le stringhe contengono parole italiane ovviamente 'A' come primo
carattere e' molto piu' probabile di 'X'.
Lo scopo della funzione di hashing e' quello di "disperdere" il piu' possibile i
valori diminuendo il piu' possibile le collisioni.
Una funzione di hashing per le stringhe abbastanza comune (e veloce da
calcolare) e' proprio quella che vedi nel codice postato da te (riguardatelo ora
e ti sarà piu' chiaro).
Spero di esserti stato utile (e anche ad altri).
Piccola nota per gli articolisti (Cuni ci sei?): puoi postare questo messaggio
come articolo-in-abbozzo su 
programmazione.it
 riservandoti di rivederlo e
migliorarlo approfondendolo in un secondo tempo (qualche cosa dovrebbe dire il
Sedjewick, sicuramente il Knuth e' un buon reference, anche altri testi su
algoritmi e strutture dati dovrebbero parlare di questo problema).
--
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556

Ti ringrazio per la esauriente spiegazione, anche se, ad essere sincero, non
mi aspettavo una risposta cosě lunga e complessa. Adesso ho capito perchč
non consigliano lo Stroustrup ai newbies!
Cecco

 questo problema).
ok, l'ho salvato sul mio hd. Appena ho un po' di tempo lo riguardo bene, lo 
metto un po' a posto e poi lo pubblico online.
ciao Anto
-- 
Antonio Cuni, 19 anni, studente
Brainbench C++ Master: 4.6, higher than 98% of all previous test takers.
C Language: 3.32, higher than 79% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it