| English | Español |
|---|---|
| hash function/hæʃ ˈfʌŋkʃn/ | función hash |
| key/kiː/ | clave |
| address/əˈdres/ | dirección |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | determinista |
| collision/kəˈlɪʒn/ | colisión |
| linear probing/ˈlɪnɪə ˈprəʊbɪŋ/ | sondeo lineal |
| chaining/ˈtʃeɪnɪŋ/ | encadenamiento |
| load factor/ləʊd ˈfæktə/ | factor de carga |
Finding one row in fifty million without looking
- A supermarket till scans a barcode and the price appears before your hand leaves the item. The product file holds fifty million lines.
- Nothing searched them. The barcode number went through a short calculation that produced a position, and the computer read that position: one read, no comparisons, the same time whether the file holds fifty rows or fifty million.
- The calculation is a hash function 散列函数, and the whole idea rests on it: do not store data where it will fit, store it where its own key says it belongs.
- This lesson is hashing algorithms, what happens when two keys want the same slot, and how to search and insert.
Encontrar una fila en cincuenta millones sin buscar
- La caja registradora de un supermercado escanea un código de barras y el precio aparece antes de que tu mano se aleje del artículo. El archivo de productos contiene cincuenta millones de líneas.
- No las buscó a todas. El número del código de barras pasó por un cálculo corto que produjo una posición, y la computadora leyó esa posición: una lectura, ninguna comparación, el mismo tiempo ya sea que el archivo contenga cincuenta filas o cincuenta millones.
- Ese cálculo es una función hash 散列函数, y toda la idea se basa en ella: no almacenes los datos donde quepan, almacénalos donde su propia clave indique que deben estar.
- Esta lección trata sobre algoritmos de hash, qué sucede cuando dos claves quieren ocupar el mismo espacio, y cómo buscar e insertar.
The hash function
- A hash function, or hashing algorithm, takes a record's key 键 and produces the address 地址 at which the record is stored.
- A good one is fast, deterministic 确定性 (the same key always gives the same address), and spreads keys evenly across the available slots.
- For $N$ slots, the three the syllabus expects: modulo,
address ← key MOD N; folding, split the key into pieces, add them, then MOD $N$; a string hash, add the character codes, then MOD $N$.
La función hash
- Una función hash, o algoritmo de hash, toma la clave 键 de un registro y produce la dirección 地址 en la cual se almacena dicho registro.
- Una buena función es rápida, determinista 确定性 (la misma clave siempre produce la misma dirección) y distribuye las claves de manera uniforme entre los espacios disponibles.
- Para $N$ espacios, las tres que espera el programa son: módulo,
address ← key MOD N; doblez, divide la clave en partes, súmalas y luego aplica MÓDULO $N$; un hash de cadena, suma los códigos de los caracteres y luego aplica MÓDULO $N$.
A hash function: · Una función hash:
A hash function maps a key to an address, enabling near-instant direct lookup. · Una función hash mapea una clave a una dirección, permitiendo una búsqueda directa casi instantánea.
What makes a hash function a good one? Select all · todos that apply. · ¿Qué hace que una función hash sea buena? Selecciona todas las opciones correctas.
Fast, deterministic and evenly spread. No realistic hash avoids collisions entirely, which is why every design includes a resolution strategy. · Rápida, determinista y distribuida uniformemente. Ninguna función hash real evita las colisiones por completo, por lo que todo diseño incluye una estrategia de resolución.
Worked example: apply each algorithm
- A file has 10 slots, numbered 0 to 9. Where does key 4517 go?
- Modulo: $4517 \bmod 10 = 7$, so slot 7.
- Folding in pairs: $45 + 17 = 62$, then $62 \bmod 10 = 2$, so slot 2.
- And the key "CAB" by a string hash? $67 + 65 + 66 = 198$, then $198 \bmod 10 = 8$, so slot 8.
- Show the arithmetic. The mark is for the calculation, not the slot number alone.
Ejemplo resuelto: aplicar cada algoritmo
- Un archivo tiene 10 espacios, numerados del 0 al 9. ¿A dónde va la clave 4517?
- Módulo: $4517 \bmod 10 = 7$, por lo tanto, espacio 7.
- Doblez en pares: $45 + 17 = 62$, luego $62 \bmod 10 = 2$, por lo tanto, espacio 2.
- ¿Y la clave "CAB" mediante un hash de cadena? $67 + 65 + 66 = 198$, luego $198 \bmod 10 = 8$, por lo tanto, espacio 8.
- Muestra la aritmética. La nota es por el cálculo, no solo por el número del espacio.
Using the modulo hash address ← key MOD N with key = 27 and N = 10, what address is produced? · Usando el hash de módulo address ← key MOD N con key = 27 y N = 10, ¿qué dirección se produce?
27 MOD 10 = 7 (the remainder when 27 is divided by 10). · 27 MOD 10 = 7 (el residuo cuando 27 se divide entre 10).
A table has 10 slots. Using folding in pairs on key 4517 (add 45 and 17, then MOD 10), which slot does it go to? · Una tabla tiene 10 ranuras. Usando plegado en pares en la clave 4517 (sumar 45 y 17, luego MOD 10), ¿a qué ranura va?
45 + 17 = 62, and 62 MOD 10 = 2. The same key under a modulo hash would go to slot 7 instead. · 45 + 17 = 62, y 62 MOD 10 = 2. La misma clave bajo una función hash de módulo iría a la ranura 7 en cambio.
Collisions
- A collision 冲突 happens when two different keys hash to the same address. With any hash and any realistic file, collisions are certain, so a strategy for them is part of the design, not an afterthought.
- Linear probing 线性探测 puts the record in the next free slot, wrapping round to the start at the end of the table. Simple, but records cluster: a full patch grows and every key landing in it takes longer.
- Chaining 链接法 makes each slot the head of a linked list of all the records that hashed there. No clustering, but extra memory for the pointers and a short walk along the list.
- Rehashing applies a second hash function to find another slot, spreading keys better at the cost of more computation.
Colisiones
- Una colisión 冲突 ocurre cuando dos claves diferentes tienen hash al mismo espacio. Con cualquier función hash y cualquier archivo realista, las colisiones son seguras, por lo que una estrategia para manejarlas es parte del diseño, no un añadido posterior.
- Sondeo lineal 线性探测 coloca el registro en el siguiente espacio libre, dando la vuelta al inicio al llegar al final de la tabla. Es simple, pero los registros se agrupan: un bloque lleno crece y cada clave que cae en él tarda más en ser accedida.
- Encadenamiento 链接法 hace que cada espacio sea la cabeza de una lista enlazada de todos los registros que tuvieron hash allí. No hay agrupación, pero requiere memoria extra para los punteros y un recorrido breve por la lista.
- Rehashing aplica una segunda función hash para encontrar otro espacio, distribuyendo mejor las claves a costa de mayor computación.
A collision occurs when: · Una colisión ocurre cuando:
Two keys mapping to the same slot is a collision; it must be resolved by probing, chaining or rehashing. · Dos claves mapeadas a la misma ranura es una colisión; debe resolverse mediante sondeo, encadenamiento o rehacheo.
Match each collision-handling idea to what it does. · Empareja cada idea de manejo de colisiones con lo que hace.
Collisions are resolved by chaining or probing; keeping the load factor low keeps lookups near O(1). · Las colisiones se resuelven mediante encadenamiento o sondeo; mantener el factor de carga bajo mantiene las búsquedas cerca de O(1).
Searching and inserting
- To insert: hash the key. If the slot is free, write the record there. If not, follow the resolution strategy, the next free slot for linear probing, or the front of that slot's list for chaining.
- To search: hash the key and read that slot. If the stored key matches, the record is found. If it does not, follow the same strategy, until either the keys match or an empty slot proves the record is not in the file.
- Both operations use the same strategy. A search that stops at the first mismatch would miss every record that was ever displaced by a collision.
Búsqueda e inserción
- Para insertar: haz hash de la clave. Si el espacio está libre, escribe el registro ahí. Si no, sigue la estrategia de resolución: el siguiente espacio libre para el sondeo lineal, o el frente de la lista de ese espacio para el encadenamiento.
- Para buscar: haz hash de la clave y lee ese espacio. Si la clave almacenada coincide, el registro se encuentra. Si no, sigue la misma estrategia, hasta que las claves coincidan o un espacio vacío demuestre que el registro no está en el archivo.
- Ambas operaciones usan la misma estrategia. Una búsqueda que se detiene en la primera discrepancia omitiría todos los registros que alguna vez fueron desplazados por una colisión.
Worked example: trace a collision
- A table of 10 slots uses
key MOD 10with linear probing. Insert 23, 33, 43 in that order, then search for 43. - 23 hashes to 3; slot 3 is free, so it goes there. 33 hashes to 3; slot 3 is taken by 23, so linear probing puts it in slot 4. 43 hashes to 3; slots 3 and 4 are taken, so it goes in slot 5.
- Searching for 43: hash to 3, read slot 3, key is 23, not a match, so probe on; slot 4 holds 33, not a match; slot 5 holds 43, found, after three reads.
- That growing run of three is the clustering that linear probing causes.
Ejemplo resuelto: rastrear una colisión
- Una tabla de 10 espacios usa
key MOD 10con sondeo lineal. Inserta 23, 33, 43 en ese orden, luego busca 43. - 23 tiene hash en 3; el espacio 3 está libre, así que va ahí. 33 tiene hash en 3; el espacio 3 está ocupado por 23, así que el sondeo lineal lo pone en el espacio 4. 43 tiene hash en 3; los espacios 3 y 4 están ocupados, así que va al espacio 5.
- Buscar 43: hash en 3, lee espacio 3, la clave es 23, no coincide, así que sonda hacia adelante; el espacio 4 contiene 33, no coincide; el espacio 5 contiene 43, encontrado, después de tres lecturas.
- Esa secuencia creciente de tres es el agrupamiento que causa el sondeo lineal.
Hash each key straight to a bucket · Enfoca cada clave directamente en un cubo
A hash function turns a key into a bucket number, so you jump straight to the record instead of searching. When two keys land in the same bucket that is a collision — they chain together in that bucket. · Una función hash convierte una clave en un número de cubo, para que saltes directamente al registro en lugar de buscarlo. Cuando dos claves caen en el mismo cubo, es una colisión — se encadenan juntas en ese cubo.
When searching a hash table, the record is not in the file as soon as the first slot read holds a different key. · Al buscar en una tabla hash, el registro no está en el archivo tan pronto como la primera ranura leída contiene una clave diferente.
The record may have been displaced by a collision. The search follows the same resolution strategy until a match or an empty slot. · El registro pudo haber sido desplazado por una colisión. La búsqueda sigue la misma estrategia de resolución hasta encontrar una coincidencia o una ranura vacía.
Load factor
- The load factor 装填因子 is the number of records divided by the number of slots. It is the single number that predicts how well the table performs.
- Below about 70% the average lookup is near one read. Above it, probe sequences lengthen sharply and performance degrades towards a linear search.
- The fix is to make the table larger and rehash every record into it, which is why a hash table is sized for the data it will hold, not the data it holds today.
Factor de carga
- El factor de carga 装填因子 es el número de registros dividido por el número de espacios. Es el único número que predice qué tan bien funcionará la tabla.
- Por debajo del 70%, la búsqueda promedio es cercana a una lectura. Por encima de ese valor, las secuencias de sondeo se alargan drásticamente y el rendimiento se degrada hacia una búsqueda lineal.
- La solución es hacer la tabla más grande y rehashear todos los registros en ella, razón por la cual una tabla hash se dimensiona según los datos que contendrá, no según los que tiene hoy.
A 10-slot table uses key MOD 10 with linear probing. After inserting 23, 33 and 43 in that order, which slot holds 43? · Una tabla de 10 ranuras usa clave MOD 10 con sondeo lineal. Después de insertar 23, 33 y 43 en ese orden, ¿qué ranura contiene 43?
All three hash to 3. 23 takes slot 3, 33 is probed to 4, and 43 to 5. Three keys in a row is exactly the clustering linear probing causes. · Los tres hacen hash en 3. 23 ocupa la ranura 3, 33 se sondea a 4, y 43 a 5. Tres claves seguidas es exactamente el agrupamiento que causa el sondeo lineal.
Marks that slip away
- A collision is two keys, one address. It is not an error and not a lost record; it is the normal case a strategy handles.
- A search must follow the same resolution strategy as the insert, and stop only on a match or an empty slot.
- Linear probing clusters; chaining costs memory. Give the trade-off, not just the mechanism.
- The load factor is records divided by slots, and the threshold is about 70%, not 100%.
Puntos que se pierden
- Una colisión es dos claves, un espacio. No es un error ni un registro perdido; es el caso normal que maneja una estrategia.
- Una búsqueda debe seguir la misma estrategia de resolución que la inserción, y detenerse solo en una coincidencia o un espacio vacío.
- El sondeo lineal agrupa; el encadenamiento cuesta memoria. Explica el compromiso, no solo el mecanismo.
- El factor de carga es registros divididos por espacios, y el umbral es aproximadamente 70%, no 100%.
To keep hash lookups fast, the load factor (records ÷ slots) should be kept: · Para mantener las búsquedas en hash rápidas, el factor de carga (registros ÷ ranuras) debe mantenerse:
A lower load factor means fewer collisions, so lookups stay close to O(1). · Un factor de carga menor significa menos colisiones, por lo que las búsquedas se mantienen cerca de O(1).
You've got it
- a hash function turns a key into an address: fast, deterministic, evenly spread; modulo, folding and string hashes are the three to know
- a collision is two keys hashing to one address, resolved by linear probing (next free slot, clusters), chaining (a linked list per slot, more memory) or rehashing
- insert and search both follow the same strategy; a search ends on a match or an empty slot
- keep the load factor, records divided by slots, below about 70% for near one-read lookups
Lo has entendido
- una función hash convierte una clave en una dirección: rápida, determinista, distribución uniforme; módulo, doblez y hashes de cadena son las tres que debes conocer
- una colisión es dos claves que tienen hash a un mismo espacio, resuelta mediante sondeo lineal (siguiente espacio libre, agrupamiento), encadenamiento (una lista enlazada por espacio, más memoria) o rehashing
- la inserción y la búsqueda siguen la misma estrategia; una búsqueda termina en una coincidencia o un espacio vacío
- mantén el factor de carga, registros divididos por espacios, por debajo del 70% para búsquedas de casi una sola lectura