Newsgroup: it.comp.lang.c
Titolo: funzioni hash

Mi hanno consigliato di usare delle funzioni hash per creare un mio piccolo
database con dei record, ma non so cosa siano queste funzioni. Chi mi da
delle delucidazioni?
grazie
--
San Vegeta from Hell
http://www.geocities.com/Area51/Dungeon/8436
http://come.to/Fantasy.it

 delle delucidazioni?
Una funzione hash č una trasformazione dallo spazio delle chiavi a
quello degli indici. Mi spiego meglio: mettiamo tu abbia dei record
sequenziali contenenti dei nomi. La funzione hash trasformerebbe un nome
in un numero indicante la posizione del record. Questo consente
l'accesso diretto al record stesso che č il piů veloce possibile.
Queste funzioni hanno perň un difetto: causano collisioni, nel senso che
spesso due trasformazioni danno come risultato lo stesso numero. Questo
si puň risolvere in due modi: aumentando la dimensione dello spazio
degli indici (aumentare la dimensione statica del database) oppure
utilizzando una tecnica mista ad accesso diretto/sequenziale che, in
caso di collisione, gestisca una lista di record a partire dalla
posizione ottenuta dalla funzione hash.
EMG

delle delucidazioni?
Le tabelle hash sono strutture utili per memorizzare e reperire dati in modo
veloce.
Esse supportano l'inserimento, la cancellazione e la ricerca di un elemento, ma
non consentono, tuttavia, l'accesso agli elementi in modo ordinato.
Una tabella hash e' in pratica un vettore in cui ogni elemento viene memorizzato
in una posizione, il cui indice viene calcolato mediante, appunto, una funzione
hash.
Quindi, una generica funzione hash h(K) si occupa di trasformare la chiave K,
associata ad un elemento, in un indice compreso tra 0 e m-1, se m e' il numero
totale di posizioni nell'array.
Se nella tabella ci sono n elementi, allora si chiama "Load Factor" il rapporto
n/m.
Una tabella vuota ha LF = 0, mentre una piena LF = 1.
Ovviamente, pero', dato che il numero degli elementi dell'array e' generalmente
inferiore a quello di tutte le possibili chiavi, e' sicuro che piu' di una di
queste ultime andra' ad occupare la stessa posizione.
Ma questo problema, chiamato "collisione", viene facilmente risolto, per
esempio, adottando come elementi del vettore delle liste.
Immagina, per esempio, di costruire un array di stringhe, in cui memorizzare
ogni stringa, usando come chiave la stringa stessa.
Questo potrebbe servire, per esempio, per un dizionario, in cui devi cercare una
determinata parola.
Ovviamente immagina la differenza tra scorrere tutto il dizionario per la sua
ricerca ed accedere _direttamente_ alla sua posizione, usando come chiave la
parola stessa.
Supponi che la parola sia "armadio".
Supponiamo che sia h("armadio") = 10 (abbiamo usato come chiave la stringa
stessa)
Ci sono molti modi in cui la funzione hash puo' trasformare una chiave in un
valore intero, e il valore 10 e' arbitrario.
Alla posizione hash_table[10] ci sara' quindi la parola "armadio".
Ci saranno di sicuro altre parole che andranno a collidere con "armadio" in
posizione 10 e allora hash_table[10] non sara' una stringa, ma una lista di
stringhe, in modo che, di volta in volta, le parole "sorelle" andranno a
posizionarsi l'una in coda all'altra.
Quando l'andrai a ricercare non dovrai scorrere tutto il dizionario, ma
semplicemente calcolare di nuovo la chiave, e scorrere la lista corrispondente
al valore trovato alla ricerca della tua parola.
Per ora mi fermo qui, dato che mi sto facendo prendere la mano :) , ma se vuoi
informazioni dettagliate fammelo sapere.
Ti lascio, comunque, di seguito un programma con cui ti illustro la tecnica che
ti ho descritto :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _hash_list_item { char * s ;
                                 struct _hash_list_item * next ;
                               } hash_list_item ;
typedef hash_list_item *  hash_list_item_ptr ;
static const unsigned HASH_SIZE = 256 ;
unsigned  hash_func ( const char * key )
{
          unsigned r = 0 ;
          while ( *key ) r += *key++;
          r %= HASH_SIZE ;
          return ( r ) ;
}
void  hash_list_insert ( hash_list_item_ptr * p , const char * s )
{
      hash_list_item_ptr  new_item ;
      new_item = malloc ( sizeof ( hash_list_item ) ) ;
      new_item->next = NULL ;
      new_item->s = malloc ( strlen ( s ) + 1 ) ;
      strcpy ( new_item->s, s ) ;
      if ( *p == NULL ) *p = new_item ;
      else
      {
         while ( (*p)->next ) *p = (*p)->next ;
         (*p)->next = new_item ;
      }
}
void  hash_table_insert ( hash_list_item_ptr ht[], const char * s )
{
      unsigned index ;
      index = hash_func ( s ) ;
      hash_list_insert ( & ht[ index ], s ) ;
}
int   hash_table_find ( hash_list_item_ptr ht[], const char * s )
{
      unsigned  index ;
      hash_list_item_ptr  cursor ;
      index = hash_func ( s ) ;
      cursor = ht [ index ] ;
      while ( cursor )
      {
            if ( !strcmp( cursor->s, s ) ) return 1 ;
            cursor = cursor->next ;
      }
      return 0 ;
}
int main()
{
    hash_list_item_ptr  ht [ HASH_SIZE ] ;
    int      c = 0 ;
    unsigned idx, n = 0 ;
    char     parola[20] ;
    for ( idx = 0 ; idx < HASH_SIZE ; idx++ )
        ht [ idx ] = NULL ;
    hash_table_insert ( ht, "armadio" ) ;
    hash_table_insert ( ht, "computer" ) ;
    hash_table_insert ( ht, "libro" ) ;
    hash_table_insert ( ht, "dinosauro" ) ;
    hash_table_insert ( ht, "lavagna" ) ;
    hash_table_insert ( ht, "valanga" ) ;
    if ( hash_table_find ( ht, "valanga" ) )
       puts(" parola trovata ! ") ;
    else
       puts(" parola non trovata ! ");
    return 0 ;
}
--
Posted from 
itaca.ulysse.it
 [195.223.254.1]
via Mailgate.ORG Server - 
http://www.mailgate.org




 Ma in pratica la funzione hash definisce o trasforma una struttura dati?
Ne trasforma le chiavi. In un certo senso si potrebbe anche dire che
definisce una nuova struttura dati a partire dalla prima, perché no.
EMG