¿Cómo determina std::unordered_map la ubicación de una clave específica en una tabla hash?
La documentación menciona que std::unordered_map utiliza una tabla hash. ¿Cómo logra una búsqueda de complejidad O(1) de una clave específica en la tabla hash? La única forma que se me ocurre es almacenando cada clave en una dirección calculada a partir del valor hash de los datos que contiene. Si este es el caso, ¿cómo mantiene todas las claves juntas en la memoria de manera que no se agoten rápidamente? Además, ¿qué sucede si se utilizan más de un std::unordered_map? ¿Cómo garantiza la implementación que no se calcularán hashes que se resuelvan a la misma dirección para dos mapas diferentes?
davy.ai
std::unordered_maplogra una búsqueda O(1) de una clave específica mediante el uso de una estructura de datos de tabla hash. Cada par clave-valor se asigna a un cubo en la tabla hash utilizando una función hash que calcula un valor hash único para cada clave. Al buscar una clave específica, se utiliza la función hash para calcular el valor hash de la clave, que luego se utiliza para ubicar el cubo correspondiente en la tabla hash. Una vez que se encuentra el cubo, se puede acceder al par clave-valor en tiempo constante, logrando así un tiempo de búsqueda O(1).Para almacenar cada clave en una dirección calculada a partir del valor hash,
std::unordered_maputiliza una técnica llamada direccionamiento abierto. En el direccionamiento abierto, cada cubo en la tabla hash contiene un par clave-valor, y si un valor hash se asigna a un cubo que ya está ocupado, el mapa explora los cubos siguientes hasta encontrar un cubo vacío. De esta manera, las claves que tienen el mismo valor hash se almacenan cerca unas de otras en memoria, pero no necesariamente consecutivas.Cuando se utilizan más de un
std::unordered_map, la implementación garantiza que ningún par de mapas calculará hashes que se reduzcan a la misma dirección mediante el uso de una técnica llamada encadenamiento separado. En el encadenamiento separado, los cubos de la tabla hash contienen listas enlazadas de pares clave-valor, y si un valor hash se asigna a un cubo que ya está ocupado, el par clave-valor se agrega a la lista enlazada. Las diferentes instancias destd::unordered_mappueden tener diferentes funciones hash, por lo que incluso si dos mapas tienen las mismas claves, es probable que sus valores hash sean diferentes y se almacenarán en cubos diferentes.