Creazione di una tabella hash/funzione hash

Question

Vorrei costruire una tabella hash che cerchi le chiavi in ​​sequenze (stringhe) di byte che vanno da 1 a 15 byte.

Vorrei memorizzare un valore intero, quindi immagino che un array per hashing sia sufficiente. Ho difficoltà a concettualizzare come costruire una funzione di hash tale che data la chiave darebbe un indice nell'array.

Qualsiasi assistenza sarebbe molto apprezzata.

Il numero massimo di voci nella hash è: 4081 * 15 + 4081 * 14 + ... 4081 = 4081 ((15 * (16))/2) = 489720.

Così, per esempio:

int table[489720]; 

int lookup(unsigned char *key) 
{ 
    int index = hash(key); 
    return table[index]; 
} 

Quali sono alcune buone scelte per una funzione di hash, o come dovrei fare per costruirne una?

Grazie.

Answer 1

Se si desidera un hash perfetto, è possibile iniziare leggendo l'articolo di Wikipedia su perfect hashing. Se incappi in ostacoli, puoi chiedere aiuto qui.

Answer 2

Se il numero medio di stringhe residenti nella tabella è basso, come in 10.000 voci, un array associativo sarebbe un approccio ragionevole, anche utilizzando una ricerca lineare se si trova su una moderna architettura CPU.

Altrimenti, la costruzione di un "hash perfetto" richiede l'ispezione di ciascun carattere della stringa e il calcolo di un valore univoco basato sull'intervallo possibile. Ad esempio, se solo l'A..Z 26 caratteri sono ammessi nella chiave, questo dovrebbe funzionare:

int 
hash (const char *key) 
{ 
    int h = 0; 
    while (key && *key) 
     h = h * 26 + (*key++ - 'A'); 
    return h; 
} 

Answer 3

Spazio chiave è di grandi dimensioni (circa 2^(8 * 15)), quindi se volete un perfetto hash, è necessario sapere quali 489720 chiavi effettive verranno visualizzate in anticipo. Anche allora, è praticamente impossibile trovare un hash perfetto per quelle chiavi, anche se hai permesso un tavolo molto più grande (a.k.a un fattore di carico molto basso). L'unico modo che conosco per trovare un hash perfetto è per tentativi ed errori, ed è probabile che un hash casuale fallisca a meno che la tua tabella non sia vicina a 489720^2 voci.

Consiglio vivamente di utilizzare uno regular (non-perfect) hash e deal with collisions appropriately, ad es. con concatenamento:

struct entry { 
    unsigned char *key; 
    int value; 
    struct entry *next; 
} *table[1<<20]; 
int lookup(unsigned char *key) { 
    int index = hash(key) % (1<<20); 
    for (struct entry *e = table[index]; e != NULL; e = e->next) { 
    if (!strcmp(key, e->key)) return e->value; 
    } 
    // not found 
} 

Raccomando anche non implementare da soli - utilizzare una libreria standard come un c++ hashmap.

Answer 4

Hash stringhe C, ho usato sempre questa funzione (prendere il risultato% dimensione della vostra tabella di hash):

int hashstring(const char* s) { 
    int key = 0; 
    while (*s) { 
    key = key*37 + *s++; 
    } 
    return key; 
} 

Non mi ricordo dove l'ho preso dal inizialmente, ma in molti anni non mi ha deluso.