[Tech]Domanda di programmazione

[Szymon Stefanek]

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.


-- 

Szymon Stefanek

------------------------------------------------------------------------------
-
- Solitary trees, if they grow at all, grow strong.
-
------------------------------------------------------------------------------
-------------- parte successiva --------------
Un allegato non testuale è stato rimosso....
Nome:        non disponibile
Tipo:        application/pgp-signature
Dimensione:  189 bytes
Descrizione: non disponibile
URL:         <http://lists.linux.it/pipermail/flug-tech/attachments/20060405/277944ee/attachment.pgp>