7 - Elección del tamaño de la tabla y load factor

Dimensionar la tabla

Escoger el tamaño correcto de la tabla hash es tan crítico como elegir la función hash. El factor de carga alpha = n / m (elementos sobre buckets) determina la probabilidad de colisión y, con ello, el costo promedio de inserción y búsqueda. Un plan de rehashing mantiene el rendimiento cuando la tabla crece.

7.1 Elección de números primos

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

7.2 Load factor α = n / m

• Encadenamiento: suele tolerar alpha hasta 1.0 (una colisión promedio por bucket); algunos diseños van hasta 2.0 si las listas son cortas.
• Open addressing: rehash típicamente al superar 0.6-0.75; más colisiones implican sondas largas y clustering.

Mantener alpha acotado preserva el tiempo promedio O(1). Si crece, la tabla se vuelve más 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 búsqueda aumenta visiblemente por listas largas o sondas extensas.
• Al detectar mucho clustering o buckets desbalanceados.

7.4 Rehashing: cómo duplicar la tabla

El rehash crea una tabla más grande y reinserta todos los pares clave-valor con la misma función hash (o una nueva). El paso es O(n) pero se realiza esporádicamente.

def rehash(tabla, nuevo_tam):
  tam = nuevo_tam * 2 + 1  # siguiente primo aproximado
  nueva = [None] * tam
  for entrada in tabla:
    if entrada is None:
      continue
    idx = hash(entrada[0]) % tam
    while nueva[idx] is not None:
      idx = (idx + 1) % tam  # probing lineal para simplificar
    nueva[idx] = entrada
  return nueva, tam

La operación reinserta los pares para alinearlos con el nuevo módulo. En open addressing es obligatorio; en encadenamiento también mejora la longitud promedio de las listas.

7.5 Impacto en rendimiento

• Costo 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 más grandes pueden impactar la localidad; open addressing se beneficia de arrays contiguos aun tras el rehash.

7.6 Ejemplos prácticos

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