Tabla Hash en C: Inserción y Redimensionado Dinámico
Definición de la estructura
struct tabla_hash {
int num_listas;
int num_elementos;
double densidad_max; //en porcentaje
struct nodo **tabla;
};
-----------------------------------------------------------
struct tabla_hash datos;
inicializa(&datos, 10, 25);
inserta_elemento(&datos, 5);
--------------------------------------------------------------
Funciones
Inicialización de la tabla
void inicializa(struct tabla_hash *datos, int num_listas, double densidad_max){
datos->num_listas = num_listas;
datos->num_elementos = 0;
datos->densidad_max = densidad_max;
datos->tabla = (struct nodo **) calloc(num_listas, sizeof(struct nodo *));
}
------------------------------------------------------------------
Inserción de un elemento
void inserta_elemento(struct tabla_hash *datos, int info_nueva){
struct nodo *nuevo = (struct nodo *) malloc(sizeof(struct nodo));
nuevo->sig = NULL;
nuevo->dato = info_nueva;
double densidad = ((double) (datos->num_elementos + 1)) / datos->num_listas * 100;
if (densidad >= datos->densidad_max)
redimensiono(datos);
int indice = funcion_hash(info_nueva, datos->num_listas);
nuevo->sig = datos->tabla[indice];
datos->tabla[indice] = nuevo;
}
----------------------------------------------------------------------------
Redimensionado de la tabla
void redimensiono(struct tabla_hash *datos){
int dim_antigua = datos->num_listas;
int i;
int sitio;
struct nodo *aux, *ant;
datos->num_listas = datos->num_listas * 2;
datos->tabla = realloc(datos->tabla, sizeof(struct nodo *) * datos->num_listas);
// A partir de tabla[dim_antigua] hasta tabla[num_listas_nueva - 1] hay que ponerlo a NULL porque realloc no inicializa
for (i = dim_antigua; i < datos->num_listas; i++)
datos->tabla[i] = NULL;
// Ahora toca reorganizar cada elemento de cada lista antigua para ponerlo en otro sitio en función de la nueva dimensión
for (i = 0; i < dim_antigua; i++){
aux = datos->tabla[i];
ant = datos->tabla[i];
while (aux != NULL){
while ((aux != NULL) && ((sitio = funcion_hash(aux->dato, datos->num_listas)) == i)){
ant = aux;
aux = aux->sig;
}
if (aux != NULL){
if (aux == ant){ // inicio de la lista
datos->tabla[i] = datos->tabla[i]->sig;
ant = datos->tabla[i];
} else {
ant->sig = aux->sig;
}
aux->sig = datos->tabla[sitio];
datos->tabla[sitio] = aux;
aux = ant->sig;
} // cierra el if (aux != NULL)
} // cierra el while (aux != NULL)
} // cierra el for
} // cierra la función
