[C] ::. Funzione hash .::

[mjordan]

Stavo leggendo il codice di VMD e mi sono imbattuto in un'implementazione di una tabella hash. Implementazione classica, se non per la funzione hash, di cui non riesco a capirne la semantica.

La struttura è tradizionale e di semplice comprensione:

typedef struct hash_t {
            struct hash_node_t ** bucket;  
            int size;                             
            int entries;                     
            int downshift;                 
            int mask;                               
} hash_t;

Il tipo hash_node_t è così definito:

typedef struct hash_node_t {
            int data;                            
            const char * key;              
            struct hash_node_t *next;  
} hash_node_t;

e fin quì ci siamo.
Analizziamo ora la funzione per l'inizializzazione della tabella:

void hash_init(hash_t *tptr, int buckets) {
             /* make sure we allocate something */
             if (buckets == 0)
                      buckets = 16;

             /* initialize the table */
             tptr->entries = 0;
             tptr->size = 2;
             tptr->mask = 1;
             tptr->downshift = 29;

             /* ensure buckets is a power of 2 */
             while (tptr->size < buckets) {
                      tptr->size <<= 1;
                      tptr->mask = (tptr->mask << 1) + 1;
                      tptr->downshift--;
             }

             /* allocate memory for table */
             tptr->bucket = (hash_node_t **)calloc(tptr->size, sizeof(hash_node_t *));
}

... e la funzione per il calcolo della funzione hash:

static int hash(const hash_t * tptr, const char * key) {
         int i = 0;
         int hashvalue;

         while (*key != '\0') {
                  i = (i << 3) + (*key++ - '0');
                  hashvalue = (((i * 1103515249) >> tptr->downshift) & tptr->mask);
                  if (hashvalue < 0) {
                           hashvalue = 0;
                  }
         }
         return hashvalue;
}

Secondo voi quale dovrebbe essere la semantica dei campi downshift, mask e dell'uso degli operatori di shift sugli interi ai fini della funzione hash?

[71104]

tutto quello che riesco a capire io (a quest'ora, intendiamoci ) è che l'autore ha ritenuto opportuno realizzare un algoritmo di hashing che traduce in un int il numero espresso nella stringa key (perché non abbia usato atoi non si sa), lo moltiplica per un numeraccio (1103515249), lo shifta a destra di tot posti, e azzera solo alcuni bit. di quanti posti deve shiftare a destra? tanti quanti specificati nel campo downshift specifico di quella istanza di hash table. quali bit deve azzerare? quelli azzerati nella maschera specifica di quella istanza ecc. ecc.

le motivazioni matematiche che gli hanno fatto concepire questo algoritmo difficilmente le saprò mai

[mjordan]

Originariamente inviato da 71104

tutto quello che riesco a capire io (a quest'ora, intendiamoci ) è che l'autore ha ritenuto opportuno realizzare un algoritmo di hashing che traduce in un int il numero espresso nella stringa key (perché non abbia usato atoi non si sa), lo moltiplica per un numeraccio (1103515249), lo shifta a destra di tot posti, e azzera solo alcuni bit. di quanti posti deve shiftare a destra? tanti quanti specificati nel campo downshift specifico di quella istanza di hash table. quali bit deve azzerare? quelli azzerati nella maschera specifica di quella istanza ecc. ecc.

Fin quì ci arrivavo pure io

le motivazioni matematiche che gli hanno fatto concepire questo algoritmo difficilmente le saprò mai

Appunto ho parlato di semantica, mi interessano proprio quelle motivazioni.

[71104]

Originariamente inviato da mjordan

Appunto ho parlato di semantica, mi interessano proprio quelle motivazioni.

la semantica è lo studio del significato a livello linguistico: il significato a livello linguistico di "downshift" e "mask" in quei sorgenti è semplicemente l'essere campi di una struct, nonché successivamente l'essere usati come operandi in operazioni di shift a destra e bitwise and, rispettivamente.

se vuoi sapere le motivazioni matematiche dell'algoritmo la richiesta che fai è pragmatica, non semantica.

aldilà di questo una funzione di hashing solitamente si progetta in base al caso specifico in maniera tale da evitare collisioni, ovvero in maniera tale da prelevare dal singolo elemento solo la parte di informazione non ridondante. per capire il significato di quella particolare funzione di hash devi conoscere le proprietà del dominio su cui essa lavora, oppure le puoi dedurre facendo reverse engineering.

tutto quello che riesco a dedurre io è che dati quei numeri, per ottenere un'informazione statisticamente non ridondante devi moltiplicarli per il numeraccio, shiftarli e AND-arli. non è molto d'aiuto, ti pare?

visto che hai a disposizione i sorgenti sarebbe molto meglio lavorare in maniera più naturale cercando prima di capire quali peculiarità ha il dominio della funzione.

[mjordan]

Cancello tutto quello che avevo scritto, non ho proprio voglia. Avanti il prossimo.

EDIT: Comunque mi rispondo da solo, variante dell'algoritmo djb2 per hashing digitale.

[71104]

Originariamente inviato da mjordan

Cancello tutto quello che avevo scritto, non ho proprio voglia. Avanti il prossimo.

mavalà, hai postato direttamente questa frase
non appare nemmeno la scrittina in corsivo "modificato da mjordan alle ecc. ecc."

EDIT - ecco vedi, ora appare