[Tech]Domanda di programmazione

[Davide Cesaroni]

Franco Bagnoli wrote:
> Davide Cesaroni ha scritto:
>> Salve a tuttiiiiiiii,
>> sto facendo, per l'esame di fondamenti di informatica 2, un
>> dizionario
>> basato su tabelle hash con chaining.
>> Lo voglio fare considerando due funzioni hash differenti, una
>> con il
>> metodo della divisione ed una con il metodo della moltiplicazione.
>> Il mio problema è quello di dover convertire ogni stringa in
>> un numero
>> da passare poi alla funzoine hash, ovviamente lo devo fare in
>> modo che
>> due parole differenti non restituiscano lo stesso numero.
>
> Non ricordo molto bene la questione, ma secondo me questa richiesta è
> impossibile/inutile. Se ogni possibile stringa deve dare un numero
> diverso, allora devi semplicemente concatenare i bit, ma ovviamente ti
> vengono dei numeri assurdi.
>
> In tutti gli algoritmi di hash che conosco ci sono delle collisioni,
> (ovvero: lo spazio degli indici è più piccolo rispetto a quello dei
> possibili input) che ovviamente si vogliono minimizzare, ma per far
> questo dvi avere un'idea chiara dei dati in input.
>
> In un mio vecchio programma ricordo che una semplice funzione di hash
> che funzionava bene si otteneva prendendo la somma dei vari byte
> modulo un numero sufficientemente grande (ovvero: quanto vuoi allocare
> come tabella di hash). Anche qui ovviamente devi trovare il
> compromesso giusto tra lunghezza della tabella (occupazione di
> memoria) e collisioni.
>
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...




	

	
		
___________________________________ 
Yahoo! Mail: gratis 1GB per i messaggi e allegati da 10MB 
http://mail.yahoo.it