Hash tables · Tablas hash
Hash tables: fast lookup
- A hash table stores items so you can find them very fast — usually in one step.
- It is a list of slots. A hash function turns a key into a slot number.
- Instead of searching every item, you jump straight to the slot the key belongs in.
Tablas hash: búsqueda rápida
- Una tabla hash almacena elementos para que puedas encontrarlos muy rápido, generalmente en un solo paso.
- Es una lista de espacios. Una función hash convierte una clave en un número de espacio.
- En lugar de buscar cada elemento, saltas directamente al espacio donde pertenece la clave.
A hash function
- A hash function takes a key and returns a slot index from
0tosize - 1. - The same key always gives the same slot, so you can find it again later.
- A simple one: add the character codes, then take
% sizeto stay in range.
Una función hash
- Una función hash toma una clave y devuelve un índice de espacio desde
0hastasize - 1. - La misma clave siempre da el mismo espacio, por lo que puedes encontrarla más tarde.
- Una simple: suma los códigos de los caracteres, luego toma
% sizepara mantenerse dentro del rango.
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch) # ord("A") is 65, ord("B") is 66, ...
return total % size
print(hash_key("cat", 10)) # a slot from 0 to 9
print(hash_key("cat", 10)) # same key -> same slot
print(hash_key("dog", 10))
Collisions
- Two different keys can hash to the same slot. That is a collision.
- A table has limited slots, so collisions are unavoidable as it fills up.
- We need a rule for what to do when the slot we want is already taken.
Colisiones
- Dos claves diferentes pueden hashear al mismo espacio. Eso es una colisión.
- Una tabla tiene espacios limitados, así que las colisiones son inevitables a medida que se llena.
- Necesitamos una regla sobre qué hacer cuando el espacio que queremos ya está ocupado.
Linear probing
- Linear probing: if a slot is full, try the next slot, then the next, wrapping around.
- Keep stepping
(slot + 1) % sizeuntil you find a free slot. - Below,
AandFboth want slot 0, soFis pushed to slot 1.
Sondeo lineal
- Sondeo lineal: si un espacio está lleno, prueba el siguiente espacio, luego el siguiente, dando vueltas.
- Sigue avanzando
(slot + 1) % sizehasta encontrar un espacio libre. - Abajo,
AyFambos quieren el espacio 0, así queFes empujado al espacio 1.
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch)
return total % size
def insert(table, key):
slot = hash_key(key, len(table))
while table[slot] is not None: # slot taken -> try the next one
slot = (slot + 1) % len(table)
table[slot] = key
return slot
table = [None] * 5
print(insert(table, "A")) # 0
print(insert(table, "F")) # 1 (A and F both hash to slot 0)
print(table) # ['A', 'F', None, None, None]
Looking up a key
- To find a key: hash it, then probe forward, comparing each slot to the key.
- Stop and return the index when you find it.
- If you reach an empty slot (or check every slot), the key is not there — return
-1.
Buscar una clave
- Para encontrar una clave: hazle hash, luego sonda hacia adelante, comparando cada espacio con la clave.
- Detente y devuelve el índice cuando la encuentres.
- Si llegas a un espacio vacío (o revisas todos los espacios), la clave no está ahí — devuelve
-1.
Why hash tables are fast
- With few collisions, insert and find take about one step — we call this
O(1). - As the table fills, probing gets longer, so it is wise to keep some slots free.
- In the worst case (everything collides) it slows to a linear scan,
O(n).
Por qué las tablas hash son rápidas
- Con pocas colisiones, insertar y encontrar toman aproximadamente un paso; llamamos a esto
O(1). - A medida que la tabla se llena, el sondeo se hace más largo, por lo que es sabio dejar algunos espacios libres.
- En el peor caso (todo colisiona), se ralentiza a un escaneo lineal,
O(n).
Common mistakes
- A hash function maps a key to an index in the table.
- Two keys can collide at the same index — handle it, for example by chaining.
Errores comunes
- Una función hash mapea una clave a un índice en la tabla.
- Dos claves pueden colisionar en el mismo índice — maneja eso, por ejemplo mediante encadenamiento.
Now you try
- Build the three parts: the hash function, insert with probing, and find.
- Each task checks your function on collisions and wrap-around cases.
- Press Check answer to test it.
Ahora tú intentas
- Construye las tres partes: la función hash, la inserción con sondeo y la búsqueda.
- Cada tarea verifica tu función en casos de colisión y casos de giro.
- Presiona Check answer para probarlo.
Hashing to a bucket · Hashing a un cubo
A hash function sends each key to a bucket; clashes chain. · Una función hash envía cada clave a un cubo; los choques forman una cadena.
Write hash_key(key, size). Add the character codes of key (use ord(ch)) and return the total % size, so the result is a slot from 0 to · hasta size - 1. Example: hash_key("AB", 10) is (65 + 66) % 10 = 1. The empty string gives 0. · Escribe hash_key(key, size). Suma los códigos de carácter de key (usa ord(ch)) y devuelve el total % size, para que el resultado sea una posición de 0 a size - 1. Ejemplo: hash_key("AB", 10) es (65 + 66) % 10 = 1. La cadena vacía da 0.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
hash_key is provided. Write insert(table, key) using linear probing: go to the key's hash slot; while that slot is full (not None), step to (slot + 1) % len(table); put the key in the first free slot and return its index. · hash_key está proporcionada. Escribe insert(table, key) usando sondeo lineal: ve a la ranura hash de la clave; mientras esa ranura esté llena (no sea None), avanza a (slot + 1) % len(table); coloca la clave en la primera ranura libre y devuelve su índice.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
hash_key is provided. Write find(table, key) that returns the index of key, or -1 if it is missing. Start at the hash slot and probe forward, comparing each slot. Stop at an empty · vacíos slot (key not there). Make sure it ends even if the table is full · pleno — never loop forever. · hash_key está proporcionada. Escribe find(table, key) que devuelva el índice de key, o -1 si no se encuentra. Comienza en la ranura hash y sondea hacia adelante, comparando cada ranura. Detente al encontrar una ranura vacía (la clave no está ahí). Asegúrate de que termine incluso si la tabla está llena — nunca bucle indefinidamente.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.