Esta es la segunda parte de la serie sobre cómo elegir el contenedor asociativo (diccionario) más adecuado en C++23. En la primera parte, abordamos los contenedores ordenados y, en esta parte, analizaremos en detalle los no ordenados.

Contenedores desordenados

Estos contenedores no proporcionan ningún orden definido para sus claves. Además, el orden de las claves puede cambiar con cada modificación, por lo que el programa nunca debería depender de él. Estos contenedores siempre se implementan como mapas hash.

Generalmente, al agregar, eliminar o buscar una clave, un mapa hash primero calcula un valor hash integral de esa clave usando la función hash. Luego, el hash (o más bien su parte) se usa como índice en la matriz preasignada contigua. Cada entrada en esta matriz se llama bucket . Algunas entradas en esa matriz estarán vacías, algunas contendrán un solo elemento y algunas podrían asignarse a más de un elemento debido a colisiones hash. Esto sucede cuando diferentes claves tienen valores hash que apuntan al mismo índice de matriz. Los mapas hash utilizan varias estrategias para lidiar con las colisiones hash (vea este artículo de Wikipedia ). La cantidad de elementos en el mapa hash dividido por el tamaño total de la matriz se llama factor de carga . Cuanto mayor sea el factor de carga, más posibles serán las colisiones hash con cada elemento recién insertado.

A diferencia de los contenedores ordenados, los mapas hash no admiten consultas de rango, operaciones de clasificación/selección, iteración sobre claves en orden y búsqueda de la clave más pequeña/más grande que la clave dada. A cambio, los mapas hash alcanzan el mejor rendimiento alcanzable: la complejidad temporal de las operaciones de búsqueda/inserción/eliminación se amortiza O(1) . Digo "amortizado" aquí, porque cuando el número de elementos se vuelve demasiado grande, un mapa hash necesita volver a hacer un hash de su contenido para reducir el factor de carga (haciendo crecer efectivamente la matriz de contenedores). La complejidad temporal del rehashing es O(n) . Sin embargo, se espera que suceda raramente, por lo que, en promedio, cada operación sigue siendo O(1) . Otra razón para un rendimiento potencialmente reducido es una función hash con una distribución deficiente, que aumentará la frecuencia de colisiones.

Mapas hash estándar

A partir de C++11, la biblioteca estándar proporciona los siguientes mapas hash: std::unordered_map ( link ), std::unordered_set ( link ), std::unordered_multimap ( link ) y std::unordered_multiset ( link ). Los mapas asocian una clave con el valor, mientras que los conjuntos solo almacenan la clave y son útiles para verificar si la clave está presente en el contenedor, pero no recuperan el valor asociado. Los contenedores múltiples permiten almacenar múltiples claves duplicadas.

Todos los contenedores desordenados estándar se basan en nodos y utilizan encadenamiento independiente para lidiar con las colisiones de hash, lo que significa que almacenan cada clave o par clave-valor en un nodo de lista enlazada independiente. La memoria para cada nuevo nodo se asigna individualmente, lo que no es particularmente eficiente. Esto también hace que la estructura de datos no sea amigable con la memoria caché de la CPU, porque cada acceso a la clave requiere indirección adicional. Así es como podría verse la estructura interna unordered_map :

A la izquierda, hay una matriz de contenedores, que está preasignada a un tamaño fijo ( 8 en nuestro ejemplo). Inicialmente, todos los contenedores están vacíos. Cuando comenzamos a agregar elementos al mapa hash, algunos contenedores se ocuparán. En el ejemplo anterior, hay un elemento con clave 10 (que llegó al contenedor 1 ) y dos elementos con claves 50 y 256 , ambos terminaron en el mismo contenedor 3 porque sus valores hash colisionaron. También hay un elemento con clave 3 , que aterrizó en el contenedor 6 Cada contenedor apunta a la lista enlazada, que idealmente no contiene más de un elemento. Los contenedores 0 , 2 , 4 , 5 y 7 están vacíos y apuntan a nullptr .

Supongamos que necesitamos encontrar el valor de la clave 256 .

• En primer lugar, el mapa calcula el hash de la clave y obtiene el resto al dividir el valor del hash por la cantidad total de contenedores ( 8 en nuestro caso). En nuestro ejemplo, el valor del resto es 3 .
• Luego, el mapa comienza a leer elementos de la lista enlazada a la que apunta el contenedor 3 .
• El primer elemento tiene la clave 50 , que no es la misma que la 256 que buscamos, por lo que el mapa seguirá iterando. El siguiente elemento tiene la clave 256 , que es exactamente la que necesitamos. El valor correspondiente es xyz .
• Si la clave no estuviera en el diccionario, el mapa llegaría a un contenedor vacío o iteraría sobre la lista enlazada hasta el final. En ambos casos, el mapa devolvería un iterador end , lo que indicaría que la clave no existe.

Es posible que notes que el último elemento de cada lista apunta al primer elemento de la siguiente lista. Esto se hace en algunas implementaciones para mejorar la eficiencia de la iteración. En lugar de verificar cada elemento por separado al iterar sobre todos los elementos del mapa hash, podemos usar esas conexiones para saltar de una lista enlazada no vacía a otra mucho más rápido.

Si continuamos agregando más elementos al mapa hash anterior, en algún momento el factor de carga será demasiado alto (por ejemplo, 80 %) y el mapa hash decidirá volver a realizar el hash. Aumentará la matriz preasignada (por ejemplo, de 8 a 16 elementos), volverá a calcular los hashes para todos los elementos existentes y colocará los elementos en los nuevos contenedores.

Los contenedores estándar proporcionan garantías de estabilidad de referencias e iteradores, pero son más débiles que las que ofrecen los contenedores ordenados. Las referencias a los elementos existentes nunca se invalidan. Los iteradores a los elementos existentes solo se pueden invalidar cuando la adición de un nuevo elemento provoca un refrito o cuando el refrito se activa manualmente:

 #include <iostream> #include <unordered_map> int main() { std::unordered_map<std::string, int> map{ {"test", 123}, {"xyz", 456}, {"abc", 10} }; auto& value = map["abc"]; auto valueIt = map.find("abc"); // Might cause a rehash if the load factor // is too high map.emplace("zzz", 1000); // Triggers the rehash manually map.rehash(1000); // References remain valid in any case: std::cout << value << "\n"; // Iterators are invalidated: the line below // is undefined behavior and might crash std::cout << valueIt->second << "\n"; }

Desde C++17, los contenedores no ordenados permiten la manipulación de nodos: es posible tomar un nodo de un mapa y moverlo a otro mapa sin copiar la clave y el valor:

 #include <iostream> #include <unordered_map> int main() { std::unordered_map<std::string, int> map1{ {"test", 123}, {"xyz", 456}, {"abc", 10} }; // Take the node from map1: auto node = map1.extract("xyz"); // We can even change its key // (we can also change the value // if needed): node.key() = "xyzxyz"; std::unordered_map<std::string, int> map2; // Insert the node into another map: map2.insert(std::move(node)); // Prints "xyzxyz: 456": for (const auto& [k, v] : map2) { std::cout << k << ": " << v << "\n"; } }

Esto es lo que sucede en el programa anterior:

Otra estrategia para lidiar con las colisiones de hash se llama direccionamiento abierto . En los mapas hash de direccionamiento abierto, cada contenedor almacena como máximo un elemento. Si el contenedor ya está ocupado, el elemento con el mismo valor hash va a otro contenedor libre. Estos mapas hash intentan agrupar elementos en bloques de memoria contiguos para mejorar la eficiencia y hacer que la estructura de datos sea más amigable con la caché de la CPU. La biblioteca estándar de C++ no proporciona mapas hash de direccionamiento abierto, pero existen muchas alternativas de terceros.

Mapas hash de terceros

Boost.Unordered es una increíble biblioteca que proporciona una amplia gama de implementaciones de mapas hash.

Existen boost::unordered_set , boost::unordered_map , boost::unordered_multiset y boost::unordered_multimap , que son análogos de los contenedores std , y todo lo escrito anteriormente se aplica a ellos. Estos contenedores utilizan una estructura interna un poco más compleja con "grupos de contenedores" para mejorar la eficiencia de la iteración.

La biblioteca también proporciona boost::unordered_node_set , boost::unordered_node_map , boost::unordered_flat_set y boost::unordered_flat_map , que son contenedores de direccionamiento abierto. La estructura interna es diferente de las variantes de direccionamiento abierto:

Puedes leer más sobre la estructura interna en esta entrada del blog .

Los contenedores basados en nodos ( boost::unordered_node_set , boost::unordered_node_map ) siguen utilizando nodos, a los que apuntan los contenedores. Estos contenedores proporcionan la misma estabilidad de iteración y referencia garantizada que los contenedores std y también proporcionan la misma API para la manipulación de nodos (es decir, el método extract ).

En los contenedores planos ( boost::unordered_flat_set , boost::unordered_flat_map ), las claves y los valores se almacenan directamente en la matriz de contenedores. Los contenedores planos son los más eficientes, pero ofrecen las garantías más débiles: los iteradores y las referencias a todos los elementos se invalidan cuando se realiza un rehashing. No se proporciona ninguna API de manipulación de nodos. Los contenedores planos pueden utilizar más memoria que los basados en nodos, especialmente si la clave o el valor sizeof son grandes.

Otra biblioteca de terceros que implementa contenedores de direccionamiento abierto es Folly F14 (proporcionada por Meta). Hay algunas variantes de diccionario que son muy similares a los contenedores de la biblioteca Boost descritos anteriormente:

• folly::F14NodeSet es lo mismo que boost::unordered_node_set , folly::F14NodeMap es lo mismo que boost::unordered_node_map .
• folly::F14ValueSet es lo mismo que boost::unordered_flat_set , y folly::F14ValueMap es lo mismo que boost::unordered_flat_map .
• folly::F14VectorMap / folly::F14VectorSet mantienen las claves/valores empaquetados en una matriz contigua, y los contenedores contienen índices en esa matriz.
• folly::F14FastMap / folly::F14FastSet es una clase general. Elige la implementación más eficiente (ya sea F14Value o F14Vector ) en función de los parámetros que especifique (como los tipos de clave y valor).

Una característica interesante de eficiencia adicional de los mapas hash F14 es el prehashing . Por ejemplo, si necesita buscar la misma clave varias veces y su hash es costoso (por ejemplo, una clave es una cadena), puede prehashearla una vez y luego usar F14HashToken en todas las llamadas de mapas hash posteriores para evitar volver a hacer hash de la misma clave varias veces. El punto de partida es el método prehash ( enlace ).

Puedes leer más sobre la estructura interna de los contenedores hash F14 en esta publicación del blog de FB .

La biblioteca Abseil Swiss Tables (proporcionada por Google) también implementa contenedores de hash planos y basados en nodos de direccionamiento abierto: absl::flat_hash_map , absl::flat_hash_set , absl::node_hash_map , absl::node_hash_set . Son similares a los de Boost y F14. Puedes leer más sobre ellos aquí y aquí .

Una biblioteca ankerl menos conocida ( github ) afirma ser muy eficiente en la mayoría de los escenarios. El autor de esta biblioteca proporciona resultados de evaluación comparativa extensos para muchos mapas hash en diferentes casos de uso ( publicación de blog ). Puede seguir estos resultados, pero tómelos con pinzas. Pruebe siempre el mapa hash que elija en el entorno de producción. Las evaluaciones comparativas son siempre sintéticas y no cubren los casos en los que la CPU y la memoria realizan otro trabajo además de las operaciones del mapa hash. Las evaluaciones comparativas tampoco cubren los casos en los que varias partes de la memoria del mapa hash no están en la memoria caché de la CPU, lo que sucederá con frecuencia en programas reales.

Calidad de la función hash

La calidad de la función hash es importante para mantener la complejidad temporal de las operaciones de búsqueda O(1) . Los mapas hash planos son particularmente sensibles a la calidad de la función hash. Una función hash ideal se puede definir de la siguiente manera: si cambia un solo bit de la clave, el valor hash correspondiente cambiará la mitad de sus bits de forma aleatoria. Dicha función hash se denomina avalancha .

Lamentablemente, algunas implementaciones de funciones hash de punteros y enteros de la biblioteca estándar de C++ no son de avalancha. Por ejemplo, libstdc++ simplemente devuelve el valor de puntero o entero directamente sin ninguna transformación adicional: github .

Las tablas hash avanzadas, como las implementaciones boost y F14 , se ocupan de este problema introduciendo el rasgo hash_is_avalanching . Si la función hash no se declara como avalanching, la tabla hash realizará un paso de mezcla adicional para mejorar la calidad del hash. Esto tiene un costo adicional. Si implementa una función hash personalizada y sabe que tiene una calidad decente, puede marcarla como avalanching como se muestra en este ejemplo . Boost usa el nombre de propiedad is_avalanching y la propiedad F14 se llama folly_is_avalanching . Lo ideal es que agregue ambos.

Si utiliza los tipos de clave admitidos de fábrica (por ejemplo, string , int , punteros) y las funciones hash predeterminadas proporcionadas por boost o F14 , ya estarán marcados correctamente como necesarios y no necesitará pensar en esto a menos que decida implementar un tipo de clave personalizado, que necesitará una función hash personalizada.

Seguridad de los hilos

En general, todos los contenedores anteriores no son seguros para subprocesos y deberá implementar una sincronización externa (por ejemplo, usando mutex) si un subproceso puede modificar el mapa hash cuando otro subproceso accede a él.

Si todos los subprocesos solo leen el mapa, no se necesita sincronización. Asegúrese de llamar solo a los métodos marcados con const . Todos los métodos que no sean const pueden modificar el contenedor. Tenga en cuenta que operator[] no es const y modificará el contenedor. Un error común en el código multiproceso es:

 std::unordered_map<std::string, bool> map; // ... if (map["key"]) { // ... }

En el código anterior, el objetivo es comprobar si el valor correspondiente a la key es true . Sin embargo, map["key"] añadirá la key al map si aún no está allí. El valor recién añadido se establecerá en el valor predeterminado ( false en el ejemplo anterior). Esto significa que dicho código no es seguro para subprocesos y no es demasiado óptimo. Una forma más eficiente y segura para subprocesos de comprobar la misma condición es la siguiente:

 if (auto it = map.find("key"); it != map.end() && it->second == true) { // ... }

• Aquí, primero obtenemos el iterador al elemento identificado por la "clave".
• Luego verificamos si el elemento existe en el mapa ( it != map.end() ).
• Si es así, finalmente verificamos su valor ( it->second == true ).

En este ejemplo, find y end no modifican el mapa y la búsqueda se vuelve segura para subprocesos. Si el objetivo solo fuera verificar si la clave existe en el mapa, simplemente podrías llamar a map.contains("key") .

Mapas desordenados seguros para subprocesos

Hay algunas implementaciones de mapas hash seguros para subprocesos.

• Una opción es boost::concurrent_flat_set y boost::concurrent_flat_map de la biblioteca Boost.Unordered . Los contenedores Boost proporcionan una API basada en visitas que es muy diferente de la API proporcionada por la biblioteca estándar de C++.
• Otra opción es folly::ConcurrentHashMap ( github ). Folly intenta mantener su API lo más cercana posible a los contenedores desordenados estándar de C++.
• libcds es una gran biblioteca de contenedores sin bloqueos que proporciona varias implementaciones de mapas hash sin bloqueos (por ejemplo, MichaelHashMap , SkipListMap , SkipListSet , FeldmanHashMap , FeldmanHashSet ). Esta biblioteca no se ha actualizado durante un tiempo y no proporciona documentación detallada, pero aún así la comparto porque los contenedores que ofrece son únicos. Si su caso de uso implica una alta contención en un mapa hash, pruebe estos diccionarios sin bloqueos que ofrece libcds .
• Si la eficiencia no es una preocupación, puede sincronizar los accesos a mapas no seguros para subprocesos mediante mutex. Como alternativa, puede evitar por completo los accesos simultáneos, lo que suele ser más eficiente que usar contenedores seguros para subprocesos o agregar sincronización.

¿Cual uso?

Veamos los puntos resumidos que explican cómo elegir el contenedor más adecuado.

• Si necesita asociar una clave con el valor, elija un mapa ; de lo contrario, utilice un conjunto .
• Si es necesario mantener claves duplicadas en el mapa, utilice contenedores múltiples .
• Si necesita las garantías de estabilidad de referencia e iterador más estrictas posibles, utilice contenedores basados en nodos std , boost , folly o abseil (como std::unordered_map , boost::unordered_map , boost::unordered_node_map o folly::F14NodeMap ). boost::unordered_node_... y folly probablemente serán los más eficientes.
• Si la estabilidad del iterador y de la referencia no es importante (lo que significa que no almacena iteradores, referencias o punteros a elementos del mapa/conjunto externamente o no espera que sigan siendo válidos después de que se modifique el mapa), elija un contenedor plano (como boost::unordered_flat_map o folly::F14FastMap ).
• Los contenedores planos utilizan más memoria que los basados en nodos, especialmente cuando sizeof de la clave o el valor es grande. Si el uso de la memoria es un problema, utilice contenedores basados en nodos.
• Los contenedores F14 proporcionan una función de prehashing para una mayor eficiencia. Si busca, agrega o elimina claves idénticas varias veces, F14 le permitirá ahorrar en el costo de hash al prehashingar las claves.
• Todos los puntos anteriores se aplican al uso de contenedores de un solo subproceso (o acceso de lectura de múltiples subprocesos sin modificaciones simultáneas). Si se requieren modificaciones de múltiples subprocesos, seleccione una de las opciones seguras para subprocesos que se enumeran arriba. Pueden mostrar un rendimiento variable en el código de producción real, por lo que debe considerar probarlas en su aplicación y comparar los resultados.