Cómo crear una tabla hash

Question

Me gustaría mencionar antes de continuar que he visto otras preguntas que hacen lo mismo en este sitio y en otros sitios. Espero que pueda obtener una buena respuesta, porque mi objetivo es doble:

1. En primer lugar, me gustaría aprender a crear una tabla hash.
2. En segundo lugar, encuentro que muchas respuestas en Stack Overflow tienden a asumir un cierto nivel de conocimiento sobre un tema que a menudo no está presente, especialmente para los tipos más nuevos. Dicho esto, espero editar mi mensaje principal para incluir una explicación del proceso un poco más en profundidad una vez que lo descubra.

---

Sobre el plato principal:

Como yo los entiendo hasta ahora, una tabla hash es una serie de listas (o una estructura de datos similar) que se espera, de manera óptima, tiene el menor número de colisiones como sea posible para preservar su elogiada complejidad O (1). La siguiente es mi proceso actual:

Así que mi primer paso es crear una matriz de punteros:

Elem ** table; 
table = new Elem*[size];//size is the desired size of the array 

Mi segundo paso es crear una función hash (muy simple).

int hashed = 0; 
hashed = (atoi(name.c_str()) + id) % size; 
//name is a std string, and id is a large integer. Size is the size of the array. 

Mi tercer paso sería crear algo para detectar colisiones, que es la parte que estoy actualmente.

He aquí algunos pseudo-código:

while(table[hashedValue] != empty) 
    hashedValue++ 

else 
    put in the list at that index. 

Es relativamente poco elegante, pero todavía estoy en el "qué es este" escenario. Tengan paciencia conmigo.

¿Hay algo más? ¿Perdí algo o hice algo incorrectamente?

Gracias

Answer 1

manija al no encontrar espacios vacíos y cambiar el tamaño de la tabla.

Answer 2

Se está faltando una definición para Elem. Eso no es trivial, ya que depende de si desea chaining o una tabla hash de sondeo.

Answer 3

Una función hash produce el mismo valor para los mismos datos. Sin embargo, su prueba de colisión modifica ese valor, lo que significa que el valor hash no solo depende de la entrada, sino también de la presencia de otros elementos en el mapa hash. Esto es malo, ya que casi nunca podrá acceder realmente al elemento que ingresó antes a través de su nombre, solo al iterar sobre el mapa.

En segundo lugar, su verificación de colisión es vulnerable a errores de desbordamiento/rango, ya que simplemente aumenta el valor de hash sin verificar el tamaño del mapa (aunque, como dije antes, ni siquiera debería estar haciendo esto).