7 - Eleccion del tamano de la tabla y load factor

Dimensionar la tabla

Escoger el tamano correcto de la tabla hash es tan critico como elegir la funcion hash. El factor de carga alpha = n / m (elementos sobre buckets) determina la probabilidad de colision y, con ello, el costo promedio de insercion y busqueda. Un plan de rehashing mantiene el rendimiento cuando la tabla crece.

7.1 Eleccion de numeros primos

Para open addressing es comun elegir capacidades primas, porque facilitan recorrer todas las celdas con doble hashing y reducen patrones de colision. En encadenamiento no es obligatorio, pero un primo cercano al doble del numero esperado de elementos dispersa mejor.

7.2 Load factor α = n / m

• Encadenamiento: suele tolerar alpha hasta 1.0 (una colision promedio por bucket); algunos diseños van hasta 2.0 si las listas son cortas.
• Open addressing: rehash tipicamente al superar 0.6-0.75; mas colisiones implican sondas largas y clustering.

Mantener alpha acotado preserva el tiempo promedio O(1). Si crece, la tabla se vuelve mas lenta y debe ampliarse.

7.3 Cuándo rehashing es obligatorio

• Cuando alpha supera el umbral definido (ej. 0.7 en open addressing, 1.0 en chaining).
• Si el tiempo promedio de busqueda aumenta visiblemente por listas largas o sondas extensas.
• Al detectar mucho clustering o buckets desbalanceados.

7.4 Rehashing: como duplicar la tabla

El rehash crea una tabla mas grande y reinsertar todos los pares clave-valor con la misma funcion hash (o una nueva). El paso es O(n) pero se realiza esporadicamente.

typedef struct {
  const char *clave;
  int valor;
} Par;

Par *rehash(Par *tabla, size_t viejo_tam, size_t *nuevo_tam) {
  size_t tam = (*nuevo_tam) * 2 + 1; /* siguiente primo aproximado */
  Par *nueva = calloc(tam, sizeof(Par));
  for (size_t i = 0; i < viejo_tam; i++) {
    if (tabla[i].clave == NULL) continue;
    size_t idx = hash(tabla[i].clave) % tam;
    while (nueva[idx].clave != NULL) {
      idx = (idx + 1) % tam; /* probing lineal para simplificar */
    }
    nueva[idx] = tabla[i];
  }
  free(tabla);
  *nuevo_tam = tam;
  return nueva;
}

La operacion reinserta los pares para alinearlos con el nuevo modulo. En open addressing es obligatorio; en encadenamiento tambien mejora la longitud promedio de las listas.

7.5 Impacto en rendimiento

• Coste amortizado: rehashing es O(n) pero se distribuye; mantener alpha estable conserva O(1) promedio.
• Memoria: duplicar la tabla requiere memoria temporal para la nueva estructura.
• Cache: tablas mas grandes pueden impactar la localidad; open addressing se beneficia de arrays contiguos aun tras el rehash.

7.6 Ejemplos practicos

Como regla general, define un umbral, mide alpha en cada insercion y dispara el rehash antes de que el rendimiento se degrade.