[Tech]Domanda di programmazione

[Franco Bagnoli]

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.

-- 
Franco Bagnoli <franco.bagnoli@unifi.it>
Dipartimento di Energetica & Centro Dinamiche Complesse
Universita' di Firenze, via S. Marta, 3 I-50139 Firenze, Italy.
Tel. +39 0554796592, fax: +39 0554796342