Olimpo Informatico

saetta · Eroe in grazia degli dei Registrato: 25/02/08 11:52 Messaggi: 129

Salve, sto creando una semplice libreria C per la gestione di tabelle hash con liste di collisione. (non sparate, sono innocente!!! Laughing

)

Mi chiedevo come scegliere una buona funzione hash che distribuisca i dati immessi in modo abbastanza omogeneo, non come la mia che infila tutto usando solo 2 liste di collisione, tra le molte disponibili.

Ovvero io ho una sitazione del tipo

TABELLA --- LISTA DI COLLISIONE
[0]------->elem_a->elem_b->elem_c->elem_d->elem_n
[1]->null
[2]->null
[3]------->elem_z->elem_t
[4]->null

ma vorrei una distribuzione migliore dei dati (ovvero sto lottando contro il clustering) tipo così:

TABELLA --- LISTA DI COLLISIONE
[0]------->elem_a->elem_b->
[1]------->elem_c
[2]------->elem_t
[3]------->elem_z
[4]------->elem_d->elem_n

Scusate se mi spiego a "disegnini" ma credevo risultasse + chiaro.

Sto usando:
una hash_stringhe(key, dim_tabella) e una hash_interi(key, dim_tabella)
ed entrambe calcolano un intero (con atoi() la prima) che usero' come indice dell'array(TABELLA[0]...TABELLA[size-1]) che mi indicizza le liste di collisione.

Possibile venga quasi sempre lo stesso indice???

SverX · Inviato: 17 Mar 2010 18:09 Oggetto: Re: [algoritmi] funzioni e tabelle hash

saetta · Inviato: 17 Mar 2010 19:05 Oggetto:

Uso due funzioni tirate giù "di getto" e comunque non ho altre idee migliori.

SverX · Inviato: 18 Mar 2010 12:02 Oggetto:

boh, secondo me potresti sommare insieme tutti i valori ascii dei caratteri della stringa e fare il modulo del numero delle tue liste di collisione... dovresti trovare un po' più di uniformità, anche se poi non è che sia così necessaria...

saetta · Inviato: 18 Mar 2010 16:26 Oggetto:

Ma come...perchè non credi sia necessaria?
Va bene che alloco memoria per ogni elemento inserito solo nel momento in cui serve, ma avere anche un array di ptr a liste dove solo una misera minoranza di ptr sono inizializzati devo dire che non mi piace granchè.

Insomma mi sa che sto cercando il miracolo dell'ottima distribuzione su liste di collisione.

Grazie.

SverX · Inviato: 19 Mar 2010 15:34 Oggetto:

saetta · Inviato: 20 Mar 2010 16:05 Oggetto:

No purtroppo la specifica recita esplicitamente "collisioni gestite con liste di trabocco" ed io cercavo un modo per calcolare delle chiavi, sulla base del carico utile (f.ne hash), sufficientemente varie, da distribuire al meglio i carichi sulle varie liste di trabocco. Crying or Very sad

SverX · Inviato: 22 Mar 2010 13:41 Oggetto:

allora io punterei ad usare il modulo. Per le stringhe puoi sommare tutti i valori ascii di tutti i caratteri che compongono la stringa e poi fare modulo del numero di liste, per i numeri fai il modulo direttamente...

saetta · Inviato: 22 Mar 2010 15:37 Oggetto:

Provo...! Grazie!

saetta · Inviato: 22 Mar 2010 19:05 Oggetto:

Una conclusione l'ho tratta...anche a giudicare dall'errore che dicevo QUI penso che sia tutto dovuto a queste 2 f.ni hash che lasciano proprio a desiderare.

Dato che devono ritornare unsigned int, mi sorgono alcune (niubbe) domande:

1)Devo convertire il risultato in numero Naturale (abs(num)) oppure il ritorno mediante un tipo "unsigned" mi garantisce la "positività" del numero?

2)Cosa faccio ritornare alla f.ne se gli vengon passati argomenti invalidi e devo uscire con una sorta di errore (il tipico -1 dei return a int...)?
(avevo pensato di fargli restituire size che e' un valore che non ha riscontro nell'array [0 ... size-1] ma ogni volta devo testarlo dopo aver chiamato la f.ne hash)

Grazie x la disponibilità... e la pazienza LOL

saetta · Inviato: 23 Mar 2010 10:38 Oggetto:

Tanto x cominciare leviamo il (size-1) e lasciamolo come (size) nella return di entrambe le f.ni.
L'operazione modulo fa tutto cio che serve con size e non size-1... Laughing

Mi rimane il dubbio su cosa far ritornare alla f.ne hash se size è 0...

SverX · Inviato: 23 Mar 2010 15:16 Oggetto:

la stringa vuota o il numero 0 sono entrambi valori validi... insomma, come può una funzione di hash ricevere valori non validi?

saetta · Inviato: 23 Mar 2010 16:07 Oggetto:

Si in effetti bisognerebbe proprio darglieli.... comunque essendo basata, la mia implementazione, su un'operazione di modulo ... non posso mica dargli size = 0 che provocherebbe una divisione per zero, no?

a MOD b = resto(a DIV b) Surprised

SverX · Inviato: 23 Mar 2010 17:58 Oggetto:

ma b è il numero delle liste, sarà costante... e non zero di sicuro no? Smile

saetta · Inviato: 23 Mar 2010 22:06 Oggetto:

Vada per la soluzione "bruta" ovvero dentro le hash non faccio nessun controllo dato che le uso solo su valori validi (gli faccio il check-in come all'aeroporto prima di darle in pasto alle f.ni hash) all'interno di una libreria mia...
e speriamo che Sverx o Freemind non usino mai tali mie funzioni!!! Wink

Grazie!