Hashing
Introducido| English | Significado |
|---|---|
| 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/ | GLOSARIO {"sentido": "colisión", "asignatura": "a level computer science", "término": "collision"} |
| linear probing/ˈlɪnɪə ˈprəʊbɪŋ/ | sonda lineal |
| chaining/ˈtʃeɪnɪŋ/ | encadenamiento |
| load factor/ləʊd ˈfæktə/ | factor de carga |
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.
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$.
Una función hash:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Una función hash mapea una clave a una dirección, permitiendo una búsqueda directa casi instantánea.
¿Qué hace que una función hash sea buena? Selecciona todas las opciones correctas.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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.
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.
Usando el hash de módulo address ← key MOD N con key = 27 y N = 10, ¿qué dirección se produce?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
27 MOD 10 = 7 (el residuo cuando 27 se divide entre 10).
Una tabla tiene 10 ranuras. Usando plegado en pares en la clave 4517 (sumar 45 y 17, luego MOD 10), ¿a qué ranura va?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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.
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.
Una colisión ocurre cuando:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Dos claves mapeadas a la misma ranura es una colisión; debe resolverse mediante sondeo, encadenamiento o rehacheo.
Empareja cada idea de manejo de colisiones con lo que hace.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Las colisiones se resuelven mediante encadenamiento o sondeo; mantener el factor de carga bajo mantiene las búsquedas cerca de O(1).
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.
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.
Enfoca cada clave directamente en un cubo
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.
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.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
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.
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.
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?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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.
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%.
Para mantener las búsquedas en hash rápidas, el factor de carga (registros ÷ ranuras) debe mantenerse:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Un factor de carga menor significa menos colisiones, por lo que las búsquedas se mantienen cerca de O(1).
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