[C] Dannate tabelle di hash!

[Gandalf_BD]

Ciao a tutti...
devo sviluppare un'applicazione che richiede l'uso di tabelle di hash che accettino come dato delle strutture e non solo dei char...

mi potreste consigliare qualche bella libreria?
quelle che ho trovato fin'ora accettano solamente dei char come tipo di dato... :muro:

grazie mille! :)

Edit: dimenticavo... mi servono per il C ;)

[cionci]

Usare delle strutture o dei char è equivalente ai fini del calcolo dell'hash...a meno che tu non intenda usare strutture variabili e non la stessa struttura per tutte le entries...

In ogni caso se vuoi usare delle strutture dati al posto delle stringhe, per calcolare l'hash passi la struttura e la dimensione alla funzione che calcola l'hash...

La funzione avrà questo formato:

int hash(void *entry, int size);

Supponendo che tu avessi già una funzione string_hash che calcolava l'hash sulle stringhe diventa semplicemente:


int hash(void *entry, int size)
{
int ret;

char *str_entry = (char *)calloc(size + 1, sizeof(char));

memcpy((void*)str_entry, entry, size);
str_entry[size] = '\0';

ret = sting_hash(str_entry);

free(str_entry);
return ret;
}

Per usarlo:

struct s {...} a;

hash((void *)a, sizeof(struct s));

Edit: in sistemi in cui il char è più di un byte funzionerebbe comunque perchè la metà dei byte che avanzano (supponendo il char da due byte) sono inizializzati a zero da calloc.

[trallallero]

scusate ma cos'é una tabella di hash ?
e poi la funzione hash() di cionci ha come primo parametro void *entry che non viene usato, a che serve ?

[cionci]

Scusa, mi sono dimenticato la copia nella stringa ;) Correggo...

[trallallero]

Scusa, mi sono dimenticato la copia nella stringa ;) Correggo...
ah ok, ma cos'é una tabella di hash ? :stordita:

[Gandalf_BD]

grazie cionci, ma io cercavo delle librerie già sviluppate :D :angel:

[cionci]

Sai cos'è un hash ? Credo di sì, ma lo spiego brevemente comunque...

Un hash è anche detta impronta digitale (fingerprint), è una funzione matematica che ritorna un numero compreso in 0 e (2^N)-1 per qualsiasi valore che gli si passi. N è la dimensione in bit dell'hash. Non importa come si calcola l'hash, l'importante sarebbe ottenere un risultato uniformemente distribuito nel codominio. In pratica l'hash è una funzione che associa ad un elemento del codominio 1 o più elementi del dominio.

Ad esempio, per ordinare una serie di stringhe solo per il primo char è come se si creasse un hash.

Si dice "collisione" quando la funzione hash ritorna lo stesso valore per due o più elementi dell'esecuzione corrente.

E visto che per ordinare queste stringhe in base allo hash ho più elementi che mi corrispondono allo stesso hash posso, devo organizzare la struttura dati tabella hash in uno di questi modi:

1) in caso di numero elementi totale limitato (che so 256) posso creare una matrice 256*256 (visto che in teoria tutti gli elementi mi potrebbero ritornare lo stesso hash)

2) in caso di numero illimitato o sconosciuto posso creare un vettore di liste che indicizzo con il valore ritornato dalla funzione di hash (la funzione di hash deve quindi ritornare una valore accettabile, solitamente massimo 16 o 24 bit)

lista **tabella_hash = (lista **)calloc(256, sizeof(lista *);

E per ogni elemento lo vado ad inserire nella lista corrispondente alla sua funzione hash:

inserisci_nella_lista(tabella_hash[hash(elemento)], elemento);

Ovviamente lo scopo dell'hash è facilitare la ricerca.
L'inserimento può essere anche ordinato...il che facilita ulteriormente la ricerca.

Nota che lo scopo dell'hash sarebbe la possibilità di effettuare sia la ricerca che l'inserimento in O(1). Quindi l'inserimento ordinato cozza un po' con questa teoria. Per questo si usano dei metodi di inserimento alternativi (che consistono nel trovare una cella libera successiva) in presenza di collisioni.

Come si può evincere dalla spiegazione sopra si potrebbe limitare la dimensione della lista a pochi elementi e di conseguenza si avrebbe ancora ricerca ed un inserimento O(1).

Nella pratica si lascia la lista libera perchè si suppone che la funzione hash sia debitamente pesata e ampia da limitare le collisioni ad un numero molto minore dell'ampiezza del valore di ritorno della funzione hash.

Chiaramente all'aumentare del numero di elementi al collisione sarà sempre più probabile, fino a diventare certa quando gli elementi raggiungeranno l'ampiezza del valore di ritorno della funzione hash.

[cionci]

grazie cionci, ma io cercavo delle librerie già sviluppate :D :angel:
Credevo che tu avessi già una tabella hash per le stringhe.

[trallallero]

@cionci: grazie, io non conoscevo ll'argomento :)

[Gandalf_BD]

Credevo che tu avessi già una tabella hash per le stringhe.
fa nulla.. grazie lo stesso :)

[cionci]

Spiegaci un po' le dimensioni di questo hash che ti interessa...quanti elementi vuoi avere nella struttura ? A scriverlo poi non ci dovrebbe volere molto...

[Gandalf_BD]

eh... in realtà non so a priori quanto grande mi serva... dev'essere una cosa un po' dinamica... cmq, nel frattempo, ho trovato questa http://directory.fsf.org/CFL.html
che ha un sacco di roba, tra cui le tabelle di hash...