¿Cómo es bella {}?
Le permite almacenar valores por clave y recuperarlos de una manera muy rentable ( O(1)más sobre esto más adelante).
En esta publicación quiero implementar una tabla hash muy básica y echar un vistazo a su funcionamiento interno para explicar una de las ideas más ingeniosas de la informática.
El problema
Imagine que está construyendo un nuevo lenguaje de programación: comienza con tipos bastante simples (cadenas, enteros, flotantes,…) y luego procede a implementar estructuras de datos muy básicas. Primero, aparece la matriz ( []), luego viene la tabla hash (también conocida como diccionario, matriz asociativa, mapa hash, mapa y… la lista continúa).
¿Alguna vez se preguntó cómo funcionan? ¿Cómo son tan malditamente rápidos?
Bueno, digamos que JavaScript no tenía {}o new Map(), ¡e implementemos el nuestro DumbMap!
Una nota sobre la complejidad
Antes de empezar a rodar, necesitamos entender cómo funciona la complejidad de una función: Wikipedia tiene un buen repaso sobre la complejidad computacional, pero agregaré una breve explicación para las perezosas.
La complejidad mide cuántos pasos requiere nuestra función: cuantos menos pasos, más rápida es la ejecución (también conocido como "tiempo de ejecución").
Echemos un vistazo al siguiente fragmento:
function fn(n, m) { return n * m}La complejidad computacional (a partir de ahora simplemente "complejidad") de fnes O(1), lo que significa que es constante (se puede leer O(1)como " el costo es uno "): no importa qué argumentos pase, la plataforma que ejecuta este código solo tiene que realizar una operación (multiplicar nen m). Nuevamente, dado que es una operación, el costo se denomina O(1).
La complejidad se mide asumiendo que los argumentos de su función podrían tener valores muy grandes. Veamos este ejemplo:
function fn(n, m) { let s = 0 for (i = 0; i < 3; i++) { s += n * m } return s}Pensarías que su complejidad es O(3), ¿verdad?
Nuevamente, dado que la complejidad se mide en el contexto de argumentos muy grandes, tendemos a "descartar" constantes y considerar O(3)lo mismo que O(1). Entonces, incluso en este caso, diríamos que la complejidad de fnes O(1). No importa cuál sea el valor de ny m, siempre terminas haciendo tres operaciones, lo cual, nuevamente, es un costo constante (por lo tanto O(1)).
Ahora este ejemplo es un poco diferente:
function fn(n, m) { let s = [] for (i = 0; i < n; i++) { s.push(m) } return s}Como puede ver, estamos repitiendo tantas veces como el valor de n, que podría ser de millones. En este caso, definimos la complejidad de esta función como O(n), ya que necesitará realizar tantas operaciones como el valor de uno de sus argumentos.
¿Otros ejemplos?
function fn(n, m) { let s = [] for (i = 0; i < 2 * n; i++) { s.push(m) } return s}Este ejemplo repite 2 * ntiempos, lo que significa que la complejidad debería ser O(2n). Dado que mencionamos que las constantes se "ignoran" al calcular la complejidad de una función, este ejemplo también se clasifica como O(n).
¿Uno mas?
function fn(n, m) { let s = [] for (i = 0; i < n; i++) { for (i = 0; i < n; i++) { s.push(m) } } return s}Aquí estamos repitiendo ny repitiendo el bucle dentro del bucle principal, lo que significa que la complejidad es “cuadrada” ( n * n): si nes 2, ejecutaremos s.push(m)4 veces, si 3 lo ejecutaremos 9 veces, y así sucesivamente.
En este caso, la complejidad de la función se denomina O(n²).
¿Un último ejemplo?
function fn(n, m) { let s = [] for (i = 0; i < n; i++) { s.push(n) } for (i = 0; i < m; i++) { s.push(m) } return s}En este caso, no tenemos bucles anidados, pero lo hacemos dos veces sobre dos argumentos diferentes: la complejidad se define como O(n+m). Claro como el cristal.
Ahora que acaba de recibir una breve introducción (o un repaso) sobre la complejidad, es muy fácil entender que una función con complejidad O(1)funcionará mucho mejor que una con O(n).
Las tablas hash tienen una O(1)complejidad: en términos sencillos , son superrápidas . Vamonos.
(Estoy un poco acostado en tablas hash que siempre tienen O(1)complejidad, pero sigue leyendo;))
Construyamos una tabla hash (tonta)
Nuestra tabla hash tiene 2 métodos simples: set(x, y)y get(x). Comencemos a escribir código:
E implementemos una forma muy simple e ineficiente de almacenar estos pares clave-valor y recuperarlos más adelante. Primero comenzamos por almacenarlos en una matriz interna (recuerde, no podemos usar {}ya que estamos implementando {}, ¡alucinante!):
Entonces es simplemente una cuestión de obtener el elemento correcto de la lista:
Nuestro ejemplo completo:
¡Nuestro DumbMap es asombroso! Funciona de inmediato, pero ¿cómo funcionará cuando agreguemos una gran cantidad de pares clave-valor?
Probemos con un punto de referencia simple. Primero intentaremos encontrar un elemento no existente en una tabla hash con muy pocos elementos, y luego intentaremos lo mismo en uno con una gran cantidad de elementos:
¿Los resultados? No tan alentador:
with very few records in the map: 0.118mswith lots of records in the map: 14.412msEn nuestra implementación, necesitamos recorrer todos los elementos internos this.listpara encontrar uno con la clave correspondiente. El costo es O(n), y es bastante terrible.
Hazlo mas rapido)
Necesitamos encontrar una manera de evitar recorrer nuestra lista: es hora de volver a poner hash en la tabla hash .
¿Alguna vez se preguntó por qué esta estructura de datos se llama tabla hash ? Esto se debe a que se usa una función hash en las teclas que configura y obtiene. Usaremos esta función para convertir nuestra clave en un número entero iy almacenar nuestro valor en el índice ide nuestra lista interna. Dado que acceder a un elemento, por su índice, desde una lista tiene un costo constante ( O(1)), la tabla hash también tendrá un costo de O(1).
Probemos esto:
Aquí estamos usando el módulo string-hash, que simplemente convierte una cadena en un hash numérico. Lo usamos para almacenar y recuperar elementos en el índice hash(key)de nuestra lista. ¿Los resultados?
with lots of records in the map: 0.013msW - O - W. ¡De esto es de lo que estoy hablando!
No tenemos que recorrer todos los elementos de la lista, ¡y recuperarlos DumbMapes súper rápido!
Permítanme expresarlo de la manera más sencilla posible: el hash es lo que hace que las tablas hash sean extremadamente eficientes . Sin magia. Nada mas. Nada. Solo una idea simple, inteligente e ingeniosa.
El costo de elegir la función hash correcta
Por supuesto, elegir una función de hash rápido es muy importante. Si nuestro se hash(key)ejecuta en unos segundos, nuestra función será bastante lenta independientemente de su complejidad.
Al mismo tiempo, es muy importante asegurarse de que nuestra función hash no produzca muchas colisiones , ya que serían perjudiciales para la complejidad de nuestra tabla hash.
¿Confuso? Echemos un vistazo más de cerca a las colisiones.
Colisiones
Podría pensar “¡ Ah, una buena función hash nunca genera colisiones! ”: Bueno, regrese al mundo real y piénselo de nuevo. Google pudo producir colisiones para el algoritmo de hash SHA-1, y es solo una cuestión de tiempo, o potencia computacional, antes de que una función de hash se rompa y devuelva el mismo hash para 2 entradas diferentes. Siempre asuma que su función hash genera colisiones e implemente la defensa adecuada contra tales casos.
Por ejemplo, intentemos usar una hash()función que genere muchas colisiones:
Esta función usa una matriz de 10 elementos para almacenar valores, lo que significa que es probable que los elementos sean reemplazados, un error desagradable en nuestro DumbMap:
Para resolver el problema, simplemente podemos almacenar varios pares clave-valor en el mismo índice. Así que modifiquemos nuestra tabla hash:
Como puede notar, aquí volvemos a nuestra implementación original: almacenamos una lista de pares clave-valor y recorremos cada uno de ellos. Esto será bastante lento cuando haya muchas colisiones para un índice particular de la lista.
Comparemos esto usando nuestra propia hash()función que genera índices del 1 al 10:
with lots of records in the map: 11.919msy usando la función hash de string-hash, que genera índices aleatorios:
with lots of records in the map: 0.014ms¡Guau! Existe el costo de elegir la función de hash correcta: lo suficientemente rápido como para que no ralentice nuestra ejecución por sí sola y lo suficientemente bueno como para que no produzca muchas colisiones.
Generalmente O (1)
¿Recuerdas mis palabras?
Las tablas hash tienen unaO(1)complejidad
Bueno, mentí: la complejidad de una tabla hash depende de la función hash que elija. Cuantas más colisiones genere, mayor será la tendencia a la complejidad O(n).
Una función hash como:
function hash(key) { return 0}significaría que nuestra tabla hash tiene una complejidad de O(n).
Es por eso que, en general, la complejidad computacional tiene tres medidas: escenarios mejor, promedio y peor de los casos. Las tablas hash tienen una O(1)complejidad en los escenarios mejores y promedio, pero caen O(n)en su peor escenario.
Recuerde: una buena función hash es la clave para una tabla hash eficiente , ni más ni menos.
Más sobre colisiones ...
La técnica que usamos para corregir DumbMapen caso de colisiones se llama encadenamiento separado: almacenamos todos los pares de claves que generan colisiones en una lista y los recorremos.
Otra técnica popular es el direccionamiento abierto:
- en cada índice de nuestra lista almacenamos un único par clave-valor
- al intentar almacenar un par en el índice
x, si ya hay un par clave-valor, intente almacenar nuestro nuevo par enx + 1 - si
x + 1se toma, pruebax + 2y así sucesivamente ... - al recuperar un elemento, hash la clave y ver si el elemento en esa posición (
x) coincide con nuestra clave - si no, intente acceder al elemento en la posición
x + 1 - enjuague y repita hasta que llegue al final de la lista, o cuando encuentre un índice vacío, eso significa que nuestro elemento no está en la tabla hash
Inteligente, simple, elegante y generalmente muy eficiente.
Preguntas frecuentes (o TL; DR)
¿Tiene una tabla hash los valores que estamos almacenando?
No, las claves tienen un hash para que se puedan convertir en un número entero i, y tanto las claves como los valores se almacenan en la posición ide una lista.
¿Las funciones hash utilizadas por las tablas hash generan colisiones?
Por supuesto, las tablas hash se implementan con estrategias de defensa para evitar errores desagradables.
¿Las tablas hash utilizan una lista o una lista vinculada internamente?
Depende, ambos pueden funcionar. En nuestros ejemplos, usamos la matriz de JavaScript ( []) que se puede cambiar de tamaño dinámicamente:
> a = []> a[3] = 1> a[ , 1 ]¿Por qué eligió JavaScript para los ejemplos? ¡Las matrices JS SON tablas hash!
Por ejemplo:
> a = [][]> a["some"] = "thing"'thing'> a[ some: 'thing' ]> typeof a'object'Lo sé, maldito JavaScript.
JavaScript es "universal" y probablemente el lenguaje más fácil de entender cuando se mira algún código de muestra. Puede que JS no sea el mejor lenguaje, pero espero que estos ejemplos sean lo suficientemente claros.
¿Es su ejemplo una implementación realmente buena de una tabla hash? ¿Es realmente TAN simple?
No, en absoluto.
Eche un vistazo a "implementar una tabla hash en JavaScript" de Matt Zeunert, ya que le dará un poco más de contexto. Hay mucho más que aprender, por lo que también te sugiero que consultes:
- Curso de Paul Kube sobre tablas hash
- Implementación de nuestra propia tabla hash con encadenamiento independiente en Java
- Algoritmos, cuarta edición - Tablas hash
- Diseñar una tabla hash rápida
En el final…
Las tablas hash son una idea muy inteligente que usamos de forma regular: no importa si crea un diccionario en Python, una matriz asociativa en PHP o un mapa en JavaScript. Todos comparten los mismos conceptos y funcionan maravillosamente para permitirnos almacenar y recuperar elementos mediante un identificador, a un costo (muy probablemente) constante.
Espero que hayas disfrutado de este artículo y no dudes en compartir tus comentarios conmigo.
Un agradecimiento especial para Joe, quien me ayudó al revisar este artículo.
¡Adiós!