[C] Hashing

[Ancosen]

Qualcuno mi può parlare un po' degli algoritmi di hashing? Mi potete fare un esempio di una Hash Table scritta in C? Grazie mille!

[tglman]

Be in c si possono costruire duve vettori di stringe o anche un record associano ad una stringa un'altra, in questo modo è sufficente cercare una stinga nel vettore delle chiavi per poi trovare il corrispettivo valore

[Ancosen]

Ma in pratica la struct della tabella hash qual'è? Mi puoi fare un esempio? Più che altro l'uso delle tabelle hash qual'è? Mi hanno dato da fare un progetto ma non ho chiara la struttura della tabella hash, quindi non posso lavorarci...

[tglman]

be il concetto di base è questo :
ho un blocco di informazioni memorizate in coppia chiave, valore es:
chiave1=valore1
chiave2=valore2
chiave3=valore3
chiave4=valore4

poi ho una funzione che passato per parametro una chiave mi restituisce il valore, es prototipo:
char *get(char *);

praticamente è un vettore che invece di usare degli indici numerici progressivi per accedere ai valori utilizza delle stringhe.

Ciao..

[end.is.forever]

Una funzione hash riassume una stringa di bit di lunghezza arbitraria in una di lunghezza fissa, per esempio un intero a 32 bit.
Per cui puoi pensare di utilizzare come indicizzatore di una tabella un dato di qualsiasi lunghezza, appunto la chiave.
Una volta applicata la funzione di hash alla chiave e ottenuto il riassunto utilizzi quello come indice per ottenere l'indirizzo a cui accedere in un vettore semplice.

Più la funzione hash è sicura (e più bit di riassunto usi) più è difficile che due chiavi diverse siano in collisione, cioè abbiano lo stesso riassunto.

Eccoti uno pseudocodice copiato da http://en.wikipedia.org/wiki/Hash_table

 record pair { key, value }
 var pair array slot[0..numSlots-1]
 
 function findSlot(key) {
     i := hash(key) modulus numSlots
     loop {
         if slot[i] is not occupied or slot[i].key = key
             return i
         i := (i + 1) modulus numSlots
     }
 }
 
 function lookup(key)
     i := findSlot(key)
     if slot[i] is occupied   // key is in table
         return slot[i].value
     else                     // key is not in table
         return not found     
 
 function set(key, value) {
     i := findSlot(key)
     if slot[i] is occupied
         slot[i].value := value
     else {
         if the table is almost full
             rebuild the table larger (note 1)
         i := findSlot(key)
         slot[i].key   := key
         slot[i].value := value
     }
 }

[Ancosen]

Quello che non riesco a capire e se quello che mi viene chiesto di implementare è una tabella hash semplice o una tabella hash più complessa...

Vi posto i link ai PDF che mi ha dato il mio professore... C'è questo HASHTABLE che non capisco cosa sia: non mi sembra molto chiaro... Eccoli qua:

Questa è la descrizione del progetto...

http://www.dsi.uniroma1.it/~galesi/descrptog.pdf

E questo è il modulo in cui è presente il tipo HASHTABLE

http://www.dsi.uniroma1.it/~galesi/tavole.pdf

Aiutatemi please!

[Ancosen]

/*
* Elemento di una tavola.
*
* Il campo key è la chiave dell'elemento la stringa.
* Il campo info è un puntatore alla struttura contenente i dati
* associati alla cbiave. Per poter implementare la tavola indipendentemente
* dal tipo dei dati associati alla chiave, questo campo è di tipo void*.
*/
struct tabelem
{
char *key; /*chiave dell'elemento*/
void *info; /*informazioni associate alla chiave*/
};

/*
* Lista di elementi di una tavola.
*/
struct telist
{
struct tabelem *el; /*elemento della tavola*/
struct telist *next; /*coda della lista*/
};

/*
* Tavola di elementi.
*
* La tavola è formata da
* - una tavola hash nella quale gli elementi vengono inseriti e ricercati per
* mezzo della chiave
* - il puntatore alla lista di tutti gli elementi nella tavola
* NB La lista degli elementi serve a scorrere in modo sequenziale gli elementi
* presenti nella tavola.
*/
struct table
{
HASHTABLE htable; /*Tavola Hash*/
struct telist *ls; /*Lista di tutti i nodi*/
};

In base a questo io avrei elaborato questa tavola hash come struttura... Secondo voi è quella che intende il testo??? Eccola

struct hash
{
int a;
struct telist *list;
}
typedef struct hash HashTable;
typedef HashTable *HASHTABLE;

Aiutatemi per favore!

[Ancosen]

Dai per favore!

[Ancosen]

Nessuno proprio mi può aiutare?

[Darkslide]

Prima di tutto una precisazione....esistono 2 tipi di hash:hash chiuso e aperto.

L'hash aperto,in caso di collisione tra chiavi usa una lista per inserire gli elementi.

L'hash chiuso invece applica algoritmi di rehash,in caso di collisione tra 2 chiavi entra in gioco un secondo algoritmo che genera una nuova chiave.


A te quale dei 2 è stato chiesto di implementare?

[Ancosen]

Mi è stato chiesto di implementare l'hash aperto. La lista è la struct telist, che ho postato poco più su, insieme ad altre due strutture... La terza rappresenta una cella dell'hashtable credo... Soltanto che non capisco come vada definito il tipo di dato HASHTABLE... Se mi dessi una manina te ne sarei infinitamente grato... Grazie!

[Ancosen]

up