Tablas hash
Mapa conceptual
- Estructuras de Datos
- Lineales
- Arrays
- Listas enlazadas
- Pilas y Colas
- No lineales
- Arboles BST
- Heaps
- Grafos
- Hash
- Funcion hash
- Colisiones
- Rehashing
- Algoritmos
- Ordenamiento
- Busqueda binaria
- BFS DFS
- Optimizacion
- Big-O
- Dinamica
- Voracidad
- Lineales
Cómo funciona
- Una función hash toma la clave y la reduce a un número (un entero).
- Ese número módulo la capacidad de la tabla da el ÍNDICE del «cubo» donde irá el valor.
- Para leer, se repite el cálculo y se va directo a ese cubo.
- Resultado: acceso promedio O(1), sin recorrer nada.
El problema: colisiones
Distintas claves pueden producir el mismo índice: eso es una colisión. Como el número de claves posibles es infinito y los cubos finitos, por el principio del palomar las colisiones SON obligatorias; el diseño no las elimina, las gestiona.
- Encadenamiento: cada cubo guarda una mini-lista de los que cayeron ahí. Buscar recorre solo esa lista.
- Sondeo abierto: si el cubo está ocupado, se prueban cubos vecinos según una regla hasta hallar uno libre.
| Escenario | Búsqueda | Cuándo ocurre |
|---|---|---|
| Promedio (buen hash, α bajo) | O(1) | distribución uniforme de claves |
| Peor caso | O(n) | todas las claves colisionan (hash adversario o pésimo) |
| Cubo con cadena larga | O(longitud de cadena) | α alto o cluster de colisiones |
f(x) = x · f(x) = log(x) · f(x) = 1
Errores frecuentes
- Asumir O(1) garantizado: una función hash que concentra claves (o un ataque deliberado, como el hash-flooding) degrada a O(n).
- Olvidar que las claves deben ser INMUTABLES y hashables: mutar la clave de un elemento ya insertado rompe el cálculo del cubo y lo «pierde».
- No dimensionar la tabla: α alto llena las cadenas; por eso se duplica el tamaño y se reinserta (rehash) al crecer.
Ejemplo resuelto
- Tabla de 10 cubos, función hash = longitud de la clave mod 10.
- Insertar «ana» (len 3) va al cubo 3; «luis» (len 4) al cubo 4; «eva» (len 3) al cubo 3.
- «ana» y «eva» colisionan: en encadenamiento, el cubo 3 guarda una lista de dos.
- Buscar «eva»: hash da 3, se recorre SOLO la lista de ese cubo (2 elementos) y se compara la clave.
- Si el cubo 3 acumulara miles, la búsqueda ahí sería lineal: señal de un hash que no dispersa.
Cuando escribes dict o set en Python, o cuando una base de datos resuelve una clave, o una caché consulta una sesión, hay una tabla hash detrás. Entender colisiones y factor de carga te advierte cuándo esa magia de «constant time» deja de serlo.
Una tabla hash da acceso promedio O(1), pero ¿qué situación la degrada hacia O(n)?
Relaciona cada término de una tabla hash con su papel:
Anatomía del hash
Toca una tarjeta para ver la respuesta.
Tablas hash (repaso formal)Funciones hash, resolución de colisiones y análisis de costo.
Explica con tus palabras por qué un set en Python responde «¿está x?» muchísimo más rápido que una list para millones de elementos, y describe una situación en la que aun así el set se degradaría y perdería su ventaja.
Tu texto se guarda sólo en este dispositivo.
VisuAlgoVisualizaciones animadas de estructuras de datos y algoritmos.
Comentarios
Inicia sesión para comentar.
Todavía no hay comentarios. Sé la primera persona en opinar.