Construyendo una función hash/tabla hash

Question

Me gustaría construir una tabla hash que busque claves en secuencias (cadenas) de bytes que van de 1 a 15 bytes.

Me gustaría almacenar un valor entero, así que me imagino que una matriz para hash sería suficiente. Tengo dificultades para conceptualizar cómo construir una función hash de manera que dado que la clave daría un índice en la matriz.

Cualquier asistencia sería muy apreciada.

El número máximo de entradas en el hash es: 4.081 * 15 + 4,081 * 14 + ... 4081 = 4081 ((15 * (16))/2) = 489720.

Así, por ejemplo:

int table[489720]; 

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

¿Cuáles son algunas buenas opciones para una función hash, o cómo hago para construir uno?

Gracias.

Answer 1

Si quiere un hash perfecto, puede comenzar leyendo el artículo de Wikipedia en perfect hashing. Si te encuentras con inconvenientes, puedes pedir ayuda aquí.

Answer 2

Si el número promedio de cadenas residentes en la tabla es bajo, como menos de 10.000 entradas, una matriz asociativa sería un enfoque razonable, incluso si se utiliza una búsqueda lineal si está en una arquitectura de CPU moderna.

De lo contrario, construir un "hash perfecto" requiere inspeccionar cada carácter de la cadena y calcular un valor único basado en el rango posible. Por ejemplo, si sólo el A..Z 26 caracteres están permitidos en la clave, esto funcionaría:

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

Answer 3

Su espacio de claves es grande (aproximadamente 2^(8 * 15)), así que si quieres una hash perfecto, necesitarás saber qué 489720 claves reales se mostrarán con anticipación. Incluso entonces, es prácticamente imposible encontrar un hash perfecto para esas teclas, incluso si permites una tabla mucho más grande (por ejemplo, un factor de carga muy bajo). La única manera que conozco de encontrar un hash perfecto es por prueba y error, y es probable que falle el hash aleatorio a menos que tu tabla tenga 489720^2 entradas.

Recomiendo usar un regular (non-perfect) hash y deal with collisions appropriately, por ejemplo. con el encadenamiento:

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 
} 

también recomiendo no se implementa esto por sí mismo - utilizar una biblioteca estándar como un c++ hashmap.

Answer 4

en Hash cadenas de C, siempre he utilizado esta función (tomar el resultado% el tamaño de su tabla hash):

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

No recuerdo donde lo tengo desde un principio, pero en muchos años no me ha decepcionado.