a En el Python. para irse, o en JavaScript. agrupaciones asociativas en PHP, en C++. Los mapas hash se implementan en prácticamente todos los lenguajes de programación de alto nivel. Y son increíbles! ¿Quién no quiere almacenar y luego acceder a los datos en tiempo constante? Ya sea que estés trabajando con grandes conjuntos de datos o moldeando problemas de Leetcode, muy a menudo esta estructura de datos viene al rescate. Pero qué son exactamente, y cómo trabajan bajo el capó? En este artículo, intentaremos y responderemos a estas preguntas. dict map Object Map Dictionary<TKey, TValue> ¿Qué es un mapa hash? En un nivel alto, un mapa hash o tabla hash es una estructura de datos que implementa un tipo de datos abstracto de matriz asociativa, una estructura que puede mapear claves a valores. La clave se utiliza para identificar de forma única un valor en el mapa, y el valor es los datos que se están almacenando. De hecho, la complejidad promedio de tiempo para estas operaciones es O(1), lo que significa que se pueden realizar en tiempo constante! Esta característica hace que los mapas hash sean probablemente la estructura de datos más utilizada en la programación, sin embargo, hay algunas advertencias a este respecto, como veremos más adelante. La peor complejidad temporal para estas operaciones es O(n), que puede ocurrir en ciertos escenarios, y cuanto más sabemos sobre los internos, más probable es que estemos evitando estos escenarios. Según la : Artículo de Wikipedia Una tabla hash es una estructura de datos que implementa una matriz asociativa, también llamada diccionario o simplemente mapa; una matriz asociativa es un tipo de datos abstracto que mapea las claves a los valores.Una tabla hash utiliza una función hash para calcular un índice, también llamado código hash, en una matriz de buckets o ranuras, desde la cual se puede encontrar el valor deseado. Una tabla hash es una estructura de datos que implementa una matriz asociativa, también llamada diccionario o simplemente mapa; una matriz asociativa es un tipo de datos abstracto que mapea las claves a los valores.Una tabla hash utiliza una función hash para calcular un índice, también llamado código hash, en una matriz de buckets o ranuras, desde la cual se puede encontrar el valor deseado. Así que vamos a dar un paso atrás y mirar los componentes de un mapa hash. ¿Qué es una función hash? Una función hash es una función que toma una entrada (o "chave") y normalmente devuelve un número entero que se utiliza para indexar los datos en el mapa hash. La clave se transforma en un número entero, que se utiliza para determinar el índice en la matriz subyacente donde se almacena el valor. Una buena función hash tiene las siguientes propiedades: Determinismo: La misma entrada siempre produce la misma salida. Distribución uniforme: La función hash debe distribuir las claves uniformemente en toda la tabla hash para minimizar las colisiones. Computación rápida: La función hash debe ser rápida de calcular, incluso para entradas grandes. Minimizar las colisiones: El espacio de las claves posibles suele ser mucho más grande (a menudo infinito) que el espacio de los códigos de hash. Esto significa que diferentes claves pueden producir el mismo código de hash. Un ejemplo simple de una función hash es la operación modulo, que toma una clave y devuelve el resto cuando se divide por el tamaño de la tabla hash. , lo que significa que el valor asociado con la clave 23 se almacenaría en el índice 3 en la matriz subyacente. También, lo que significa que tenemos una colisión. En este caso, ambas claves mapearían al mismo índice en la matriz. 23 % 10 = 3 33 % 10 = 3 ¿Qué es un bucket? Un bucket es una ranura en la tabla hash donde se almacena un par de valores clave. En caso de una colisión, donde dos claves diferentes producen el mismo código hash, el bucket puede almacenar múltiples pares de valores clave. Esto a menudo se hace usando una lista vinculada u otra estructura de datos para manejar colisiones. Este diagrama ilustra cómo funciona todo esto: y Aquí podemos ver cómo la función hash mapea las claves a los índices en la matriz subyacente. Las claves 23 y 33 ambos producen el mismo código hash de 3, lo que significa que se almacenan en el mismo cubo. El cubo puede entonces almacenar ambos pares de valores clave, pero cuando recuperamos un valor, necesitamos comprobar las claves en el cubo para encontrar el correcto. Esto es donde la complejidad del tiempo puede aumentar a O(n) en el peor caso, si muchas (o incluso todas) claves se chocan y se almacenan en el mismo cubo. Factor de carga El factor de carga es una medida de cuán completa es la tabla hash. Se calcula como el número de elementos en la tabla hash dividido por el número de buckets (o ranuras) en la matriz subyacente. Un factor de carga más alto significa que hay más elementos en la tabla hash en relación al número de buckets, lo que puede conducir a más colisiones y rendimiento más lento. Resolución de colisión Cuando dos claves producen el mismo código hash, tenemos una colisión.Hay varias estrategias para manejar colisiones en mapas hash: : In this method, each bucket contains a linked list (or another data structure) of all key-value pairs that hash to the same index. When a collision occurs, the new key-value pair is simply added to the list in the appropriate bucket. This is the most common method for handling collisions. Chaining : Average O(1) for all operations, worst-case O(n) if all keys hash to the same bucket Complexity : Simple to implement, handles high load factors well, deletion is straightforward Pros : Extra memory overhead for pointers, poor cache performance due to scattered memory access Cons Open Addressing: En este método, cuando se produce una colisión, la tabla hash busca el siguiente slot disponible en la matriz para almacenar el nuevo par de valores clave. Si se produce una colisión, el algoritmo comprueba la próxima ranura en la matriz hasta encontrar una vacía. Linear Probing Complejidad: Media O(1), peor O(n) debido a la agrupación primaria Pros: Implementación simple, buen rendimiento de caché para accesos cercanos Desventajas: Clustering primario (slots ocupados consecutivos), degradación del rendimiento con el clustering : En lugar de comprobar la próxima ranura, verifica las ranuras a distancias crecientes (1, 4, 9, etc.) del índice original. Quadratic Probing Complejidad: Media O(1), mejor que la sonda lineal debido a la reducción del agrupamiento Ventajas: Reduce el agrupamiento primario en comparación con el sondeo lineal, aún cache-friendly Desventajas: Clustering secundario (claves con el mismo hash siguen la misma secuencia de sonda), puede que no visite todas las ranuras : Utiliza una segunda función hash para determinar el tamaño de paso para la detección. A diferencia de la detección lineal que siempre se mueve al siguiente slot, o la detección cuadrada que utiliza una secuencia fija, la detección doble calcula un tamaño de paso único para cada clave. dónde La segunda función hash debe devolver un valor que sea relativamente primario al tamaño de la tabla para asegurar que todos los ranuras puedan ser visitados. y , entonces examinaríamos los índices 7, 10, 13, 16 etc. Double Hashing index = (hash1(key) + i * hash2(key)) % table_size i hash1(key) = 7 hash2(key) = 3 : Average O(1), best performance among open addressing methods Complexity : Minimizes clustering, uniform distribution of probe sequences, visits all slots when properly implemented Pros : More complex implementation, requires computing two hash functions, and slightly more overhead per operation Cons : If the load factor becomes too high, the hash table can be resized and all existing key-value pairs can be rehashed into the new table. This helps to maintain efficient performance as the number of elements grows. Rehashing : O(n) for the rehashing operation itself, but amortizes to O(1) per insertion over time Complexity : Maintains optimal performance by keeping the load factor low, prevents performance degradation Pros : Temporary performance spike during rehashing, requires additional memory during the resize operation Cons Cada uno de estos métodos tiene sus propios compromisos en términos de complejidad, rendimiento y uso de la memoria.La elección de la estrategia de resolución de colisión puede tener un impacto significativo en el rendimiento general del mapa hash. Aquí está un breve resumen de los pros y contras de cada método de resolución de colisión: Feature Chaining Linear Probing Quadratic Probing Double Hashing Average Time Complexity O(1) O(1) O(1) O(1) Worst-case Time Complexity O(n) O(n) O(n) O(n) Memory Overhead High (pointers) Low Low Low Cache Performance Poor Good Good Moderate Implementation Complexity Simple Simple Moderate Complex Clustering Issues None Primary clustering Secondary clustering Minimal Load Factor Tolerance High (>1.0) Low (<0.7) Low-Medium (<0.7) Medium (<0.8) Deletion Complexity Simple Complex (tombstones) Complex (tombstones) Complex (tombstones) Space Efficiency Lower Higher Higher Higher Performance Degradation Gradual Rapid at high load Moderate at high load Slow at high load Hash Function Requirements One One One Two Best Use Cases Unknown load factors, frequent deletions Cache-friendly applications, low load Better than linear, moderate load High performance, predictable load Average Time Complexity O (1) O (1) O (1) O (1) Worst-case Time Complexity O(n) O(n) O(n) O(n) Memory Overhead Los puntos altos (pointers) Bajo Bajo Bajo Cache Performance Pobre bueno Good moderado Implementation Complexity sencillo sencillo moderado Complejo Clustering Issues Ninguno Clúster Primario Clúster secundario El mínimo Load Factor Tolerance Más alto (>1.0) Bajo nivel (< 0,7) Bajo nivel medio (<0.7) Mediana (< 0,8) Deletion Complexity sencillo El complejo (Tombstones) El complejo (Tombstones) El complejo (Tombstones) Space Efficiency Bajo más alto más alto más alto Performance Degradation Gradualmente Rápido en alta carga Moderado en alta carga Lenta en alta carga Hash Function Requirements Una Una Una dos Best Use Cases Factores de carga desconocidos, supresiones frecuentes Aplicaciones cache-friendly, baja carga Mejor que la carga lineal y moderada Alto rendimiento, carga previsible Algunos ejemplos del mundo real Implementación de lenguajes de programación Muchos lenguajes de programación tienen mapas hash incorporados.Estas implementaciones a menudo utilizan una combinación de las técnicas descritas anteriormente para proporcionar un rendimiento eficiente y manejar colisiones de manera efectiva. El dict de Python utiliza la dirección abierta con sondado aleatorio, rehashing cuando el factor de carga supera aproximadamente 0,66. HashMap de Java utiliza la cadena con listas vinculadas (convertir a árboles equilibrados para buckets grandes en Java 8+), rehashes a 0.75 factor de carga. El mapa de C++ normalmente utiliza la cadena, pero las implementaciones pueden variar. Sistemas de bases de datos Los mapas hash también se utilizan ampliamente en la indexación de bases de datos. Muchos sistemas de bases de datos utilizan índices hash para acelerar la recuperación de datos. Estos índices permiten búsquedas rápidas al hashar las columnas indexadas y almacenar los pares de valores clave resultantes en una tabla hash. Cuando se ejecuta una consulta, la base de datos puede encontrar rápidamente las filas pertinentes calculando el hash de la clave de la consulta y mirándola en el índice hash. Algunos sistemas de bases de datos populares que utilizan la indexación de hash incluyen: PostgreSQL: soporta los índices de hash, pero no son tan comunes como los índices de árboles B. MongoDB: Utiliza índices de hash para el sharding y para apoyar consultas de igualdad en campos hashados. Redis: Implementa mapas hash como una estructura de datos central, permitiendo un almacenamiento y recuperación eficientes de pares de valores clave. Estas implementaciones a menudo aprovechan los mismos principios subyacentes de hashing y resolución de colisión discutidos anteriormente, pero también pueden incorporar optimizaciones adicionales específicas para el contexto de la base de datos. Control de Versiones Los sistemas de control de versiones como Git utilizan mapas hash para gestionar de manera eficiente los cambios de archivos y rastrear las versiones. Cada comité en Git es identificado por un hash SHA-1 de su contenido, que sirve como una clave única para el objeto de comité. Esto permite a Git buscar rápidamente comités, ramas y otros objetos en el repositorio. Putting It All Together: How Implementation Knowledge Matters Entender cómo se implementan los mapas hash en el lenguaje de programación de su elección puede conducir a mejoras significativas en el rendimiento de su código. Por ejemplo, desde Python utiliza la dirección abierta con el manejo de cuerdas optimizado, entendiendo esto puede conducir a un mejor rendimiento.Aquí está cómo escribir código eficiente vs ineficiente: dict Bad Implementation (Luchando contra el Dictado de Python) def count_words_bad(text): word_counts = {} words = text.split() for word in words: # This is inefficient with open addressing! if word in word_counts: # First lookup word_counts[word] += 1 # Second lookup + assignment else: word_counts[word] = 1 # Third lookup + assignment return word_counts Entrar en modo de pantalla completa Salir en modo de pantalla completa Problems: Múltiples búsquedas de hash por palabra (hasta 3!) La dirección abierta hace que los cheques sin clave sean caros No aprovecha las optimizaciones de dict de Python Buena implementación (Funciona con el dictado de Python) from collections import defaultdict, Counter def count_words_good_v1(text): # defaultdict eliminates key existence checks word_counts = defaultdict(int) words = text.split() for word in words: word_counts[word] += 1 # Single operation! return dict(word_counts) def count_words_good_v2(text): # Counter is optimized specifically for Python's dict implementation words = text.split() return Counter(words) def count_words_good_v3(text): # dict.get() with default avoids the membership test word_counts = {} words = text.split() for word in words: word_counts[word] = word_counts.get(word, 0) + 1 # Single lookup return word_counts Entrar en modo de pantalla completa Salir en modo de pantalla completa Why These Are Better: Una operación de hash por palabra en lugar de múltiples Aprovecha la optimización de cuerdas de Python - las claves de cuerdas se manejan de manera muy eficiente Funciona con la dirección abierta - menos operaciones de exploración necesarias Utiliza optimizaciones integradas como Counter que está ajustado para la implementación de Python Diferencia de rendimiento La buena implementación es a menudo 2-3 veces más rápida, simplemente por entender y trabajar con la implementación de dict de Python en lugar de contra ella! Typical Results: Conclusión Hash maps are among the most fundamental and powerful data structures in computer science, providing near-constant time access to data that makes them indispensable in modern programming. Throughout this deep dive, we've explored how they achieve their remarkable O(1) average performance through clever use of hash functions, strategic collision resolution, and careful load factor management. La idea clave es que la "magia" de los mapas hash no es realmente mágica en absoluto - es el resultado de algoritmos bien diseñados y estructuras de datos que trabajan juntos. Key Takeaways: Las funciones hash son la base: determinan cómo los datos se distribuyen uniformemente y afectan directamente a las tasas de colisión. Las estrategias de resolución de colisiones tienen diferentes compromisos: cadena para la simplicidad y la robustez, acceso abierto para la eficiencia de la memoria y el rendimiento de la caché. La gestión del factor de carga a través del rehashing evita la degradación del rendimiento a medida que crecen los mapas hash El conocimiento de la implementación se traduce en ganancias reales en el rendimiento: comprender si su idioma utiliza cadena o dirección abierta puede hacer que su código sea 2-3 veces más rápido. Ya sea que estés optimizando un script de Python, debugando problemas de rendimiento en Java o tomando decisiones arquitectónicas para un sistema de bases de datos, esta comprensión de los internos de HashMap te da las herramientas para tomar decisiones informadas. , de , o Conocerás exactamente lo que está sucediendo bajo el capó y cómo aprovechar al máximo estas increíbles estructuras de datos. dict HashMap unordered_map Los mapas de hash son realmente increíbles - y ahora sabes por qué!
