Internals de las funciones hash y gestión de colisiones
Comprenda cómo Python aplica hash a los objetos, cómo el direccionamiento abierto y el encadenamiento resuelven colisiones, y por qué O(1) en el caso promedio puede degradarse a O(n).
Internals de las funciones hash y gestión de colisiones es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué es un mapa hash?
Un mapa hash (un diccionario en Python) asocia claves con valores mediante una función hash que convierte cualquier clave en un índice entero de un array subyacente. Una función hash ideal distribuye las claves uniformemente por el array, lo que permite realizar búsquedas, inserciones y eliminaciones en O(1) en el caso medio. El array subyacente se denomina tabla hash o array de cubetas.
En Python, dict es un mapa hash altamente optimizado. Comprender sus componentes internos le ayuda a razonar sobre el comportamiento en el peor caso y a elegir las claves adecuadas.
# Python dict is a hash map
hm = {}
hm['alice'] = 95
hm['bob'] = 87
hm['carol'] = 91
print(hm['alice']) # O(1) lookup: 95
print('bob' in hm) # O(1) membership: True
del hm['bob'] # O(1) deletion
print(hm) # {'alice': 95, 'carol': 91}Funciones hash y el método __hash__
Python llama a __hash__(key) para calcular un entero a partir de la clave y, después, toma ese entero módulo el tamaño de la tabla para encontrar el índice de la cubeta. Los tipos integrados como int, str y tuple cuentan con implementaciones hash integradas y rápidas. list y dict no son hashables (son mutables, y modificarlos invalidaría cualquier hash almacenado).
Una buena función hash distribuye las claves uniformemente, es determinista y se calcula rápidamente. El hash de las cadenas de Python se aleatoriza entre ejecuciones (una medida de seguridad); utilice PYTHONHASHSEED=0 para desactivarlo y obtener reproducibilidad en las pruebas.
# Built-in hash in Python
print(hash(42)) # integer hashes to itself (CPython)
print(hash('hello')) # string hash (randomised per run)
print(hash((1, 2, 3))) # tuple hash: depends on contents
# Unhashable types
try:
hash([1, 2, 3]) # lists are mutable -> not hashable
except TypeError as e:
print('Error:', e)
# Custom class: define __hash__ and __eq__
class Point:
def __init__(self, x, y): self.x = x; self.y = y
def __hash__(self): return hash((self.x, self.y))
def __eq__(self, other): return self.x == other.x and self.y == other.y
points = {Point(1, 2): 'A', Point(3, 4): 'B'}
print(points[Point(1, 2)]) # 'A'Colisiones: cuando dos claves generan la misma cubeta
Se produce una colisión cuando dos claves distintas generan el mismo índice de cubeta. Las colisiones son inevitables (por el principio del palomar: hay infinitas claves y un número finito de cubetas). Dos estrategias estándar para resolverlas son el encadenamiento y el direccionamiento abierto. Python utiliza una variante del direccionamiento abierto con sondeo seudoaleatorio.
El encadenamiento almacena una lista enlazada (o un array dinámico) en cada cubeta; todas las claves que colisionan en esa cubeta forman una cadena. El direccionamiento abierto busca la siguiente cubeta vacía según una secuencia de sondeo.
# Simplified chaining hash map
class ChainingHashMap:
def __init__(self, capacity=8):
self.capacity = capacity
self.buckets = [[] for _ in range(capacity)]
def _idx(self, key):
return hash(key) % self.capacity
def put(self, key, val):
bucket = self.buckets[self._idx(key)]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, val)
return
bucket.append((key, val))
def get(self, key):
for k, v in self.buckets[self._idx(key)]:
if k == key:
return v
return None
hm = ChainingHashMap()
hm.put('a', 1); hm.put('b', 2)
print(hm.get('a')) # 1
print(hm.get('c')) # NoneDireccionamiento abierto: sondeo lineal
En el sondeo lineal, cuando se produce una colisión en el índice i, el mapa comprueba i+1, i+2, ... (volviendo al principio al llegar al final) hasta encontrar una posición vacía. La búsqueda debe sondear la misma secuencia para encontrar la clave. Las eliminaciones requieren un marcador «tombstone» en lugar de vaciar la posición, para no romper la cadena de sondeo.
El agrupamiento es el principal inconveniente: una vez que se forma un grupo de posiciones ocupadas, las inserciones posteriores en esa zona amplían el grupo y degradan el rendimiento hasta acercarlo a O(n).
class LinearProbingHashMap:
DELETED = object() # tombstone sentinel
def __init__(self, capacity=8):
self.capacity = capacity
self.keys = [None] * capacity
self.vals = [None] * capacity
self.size = 0
def _probe(self, key):
idx = hash(key) % self.capacity
while self.keys[idx] is not None and self.keys[idx] != key:
idx = (idx + 1) % self.capacity
return idx
def put(self, key, val):
idx = self._probe(key)
if self.keys[idx] is None:
self.size += 1
self.keys[idx] = key
self.vals[idx] = val
def get(self, key):
idx = self._probe(key)
if self.keys[idx] == key:
return self.vals[idx]
return None
hm = LinearProbingHashMap()
hm.put('x', 10); hm.put('y', 20)
print(hm.get('x')) # 10Factor de carga y redimensionamiento
El factor de carga es la proporción entre las entradas almacenadas y la capacidad total: α = n/m. A medida que aumenta α, también aumenta la probabilidad de colisión y el rendimiento se degrada. El dict de Python cambia de tamaño (duplica la capacidad) cuando el factor de carga supera aproximadamente 2/3. El redimensionamiento vuelve a calcular el hash de todas las entradas existentes y las coloca en la nueva tabla, una operación O(n) que se produce con poca frecuencia y mantiene el coste amortizado de inserción en O(1).
import sys
d = {}
prev_size = sys.getsizeof(d)
for i in range(30):
d[i] = i
new_size = sys.getsizeof(d)
if new_size != prev_size:
print(f'Resized at n={i+1}: {prev_size} -> {new_size} bytes')
prev_size = new_sizeO(1) medio frente a O(n) en el peor caso
Con una buena función hash, las colisiones son poco frecuentes y la longitud esperada de la cadena es constante, independientemente de n. Por tanto, las búsquedas, inserciones y eliminaciones tienen un coste de O(1) en el caso medio. Sin embargo, un escenario de peor caso, como una entrada diseñada deliberadamente para asignar todas las claves a la misma cubeta, degrada todas las operaciones a O(n). La semilla hash aleatorizada de Python mitiga este ataque, pero no elimina el peor caso en términos teóricos.
En un análisis de entrevista, diga: «O(1) en promedio y O(n) en el peor caso debido a las colisiones».
# Python randomised hash seed prevents worst-case hash-flooding
import os
print('PYTHONHASHSEED:', os.environ.get('PYTHONHASHSEED', 'random'))
# By default Python randomises the hash of strings each run
# This prevents an attacker from crafting keys that all collide
# To reproduce results in testing: PYTHONHASHSEED=0 python script.pydict, defaultdict y Counter de Python
Python proporciona tres variantes de mapas hash que conviene conocer. dict es el mapa de uso general; acceder a una clave ausente genera KeyError. defaultdict(factory) devuelve un valor predeterminado al acceder a una clave ausente (es útil para recopilar listas o contar). Counter es una subclase especializada para contar objetos hashables y también admite operaciones aritméticas entre contadores.
from collections import defaultdict, Counter
# defaultdict for grouping
groups = defaultdict(list)
for word in ['apple', 'ant', 'banana', 'bee', 'avocado']:
groups[word[0]].append(word)
print(dict(groups))
# {'a': ['apple','ant','avocado'], 'b': ['banana','bee']}
# Counter for frequency
c = Counter('abracadabra')
print(c.most_common(3)) # [('a',5),('b',2),('r',2)]
print(c['a'] - Counter('aa')['a']) # counter subtractionMapa hash frente a conjunto hash
Un conjunto hash almacena únicamente claves (sin valores asociados) y permite comprobar la pertenencia, insertar y eliminar elementos en O(1). El set de Python es un conjunto hash. Utilice un conjunto cuando solo necesite responder a la pregunta «¿existe este elemento?», sin almacenar datos asociados. Utilice un dict cuando necesite asociar valores (conteos, resultados, etc.) con claves.
# set for membership testing
visited = set()
for node in [1, 3, 5, 3, 7, 1]:
if node not in visited:
print('New node:', node)
visited.add(node)
# Set operations: union, intersection, difference
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print('Union:', A | B) # {1,2,3,4,5,6}
print('Intersection:', A & B) # {3,4}
print('Difference:', A - B) # {1,2}Implementar un mapa hash desde cero (versión de entrevista)
A veces, los entrevistadores le pedirán implementar un mapa hash básico. Sus componentes clave son: un array de cubetas de tamaño fijo (utilice 16 o 1024); cada cubeta es una lista de pares (key, value) para el encadenamiento; una función hash (utilice el hash integrado de Python % capacity); y un redimensionamiento cuando el factor de carga supere 0.7. Mencionar proactivamente el redimensionamiento y el factor de carga demuestra un conocimiento profundo.
class HashMap:
def __init__(self, capacity=16):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, val):
b = self.buckets[self._hash(key)]
for i, (k, v) in enumerate(b):
if k == key:
b[i] = (key, val)
return
b.append((key, val))
self.size += 1
if self.size / self.capacity > 0.7:
self._resize()
def get(self, key, default=None):
for k, v in self.buckets[self._hash(key)]:
if k == key:
return v
return default
def _resize(self):
old = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.size = 0
for bucket in old:
for k, v in bucket:
self.put(k, v)
hm = HashMap()
for i in range(20):
hm.put(i, i * 2)
print(hm.get(10)) # 20
print(hm.capacity) # should have resizedCuándo fallan los mapas hash: claves no hashables
Solo los objetos hashables pueden ser claves de un diccionario. En Python, un objeto es hashable si tiene un método __hash__ y un método __eq__, y su valor hash no cambia durante toda su vida útil. Las listas, los conjuntos y los diccionarios son mutables y, por tanto, no son hashables. Las tuplas y los frozensets son alternativas hashables a las listas y los conjuntos cuando se utilizan como claves.
Una trampa habitual en las entrevistas: para agrupar anagramas se debe utilizar una tupla ordenada (no una lista ordenada) como clave del diccionario.
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # tuple is hashable; list is not
groups[key].append(s)
return list(groups.values())
print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]Resumen: complejidad de los mapas hash
Los mapas hash ofrecen un coste medio de O(1) para insertar, eliminar y buscar, lo que constituye la base de muchas soluciones óptimas de entrevistas. Los supuestos clave son que una buena función hash distribuye las claves uniformemente, que el factor de carga se mantiene acotado (el redimensionamiento se encarga de mantenerlo así) y que los objetos clave son inmutables y hashables. Cuando se cumplen estos supuestos, los mapas hash convierten los recorridos lineales O(n) en búsquedas O(1), lo que permite soluciones como two-sum en O(n) en lugar de O(n²).
Comprobación rápida
Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección aprendió que: un mapa hash asigna claves a índices de cubeta mediante una función hash y consigue operaciones O(1) en el caso medio, las colisiones se resuelven mediante encadenamiento (una lista enlazada por cubeta) o direccionamiento abierto (sondeo hasta encontrar la siguiente posición vacía) y solo los objetos inmutables y hashables pueden ser claves de un diccionario; utilice tuplas en lugar de listas cuando necesite una clave de secuencia. A continuación resolverá two-sum y sus numerosas variantes de entrevista.
Preguntas frecuentes
¿La lección «Internals de las funciones hash y gestión de colisiones» es gratis?
Sí — el texto completo de «Internals de las funciones hash y gestión de colisiones» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Internals de las funciones hash y gestión de colisiones»?
Comprenda cómo Python aplica hash a los objetos, cómo el direccionamiento abierto y el encadenamiento resuelven colisiones, y por qué O(1) en el caso promedio puede degradarse a O(n). Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar DSA Interview Prep?
No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.
¿Cuánto tiempo toma la lección «Internals de las funciones hash y gestión de colisiones»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?
Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Internals de las funciones hash y gestión de colisiones
- Two-sum y sus numerosas variantes
- Conteo y agrupación por frecuencia
- Secuencia consecutiva más larga y caché LRU