6 - Direccionamiento abierto (Open Addressing)

Direccionamiento abierto

En open addressing todas las entradas viven dentro del mismo array. Si un bucket está ocupado, la estrategia de probing define la siguiente celda a inspeccionar hasta hallar un espacio libre (inserción) o la clave buscada (búsqueda/eliminación). Para sostener el tiempo promedio O(1) se necesita factor de carga bajo (usualmente < 0.7) y una función de exploración que reduzca el clustering.

En Python, este enfoque se parece a la forma en que los diccionarios y sets exploran celdas dentro del mismo arreglo. El rendimiento depende de evitar muchas sondas consecutivas, por eso conviene vigilar el factor de carga y planificar rehashing antes de saturar la tabla.

6.1 Concepto básico

Una colisión no crea una lista adicional; se recorre el propio array siguiendo una secuencia determinística. Cada intento i revisa una posición distinta hasta encontrar una celda disponible.

6.2 Búsqueda lineal (linear probing)

Explora celdas contiguas: idx = (h + i) % capacidad. Es simple y cache-friendly, pero sufre clustering primario: secuencias de ocupados crecen y atraen más colisiones.

6.3 Búsqueda cuadrática (quadratic probing)

La distancia crece cuadráticamente: idx = (h + i*i) % capacidad o (h + i*(i+1)/2) % capacidad. Dispersa mejor las colisiones cercanas y reduce el clustering primario. Requiere elegir una capacidad que garantice recorrer toda la tabla (frecuente usar números primos y reinserción al rebasar cierto factor de carga).

6.4 Doble hashing (double hashing)

Usa dos funciones: idx = (h1 + i * h2) % capacidad. El paso h2 debe ser distinto de 0 y coprimo con la capacidad (por ejemplo, h2 = 1 + (clave % (capacidad - 1))). Minimiza tanto clustering primario como secundario y distribuye mejor las sondas.

6.5 Manejo de celdas ocupadas y celdas borradas

• Vacía: nunca tuvo un elemento; detiene la búsqueda.
• Ocupada: almacena clave y valor.
• Borrada: contiene un marcador; permite continuar el probing en búsquedas, pero habilita reutilizar el espacio en inserciones.

Sin el estado "borrada" la eliminación rompería la cadena de sondas y haría inaccesibles algunas claves.

Si se acumulan muchas celdas marcadas como borradas, las búsquedas recorren más posiciones. En esos casos es recomendable rehashing para limpiar marcas y recuperar rendimiento.

6.6 Problema del clustering

Primario: secuencias contiguas crecen con linear probing. Secundario: ocurre cuando muchas claves comparten la misma secuencia de sondas (afecta linear y quadratic). Mitigación: reducir factor de carga, usar quadratic o doble hashing, y rehashing preventivo.

Una forma de monitorear el clustering es medir la cantidad promedio de sondas por operación. Si ese promedio sube, la tabla ya no está en su zona óptima.

6.7 Inserción

Se calcula el índice base, se recorre la secuencia de probing hasta encontrar una celda vacía o borrada. Si se encuentra la clave, se actualiza el valor; si no, se escribe en la primera celda disponible.

Una implementación robusta guarda la primera celda borrada y la reutiliza si no se encuentra un lugar vacío antes. También actualiza el contador de elementos para decidir cuándo rehash.

CELDA_VACIA = 0
CELDA_OCUPADA = 1
CELDA_BORRADA = 2

class Entrada:
  def __init__(self, clave=None, valor=0, estado=CELDA_VACIA):
    self.clave = clave
    self.valor = valor
    self.estado = estado


def hash1(clave, cap):
  h = 5381
  for caracter in clave:
    h = ((h << 5) + h) + ord(caracter)
  return h % cap


def hash2(clave, cap):
  h = 0
  for caracter in clave:
    h = h * 131 + ord(caracter)
  return 1 + (h % (cap - 1))


def insertar(tabla, clave, valor):
  cap = len(tabla)
  base = hash1(clave, cap)
  paso = hash2(clave, cap)
  primera_borrada = -1
  for i in range(cap):
    idx = (base + i * paso) % cap
    entrada = tabla[idx]
    if entrada.estado == CELDA_OCUPADA and entrada.clave == clave:
      entrada.valor = valor
      return True
    if entrada.estado == CELDA_BORRADA and primera_borrada == -1:
      primera_borrada = idx
    if entrada.estado == CELDA_VACIA:
      destino = primera_borrada if primera_borrada != -1 else idx
      tabla[destino] = Entrada(clave, valor, CELDA_OCUPADA)
      return True
  return False

6.8 Búsqueda

El recorrido sigue la misma secuencia usada para insertar. Se detiene al encontrar una celda vacía (la clave no está) o la coincidencia exacta.

Las celdas borradas no detienen la búsqueda: se deben saltar para no perder claves insertadas más adelante en la secuencia.

def buscar(tabla, clave):
  cap = len(tabla)
  base = hash1(clave, cap)
  paso = hash2(clave, cap)
  for i in range(cap):
    idx = (base + i * paso) % cap
    entrada = tabla[idx]
    if entrada.estado == CELDA_VACIA:
      return None
    if entrada.estado == CELDA_OCUPADA and entrada.clave == clave:
      return entrada
  return None

6.9 Eliminación

Se busca la clave y, si se encuentra, la celda se marca como borrada. No se puede marcar como vacía porque cortaría el recorrido de otras claves que colisionaron.

Si se eliminan muchos elementos, el rehashing ayuda a compactar la tabla y eliminar marcas viejas.

def eliminar(tabla, clave):
  entrada = buscar(tabla, clave)
  if not entrada:
    return False
  entrada.estado = CELDA_BORRADA
  return True

6.10 Comparación entre métodos

En la práctica: linear probing es ideal con tablas más grandes que el número esperado de elementos y lecturas frecuentes; quadratic probing evita clusters grandes con pocos cambios; doble hashing ofrece la mejor distribución a costa de dos funciones y más cuidado al elegir la capacidad.

En implementaciones reales de Python se usan variantes de open addressing con criterios de rehash y sondas optimizadas. La idea central sigue siendo la misma: mantener sondas cortas y una buena distribución.

6.11 Programa completo para probar en VSCode (open addressing con doble hashing)

Ejecuta este programa en VSCode para ver inserciones, búsquedas y eliminaciones usando direccionamiento abierto con doble hashing y manejo de celdas vacías/borradas.

CELDA_VACIA = 0
CELDA_OCUPADA = 1
CELDA_BORRADA = 2

class Entrada:
  def __init__(self, clave=None, valor=0, estado=CELDA_VACIA):
    self.clave = clave
    self.valor = valor
    self.estado = estado


class HashOA:
  def __init__(self, capacidad):
    self.capacidad = capacidad
    self.cantidad = 0
    self.celdas = [Entrada() for _ in range(capacidad)]


def hash1(clave, cap):
  h = 5381
  for caracter in clave:
    h = ((h << 5) + h) + ord(caracter)
  return h % cap


def hash2(clave, cap):
  h = 0
  for caracter in clave:
    h = h * 131 + ord(caracter)
  return 1 + (h % (cap - 1))


def hash_buscar(tabla, clave):
  base = hash1(clave, tabla.capacidad)
  paso = hash2(clave, tabla.capacidad)
  for i in range(tabla.capacidad):
    idx = (base + i * paso) % tabla.capacidad
    entrada = tabla.celdas[idx]
    if entrada.estado == CELDA_VACIA:
      return None
    if entrada.estado == CELDA_OCUPADA and entrada.clave == clave:
      return entrada
  return None


def hash_insertar(tabla, clave, valor):
  base = hash1(clave, tabla.capacidad)
  paso = hash2(clave, tabla.capacidad)
  primera_borrada = -1
  for i in range(tabla.capacidad):
    idx = (base + i * paso) % tabla.capacidad
    entrada = tabla.celdas[idx]
    if entrada.estado == CELDA_OCUPADA and entrada.clave == clave:
      entrada.valor = valor
      return True
    if entrada.estado == CELDA_BORRADA and primera_borrada == -1:
      primera_borrada = idx
    if entrada.estado == CELDA_VACIA:
      destino = primera_borrada if primera_borrada != -1 else idx
      tabla.celdas[destino] = Entrada(clave, valor, CELDA_OCUPADA)
      tabla.cantidad += 1
      return True
  return False


def hash_eliminar(tabla, clave):
  entrada = hash_buscar(tabla, clave)
  if not entrada:
    return False
  entrada.estado = CELDA_BORRADA
  tabla.cantidad -= 1
  return True


def hash_imprimir(tabla):
  for i in range(tabla.capacidad):
    entrada = tabla.celdas[i]
    if entrada.estado == CELDA_OCUPADA:
      print(f"[{i}] ({entrada.clave} -> {entrada.valor})")
    elif entrada.estado == CELDA_BORRADA:
      print(f"[{i}] ")
    else:
      print(f"[{i}] ")


if __name__ == "__main__":
  tabla = HashOA(13)
  hash_insertar(tabla, "juan", 50)
  hash_insertar(tabla, "ana", 23)
  hash_insertar(tabla, "luis", 19)
  hash_insertar(tabla, "pedro", 90)
  hash_insertar(tabla, "maria", 41)

  print("Tabla despues de insertar:")
  hash_imprimir(tabla)

  resultado = hash_buscar(tabla, "pedro")
  print("Buscar 'pedro':", "encontrado" if resultado else "no encontrado")

  hash_eliminar(tabla, "pedro")

  resultado = hash_buscar(tabla, "pedro")
  print("Buscar 'pedro' luego de borrar:", "encontrado" if resultado else "no encontrado")

  print("Tabla final:")
  hash_imprimir(tabla)

Ejecútalo y observa el probing generado por el doble hashing, incluyendo celdas marcadas como borradas para preservar la cadena de búsqueda.