[Tech]Domanda di programmazione

[Davide Cesaroni]

Szymon Stefanek wrote:
> On Tuesday 04 April 2006 20:50, Davide Cesaroni wrote:
>
>   
>> ciò che hai detto lo so bene, è ovvio che una funzione hash abbia delle
>> collisioni, ma io intendevo una cosa un po' differente (mi sono spiegato
>> molto male in effetti).
>>
>> Consideriamo h(k), la funzione hash che trasforma un intero k in un altro
>> intero che sarà poi un indice dell'array usato come tabella hash (che
>> sarà di dimensione ridotta rispetto al numero di parole da inserire).
>> Adesso siamo tutti d'accordo sul fatto che presi due k differenti c'è la
>> possibilità che il valore restituito dalla funzione hash sia lo stesso
>> (le collisioni a cui ti riferivi te); ciò che volevo io era trasformare
>> la stringa in un numero da passare alla funzione hash in modo che questa
>> mi dica in che posizione inserire la parola. Perciò non volevo che due
>> parole differenti portassero allo stesso valore numerico, perchè sennò
>> oltre alle collisioni dovute ad h(k) avrei anche quelle dovute alla
>> funzione di trasformazione della striga...
>>
>> spero di essermi spiegato meglio...
>>     
>
> Si, ma ti stai complicando la vita :D
>
> La somma dei caratteri ascii modulo dimensione della tabella, come suggeriva 
> Franco, è una funzione hash ottima per una marea di applicazioni.
>
> Cmq, non è sbagliato ciò che dici: è vero che la somma dei caratteri ascii 
> porta "mediamente" verso un sottoinsieme ristretto di numeri. Soprattutto se 
> usi le parole del linguaggio naturale come chiavi.
>
> Scendere sotto 100 sarà difficile perchè le parole di una sola lettera sono 
> rare. Salire sopra 1000 sarà difficile perchè le parole con più di 10 lettere 
> sono di nuovo rare. Bisognerebbe verificare con criterio ma immagino che le 
> somme più frequenti saranno attorno a 400-500.
>
> Questo significa che se usi una tabella con più di 1000 elementi probabilmente 
> l'operazione di modulo non avrà mai effetto e l'occupazione della tabella non 
> sarà efficiente.
>
> L'idea è quella di avere un numerone grande modulo un numero relativamente 
> piccolo.
>
> Una soluzione può essere quella di moltiplicare ogni carattere ascii per il 
> valore corrispondente alla sua posizione nella stringa. 
> Oppure (più fico) shiftare di un paio di bit a sinistra ad ogni iterazione.
>
> unsigned int hash(const char * p)
> {
> 	unsigned int u = 0;
> 	while(*p)
> 	{
> 		u <<= 2; // shifta PRIMA, altrimenti ottieni solo pari
> 		u += (unsigned int)*p;
> 		p++;
> 	}
> 	return u % dimensione_tabella;
> }
>
> Questo dovrebbe portarti ad avere numeri grandi (rispetto ai quali la 
> dimensione della tabella è piccola) e hash diversi per parole che hanno una 
> somma ascii uguale (come "la" e "al").
>
> Comunque queste considerazioni le puoi fare solo se sai a priori di che tipo 
> saranno le chiavi utilizzate.
>   
inanzitutto grazie per i consigli, poi volevo aggiungere che l'idea è
quella di prendere le stringhe da inserire nell'hash da un file di testo
giusto per fare una statistica delle parole (forse c'erano altri modi
migliori ma volevo fare qualcosa che trattasse degli argomenti trattati
a lezione). L'idea di shiftare i bit è molto interessante e ora valuterò
se usare questa o bovinamente una somma dei valori di ogni carattere;
tanto se collisione ci deve essere...casomai potrebbe essere
interessante vedere come varia la distribuzione dei dati, oltre che in
funzione dell'hash, anche in base al criterio scelto per calcolare il
valore numerico di una stringa.

Grazie ancora a tutti...se avete altri consigli, suggerimenti o critiche...

		
___________________________________ 
Yahoo! Messenger with Voice: chiama da PC a telefono a tariffe esclusive 
http://it.messenger.yahoo.com