El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia

HOME

La TablaHashIngenua de la lección anterior nos dio el O(1)... y perdió la tarea 3 en cuanto el id 11 aterrizó en su casilla. Esta lección repara esa herida en dos frentes. Primero, el frente preventivo: entender qué hace buena a una función hash, porque una función bien diseñada reparte las claves y hace las colisiones raras. Segundo, el frente curativo: aceptar que raras no significa imposibles (lo demostraremos), y construir una tabla que las resuelva sin perder ni un dato. El resultado será la TablaHash definitiva del curso — con encadenamiento, factor de carga y redimensionado —, la pieza que TaskFlow necesitaba para que su índice id→tarea sea de fiar. Es la lección más de "taller de ingeniería" del módulo: aquí se ve cómo se diseña de verdad una estructura de datos profesional.

Contenido

Qué le pedimos a una función hash
Hash de enteros y hash de cadenas: una mala y una buena
Midiendo la diferencia: el histograma
Las colisiones son inevitables: el principio del palomar
Estrategia curativa 1: encadenamiento
La clase TablaHash completa
Factor de carga y redimensionado (rehashing)
Estrategia curativa 2: direccionamiento abierto
Encadenamiento vs direccionamiento abierto
El peor caso O(n), explicado de verdad

Qué le pedimos a una función hash

Una función hash h(clave) → entero es apta para una tabla si cumple tres propiedades, por orden de importancia:

Determinista: la misma clave produce siempre el mismo hash (dentro de la misma ejecución). Es innegociable: guardar y buscar usan el mismo cálculo, así que si h cambiara de opinión, guardaríamos en una casilla y buscaríamos en otra. Una función hash que use random o la hora actual no es una función hash: es un generador de datos perdidos.
Uniforme: los hashes deben repartirse por todo el rango como si fueran aleatorios, sin serlo. Si la función favorece ciertas zonas, las claves se amontonan en pocas casillas y el O(1) promedio se erosiona hacia el O(n). Esta es la propiedad difícil, y la que separa una función buena de una mala.
Rápida: se ejecuta en cada insertar, obtener, borrar y contiene. Una función hash de coste alto grava cada operación de la tabla; O(longitud de la clave) es el estándar.

Hay una tensión estética curiosa: queremos un resultado que parezca caótico (uniformidad) producido por un proceso totalmente predecible (determinismo). Diseñar buenas funciones hash es el arte de fabricar caos reproducible.

Hash de enteros y hash de cadenas: una mala y una buena

Enteros: el caso fácil. hash(n) == n para enteros pequeños en Python, y suele bastar: los ids de TaskFlow (1, 2, 3...) se reparten perfectamente con % capacidad. La uniformidad la hereda de las propias claves — con la letra pequeña de que claves con patrón (todos los ids múltiplos de 8, por ejemplo) pueden resonar mal con ciertas capacidades; volveremos a esto en los consejos.

Cadenas: aquí hay que trabajar. Una cadena es una secuencia de caracteres, y cada carácter tiene un código entero (ord("a") es 97). La tentación inmediata es sumarlos:

def hash_suma(texto):
    """Función hash MALA: suma los códigos de los caracteres."""
    return sum(ord(c) for c in texto)

Es determinista y rápida... pero fatalmente no uniforme, por un defecto estructural: la suma ignora el orden. hash_suma("amor") y hash_suma("roma") son idénticos — todas las permutaciones de las mismas letras colisionan siempre, con cualquier capacidad. Y hay un segundo defecto más sutil: claves de longitud parecida producen sumas parecidas, apelotonadas en una franja estrecha de valores.

La solución clásica es el hash polinómico: recorrer los caracteres acumulando, pero multiplicando el acumulador por una constante en cada paso, de modo que la posición importe:

def hash_poli(texto, base=31):
    """Función hash razonable: polinómica. h = c0·31^(n-1) + c1·31^(n-2) + ... + cn"""
    h = 0
    for c in texto:
        h = (h * base + ord(c)) % (2 ** 32)   # acotamos a 32 bits
    return h

Desmenucemos por qué funciona:

Cada carácter queda multiplicado por una potencia distinta de 31 según su posición: el primer carácter pesa 31^(n-1), el último pesa 1. Reordenar los caracteres cambia el resultado — adiós al problema de los anagramas.
La multiplicación reiterada hace que un cambio en un solo carácter se propague y altere el resultado de forma aparentemente caótica (el "caos reproducible" que buscábamos). Se eligen bases primas como 31 o 131 porque mezclan bien y no comparten factores con capacidades habituales.
El % (2 ** 32) mantiene el número en 32 bits para que no crezca sin límite; es un detalle de contención, no de diseño.

Este esquema no es un juguete académico: el hash de las cadenas en Java es exactamente un polinómico con base 31. CPython usa algo más blindado (SipHash, con la aleatorización entre ejecuciones que vimos en 05-01), pero la idea de fondo — mezclar posición y valor — es la misma.

Midiendo la diferencia: el histograma

Las palabras "uniforme" y "apelotonada" se entienden mejor viéndolas. Tomemos 100 claves con estructura realista — los ids textuales "T-001" a "T-100" de las tareas de TaskFlow — y repartámoslas en 20 cubetas con cada función, contando cuántas caen en cada una:

claves = [f"T-{i:03d}" for i in range(1, 101)]     # T-001 .. T-100
CAPACIDAD = 20

def histograma(funcion_hash, nombre):
    cubetas = [0] * CAPACIDAD
    for clave in claves:
        cubetas[funcion_hash(clave) % CAPACIDAD] += 1
    print(f"--- {nombre} ---")
    for i, n in enumerate(cubetas):
        print(f"{i:2} | {'#' * n} ({n})")

histograma(hash_suma, "hash_suma")
histograma(hash_poli, "hash_poli")

Salida (recortada a las cubetas más ilustrativas):

--- hash_suma ---
 1 | ######### (9)
 2 | ########## (10)
 3 | ######### (9)
 ...
10 | ## (2)
11 | # (1)
12 |  (0)
13 |  (0)
...
--- hash_poli ---
 3 | ##### (5)
 4 | ###### (6)
 5 | ###### (6)
 6 | ##### (5)
 7 | ###### (6)
 ...

El veredicto es visual: con hash_suma, el reparto es una montaña — cubetas con 10 claves al lado de dos cubetas vacías (las sumas de estas claves se concentran en una franja, y el % 20 dibuja esa franja en la tabla). Con hash_poli, todas las cubetas tienen entre 4 y 6 claves: prácticamente el ideal de 100/20 = 5. Y el defecto de los anagramas, negro sobre blanco:

print(hash_suma("T-012"), hash_suma("T-021"), hash_suma("T-102"))
# 276 276 276   ← colisión garantizada, da igual la capacidad
print(hash_poli("T-012"), hash_poli("T-021"), hash_poli("T-102"))
# 78964056 78964086 78964986   ← tres valores distintos

En una tabla con hash_suma, buscar en la cubeta de 10 claves cuesta el doble que el promedio ideal, y las cubetas vacías son capacidad desperdiciada. La uniformidad no es una virtud abstracta: es tiempo de ejecución.

Las colisiones son inevitables: el principio del palomar

¿Y si diseñáramos una función hash tan buena que nunca colisionara? Imposible, y la demostración cabe en dos líneas. El principio del palomar: si n palomas se reparten en m nidos y n > m, algún nido tiene al menos dos palomas. Con claves y casillas: una tabla de capacidad 64 con 65 claves tiene, con matemática certeza, al menos una colisión — da igual lo exquisita que sea la función. Las claves posibles (todos los enteros, todas las cadenas) siempre superan infinitamente a las casillas disponibles.

Y la realidad es aún más impaciente: no hace falta llenar la tabla para colisionar. Es la paradoja del cumpleaños: igual que en una sala con solo 23 personas ya hay un 50% de probabilidad de dos cumpleaños coincidentes (¡con 365 "casillas"!), en una tabla de capacidad 365 basta insertar unas 23 claves aleatorias para que la primera colisión sea más probable que improbable. Conclusión operativa: la pregunta nunca es "¿habrá colisiones?" sino "¿qué haremos cuando lleguen?". Hay dos grandes respuestas; vamos con la principal.

Estrategia curativa 1: encadenamiento

El encadenamiento (chaining) disuelve el problema cambiando qué es una casilla: en vez de sitio para un par, cada casilla es una cubeta que contiene una colección de pares — todos los que el hash mande allí. ¿Y qué estructura usar para esa colección de tamaño variable, con inserción O(1) y borrado por predicado? La tenemos construida y probada desde el módulo 2: la ListaEnlazada.

graph LR
    subgraph "Array de cubetas (capacidad 8)"
        C0["0"] --> N
        C3["3"] --> A["(3, tarea 3)"] --> B["(11, tarea 11)"] --> N3["None"]
        C5["5"] --> D["(5, tarea 5)"] --> N5["None"]
    end
    N["None"]

La colisión de 05-01 deja de ser una tragedia: las claves 3 y 11 comparten cubeta, cada una con su par intacto. Buscar la clave 3 es: calcular la cubeta (O(1)) y recorrer su pequeña lista comparando claves (O(longitud de la cubeta)). Si la función hash reparte bien, esa longitud media es n / capacidad — un número pequeño y controlado, como veremos con el factor de carga.

La clase `TablaHash` completa

Reutilizamos Nodo y ListaEnlazada tal cual quedaron en 02-02 (con insertar_al_inicio, buscar(condicion), borrar(condicion) e iteración). Cada cubeta guardará pares como listas [clave, valor] — mutables a propósito, para poder actualizar el valor sin tocar la estructura:

class TablaHash:
    """Diccionario clave→valor con encadenamiento. La tabla 'de verdad' del curso."""

    FACTOR_CARGA_MAX = 0.75          # umbral de redimensionado (sección 7)

    def __init__(self, capacidad=8):
        self.capacidad = capacidad
        self.cubetas = [ListaEnlazada() for _ in range(capacidad)]
        self.n = 0                   # pares almacenados

    def _indice(self, clave):
        return hash(clave) % self.capacidad

    def insertar(self, clave, valor):
        """Inserta o actualiza. Coste promedio: O(1)."""
        cubeta = self.cubetas[self._indice(clave)]
        par = cubeta.buscar(lambda p: p[0] == clave)
        if par is not None:
            par[1] = valor                        # la clave existía: actualizar
            return
        cubeta.insertar_al_inicio([clave, valor]) # nueva: O(1) en la lista
        self.n += 1
        if self.n / self.capacidad > self.FACTOR_CARGA_MAX:
            self._redimensionar()

    def obtener(self, clave, por_defecto=None):
        """Coste promedio: O(1) — una cubeta corta, no toda la tabla."""
        par = self.cubetas[self._indice(clave)].buscar(lambda p: p[0] == clave)
        return par[1] if par is not None else por_defecto

    def contiene(self, clave):
        par = self.cubetas[self._indice(clave)].buscar(lambda p: p[0] == clave)
        return par is not None

    def borrar(self, clave):
        """Borra el par y devuelve su valor, o None si no estaba."""
        par = self.cubetas[self._indice(clave)].borrar(lambda p: p[0] == clave)
        if par is None:
            return None
        self.n -= 1
        return par[1]

    def __len__(self):
        return self.n

    def _redimensionar(self):
        """Duplica la capacidad y recoloca TODOS los pares (rehashing)."""
        antiguas = self.cubetas
        self.capacidad *= 2
        self.cubetas = [ListaEnlazada() for _ in range(self.capacidad)]
        self.n = 0
        for cubeta in antiguas:
            for clave, valor in cubeta:          # __iter__ de la ListaEnlazada
                self.insertar(clave, valor)      # se recalcula con la nueva capacidad

Puntos que merecen lupa:

insertar primero busca: si la clave ya existe, actualiza el valor dentro del par (par[1] = valor) y no toca self.n. Así se cumple el contrato de claves únicas del TDA. Solo si es nueva se inserta — al inicio de la cubeta, que en la ListaEnlazada es O(1).
Todas las operaciones repiten el mismo patrón: traducir la clave a cubeta (O(1)) y delegar en la lista enlazada del módulo 2 (buscar o borrar por predicado p[0] == clave). El trabajo O(n) que aquellos métodos hacían sobre la lista entera aquí se hace sobre una cubeta de 2 o 3 elementos: mismo código, otro mundo.
Nada se pierde jamás: repite el experimento fatal de 05-01 (insertar(3, t3), insertar(11, t11)) y verás que obtener(3) y obtener(11) devuelven cada uno su tarea. La cubeta 3 simplemente tiene dos pares.

Factor de carga y redimensionado (rehashing)

El encadenamiento tiene un enemigo lento: la ocupación. Si en una tabla de 8 cubetas insertamos 800 pares, cada cubeta tendrá ~100 — y cada obtener recorrerá una lista de 100. Formalicémoslo con el factor de carga:

factor de carga = n / capacidad     (pares almacenados / cubetas)

Es exactamente la longitud media de cubeta. Con factor 0.75, la cubeta media tiene menos de un par; con factor 100, la tabla es una lista enlazada disfrazada. La defensa es vigilarlo y, al superar un umbral (nuestro FACTOR_CARGA_MAX = 0.75, similar al de las tablas reales), redimensionar: duplicar la capacidad y reinsertar todos los pares.

¿Por qué reinsertar en vez de copiar las cubetas? Porque el índice de cada clave depende de la capacidad: hash(11) % 8 = 3, pero hash(11) % 16 = 11. Al cambiar la capacidad, todas las direcciones caducan y hay que recalcularlas — eso es el rehashing (ya lo intuiste en el ejercicio 1 de 05-01). Dos matices de coste:

Un redimensionado concreto cuesta O(n): toca recolocarlo todo. La operación de inserción que lo dispara es, puntualmente, cara.
Pero duplicar la capacidad (en vez de sumarle un poco) espacia los redimensionados exponencialmente: para llegar a n pares se han pagado redimensionados de n/2 + n/4 + n/8 + ... < n reinserciones en total. Repartido entre las n inserciones, sale a O(1) amortizado por inserción — el mismo argumento del array dinámico que vimos con la list en 01-05. La simetría no es casual: la tabla hash es un array por debajo, y hereda sus trucos.

Estrategia curativa 2: direccionamiento abierto

La segunda familia de soluciones prescinde de listas: todo vive dentro del propio array, un par por casilla. En el direccionamiento abierto, si la casilla calculada está ocupada por otra clave, se busca alojamiento en una casilla alternativa siguiendo una regla fija. La regla más simple es el sondeo lineal (linear probing): probar la siguiente casilla, y la siguiente, avanzando circularmente ((i + 1) % capacidad, la aritmética de la ColaCircular de 04-03) hasta encontrar hueco.

Insertar 11 cuando la casilla 3 está ocupada por la clave 3: probar la 4; ¿libre? el par se queda allí.
Buscar 11: calcular casilla 3; hay un par pero de otra clave → seguir a la 4; clave 11 → encontrada. La búsqueda recorre la misma senda que la inserción y solo puede detenerse al encontrar la clave... o una casilla vacía (si estuviera, habría aparecido antes del primer hueco).
Borrar, y aquí está la trampa fina: si borramos la clave 3 dejando su casilla vacía, la búsqueda de 11 llegará a la casilla 3, verá el hueco y concluirá — erróneamente — que 11 no existe, porque el hueco corta la senda. La solución estándar es no vaciar, sino dejar una marca especial (DELETED, una "lápida"): la búsqueda la atraviesa como ocupada, la inserción puede reutilizarla como libre.

No implementaremos esta variante en detalle (el concepto es lo exigible aquí; con encadenamiento ya tenemos nuestra tabla de trabajo), pero sí su idea-problema característica: el agrupamiento primario. Las casillas ocupadas consecutivas forman "atascos" que crecen — cada colisión que cae en el atasco lo alarga, y alargarlo hace más probable recibir la siguiente. Por eso el direccionamiento abierto es más sensible al factor de carga y suele redimensionar antes (típicamente hacia 0.5–0.7; el dict de CPython, que usa una variante sofisticada de esta familia, redimensiona a 2/3).

Encadenamiento vs direccionamiento abierto

Criterio	Encadenamiento	Direccionamiento abierto
Dónde viven los pares	En listas fuera del array (cubetas)	Dentro del propio array
Colisión	Se añade a la cubeta	Se sondea otra casilla
Borrado	Sencillo (borrar de la lista)	Delicado: exige marcas `DELETED`
Factor de carga tolerable	Puede superar 1 (cubetas de varios pares)	Debe quedar por debajo de 1, con margen
Memoria	Punteros extra por nodo	Compacta y amigable con la caché de la CPU
Riesgo característico	Cubetas largas si el hash es malo	Agrupamiento primario (atascos)
Quién la usa	Java `HashMap`, nuestra `TablaHash`	CPython `dict`/`set` (variante avanzada)

Ambas familias sostienen software de producción; el encadenamiento es más didáctico y robusto frente a cargas altas, el direccionamiento abierto exprime mejor la memoria moderna. Para el curso, nuestra TablaHash de encadenamiento es la referencia.

El peor caso O(n), explicado de verdad

Ya podemos saldar la deuda de la tabla de costes de 05-01. El peor caso O(n) ocurre cuando todas las claves acaban en la misma cubeta (o en el mismo atasco, en direccionamiento abierto): la tabla degenera en una lista enlazada y cada operación la recorre entera. ¿Cómo se llega ahí?

Función hash mala: hash_suma con claves anagramáticas, o cualquier función que resuene con el patrón de las claves. Es el caso evitable — de ahí la mitad "preventiva" de esta lección.
Mala suerte extrema: posible, astronómicamente improbable con una función uniforme. El análisis probabilístico dice que, con hash uniforme y factor de carga acotado, la cubeta media tiene O(1) pares — por eso el promedio O(1) es una promesa sólida y no publicidad engañosa.
Mala fe: un atacante que conoce la función hash puede fabricar miles de claves colisionantes y convertir cada petición en O(n) (ataque hash flooding, un clásico de denegación de servicio contra servidores web). Esta es la razón de que Python aleatorice el hash de las cadenas en cada ejecución (la nota de 05-01): sin conocer la semilla, no se pueden fabricar colisiones a medida.

La ingeniería completa, en una línea: buena función hash + factor de carga vigilado + redimensionado = O(1) promedio con peor caso O(n) confinado a lo improbable o lo malicioso.

Errores Comunes y Consejos

Olvidar el caso "la clave ya existe" en insertar: añadir sin buscar primero crea claves duplicadas dentro de la cubeta; obtener encontrará una versión u otra según el orden y borrar eliminará solo una. Es el error número uno al implementar encadenamiento.
Redimensionar copiando cubetas en vez de rehashing: si al ampliar copias las listas tal cual, las claves quedan en cubetas calculadas con la capacidad antigua y la tabla "pierde" pares (están, pero _indice ya no apunta a ellos). Todo redimensionado es una reinserción.
Actualizar self.n a destiempo: incrementarlo al actualizar un valor existente, u olvidar decrementarlo al borrar, corrompe el factor de carga — y con él, la política de redimensionado. n cuenta pares, no llamadas.
En direccionamiento abierto, borrar dejando hueco: rompe las sendas de búsqueda de las claves que sondearon por encima. Si algún día lo implementas, la lápida DELETED no es opcional.
Capacidades con mal encaje: con claves enteras con patrón (ids múltiplos de 4) y capacidad potencia de 2, % capacidad solo mira los bits bajos y media tabla queda vacía. Las capacidades primas (como el 13 o el 20 elegidos a conciencia en los ejemplos) o un hash que mezcle bits evitan la resonancia. CPython resuelve esto mezclando; nuestro hash polinómico, también.
Consejo: cuando una tabla hash "vaya lenta", imprime su histograma de ocupación como el de la sección 3. Es la radiografía que distingue en segundos una función hash enferma de un factor de carga desbocado.

Ejercicios

Diagnóstico de anagramas. Sin ejecutar código: ¿en qué cubeta caerán "T-123", "T-132", "T-213", "T-231", "T-312" y "T-321" con hash_suma y capacidad 20? ¿Y garantiza hash_poli que no colisionen? Justifica ambas respuestas con las propiedades de la sección 1.
Sondeo lineal sobre papel. Tabla de direccionamiento abierto, capacidad 7, claves enteras (hash(n) == n). Partiendo de la tabla vacía, traza casilla a casilla: insertar(10), insertar(17), insertar(3), borrar(10) y después contiene(17). Hazlo dos veces: borrando con hueco (None) y borrando con lápida (DELETED). ¿Qué responde contiene(17) en cada caso?
El factor de carga, medido. Añade a TablaHash el método longitud_maxima_cubeta() que devuelva la longitud de la cubeta más larga (usa len(cubeta), que la ListaEnlazada ya ofrece). Inserta los pares (i, i) para i de 0 a 999 en dos tablas de capacidad inicial 8: una normal y otra con FACTOR_CARGA_MAX = float("inf") (redimensionado desactivado). Compara capacidad, factor de carga y cubeta máxima de ambas.

Soluciones

Ejercicio 1. Las seis claves son permutaciones de los mismos caracteres, y la suma no depende del orden: todas tienen hash_suma = ord("T") + ord("-") + ord("1") + ord("2") + ord("3") = 84 + 45 + 49 + 50 + 51 = 279, luego todas caen en la cubeta 279 % 20 = 19. Seis claves, una cubeta: buscar cualquiera de ellas cuesta hasta 6 comparaciones. Con hash_poli el orden pesa (cada carácter va multiplicado por una potencia de 31 distinta), así que estas seis en concreto reciben hashes distintos — pero no hay garantía general: el principio del palomar sigue vigente y hash_poli también colisiona para algunos pares de claves. La diferencia es estadística, no absoluta: la buena función hace las colisiones raras y sin patrón explotable; la mala las fabrica en serie.

Ejercicio 2. Trazado común: insertar(10) → 10 % 7 = 3, casilla 3 libre → se queda en la 3. insertar(17) → 17 % 7 = 3, ocupada (10) → sondeo a la 4, libre → 4. insertar(3) → 3 % 7 = 3, ocupada (10) → 4 ocupada (17) → 5 libre → 5. Estado: [_, _, _, 10, 17, 3, _] — un atasco de tres casillas nacido de una sola colisión: agrupamiento primario en miniatura.

Borrado con hueco: la casilla 3 queda None. contiene(17) → calcula 3, ve None, responde False: la clave 17 está en la casilla 4, pero el hueco cortó la senda. La tabla acaba de mentir.
Borrado con lápida: la casilla 3 queda DELETED. contiene(17) → casilla 3 es lápida, la atraviesa → casilla 4, clave 17 → responde True. La lápida preserva la senda; una inserción futura podrá reutilizar la casilla 3.

Ejercicio 3.

    def longitud_maxima_cubeta(self):
        return max(len(cubeta) for cubeta in self.cubetas)

normal = TablaHash(capacidad=8)
congelada = TablaHash(capacidad=8)
congelada.FACTOR_CARGA_MAX = float("inf")     # desactiva el redimensionado

for i in range(1000):
    normal.insertar(i, i)
    congelada.insertar(i, i)

print(normal.capacidad, len(normal) / normal.capacidad,
      normal.longitud_maxima_cubeta())        # 2048  0.488  1
print(congelada.capacidad, len(congelada) / congelada.capacidad,
      congelada.longitud_maxima_cubeta())     # 8     125.0  125

La tabla normal ha ido duplicando hasta capacidad 2048: factor de carga ~0.49 y cubetas de a lo sumo 1 par (claves enteras consecutivas: reparto perfecto) — obtener es una comparación. La congelada mantiene 8 cubetas con 125 pares cada una: cada obtener recorre hasta 125 nodos. Misma función hash, mismas claves; la única diferencia es la política de redimensionado. El O(1) promedio no es un regalo de las matemáticas: es factor de carga mantenido a raya.

Conclusión

Esta lección ha convertido la idea frágil de 05-01 en una estructura de producción. En el frente preventivo: una función hash debe ser determinista, uniforme y rápida; el hash polinómico logra la uniformidad haciendo que la posición de cada carácter importe, y el histograma nos dio una herramienta para ver la calidad de un hash. En el frente curativo: el principio del palomar garantiza colisiones, el encadenamiento las resuelve dando a cada cubeta una ListaEnlazada (el módulo 2 trabajando por dentro del módulo 5), y el factor de carga con redimensionado por duplicación mantiene las cubetas cortas a coste O(1) amortizado — con el direccionamiento abierto y sus lápidas como familia alternativa. Resultado: la TablaHash con insertar/obtener/borrar/contiene en O(1) promedio, peor caso O(n) explicado y confinado. Ahora bien: en el día a día no programarás tu tabla — Python trae dos de calidad industrial, dict y set, y ahora ya sabes exactamente qué hay bajo su capó. La próxima lección los explota a fondo: claves hashables, costes reales, y los patrones (agrupar, contar, indexar) que harán volar a TaskFlow. Nos vemos en 05-03.

Funciones Hash y Resolución de Colisiones

Contenido

Qué le pedimos a una función hash

Hash de enteros y hash de cadenas: una mala y una buena

Midiendo la diferencia: el histograma

Las colisiones son inevitables: el principio del palomar

Estrategia curativa 1: encadenamiento

La clase `TablaHash` completa

Factor de carga y redimensionado (rehashing)

Estrategia curativa 2: direccionamiento abierto

Encadenamiento vs direccionamiento abierto

El peor caso O(n), explicado de verdad

Errores Comunes y Consejos

Ejercicios

Soluciones

Conclusión

Curso de Estructuras de Datos

Módulo 1: Introducción a las Estructuras de Datos

Módulo 2: Listas

Módulo 3: Pilas

Módulo 4: Colas

Módulo 5: Tablas Hash y Diccionarios

Módulo 6: Árboles

Módulo 7: Grafos

Módulo 8: Conclusiones y Recursos Adicionales

Funciones Hash y Resolución de Colisiones

Contenido

Qué le pedimos a una función hash

Hash de enteros y hash de cadenas: una mala y una buena

Midiendo la diferencia: el histograma

Las colisiones son inevitables: el principio del palomar

Estrategia curativa 1: encadenamiento

La clase TablaHash completa

Factor de carga y redimensionado (rehashing)

Estrategia curativa 2: direccionamiento abierto

Encadenamiento vs direccionamiento abierto

El peor caso O(n), explicado de verdad

Errores Comunes y Consejos

Ejercicios

Soluciones

Conclusión

Curso de Estructuras de Datos

Módulo 1: Introducción a las Estructuras de Datos

Módulo 2: Listas

Módulo 3: Pilas

Módulo 4: Colas

Módulo 5: Tablas Hash y Diccionarios

Módulo 6: Árboles

Módulo 7: Grafos

Módulo 8: Conclusiones y Recursos Adicionales

La clase `TablaHash` completa