Esta es la segunda parte de la serie sobre cómo elegir el contenedor asociativo (diccionario) más adecuado en C++23. y, en esta parte, analizaremos en detalle los no ordenados. En la primera parte, abordamos los contenedores 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 . 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 ). La cantidad de elementos en el mapa hash dividido por el tamaño total de la matriz se llama . Cuanto mayor sea el factor de carga, más posibles serán las colisiones hash con cada elemento recién insertado. bucket este artículo de Wikipedia factor de carga 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 . 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 . Sin embargo, se espera que suceda raramente, por lo que, en promedio, cada operación sigue siendo . Otra razón para un rendimiento potencialmente reducido es una función hash con una distribución deficiente, que aumentará la frecuencia de colisiones. amortiza O(1) O(n) O(1) Mapas hash estándar A partir de C++11, la biblioteca estándar proporciona los siguientes mapas hash: ( ), ( ), ( ) y ( ). asocian una clave con el valor, mientras que 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 permiten almacenar múltiples claves duplicadas. std::unordered_map link std::unordered_set link std::unordered_multimap link std::unordered_multiset link Los mapas los conjuntos múltiples Todos los contenedores desordenados estándar se basan en nodos y utilizan 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 : encadenamiento independiente unordered_map A la izquierda, hay una matriz de contenedores, que está preasignada a un tamaño fijo ( 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 (que llegó al contenedor ) y dos elementos con claves y , ambos terminaron en el mismo contenedor porque sus valores hash colisionaron. También hay un elemento con clave , que aterrizó en el contenedor Cada contenedor apunta a la lista enlazada, que idealmente no contiene más de un elemento. Los contenedores , , , y están vacíos y apuntan a . 8 10 1 50 256 3 3 6 0 2 4 5 7 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 ( en nuestro caso). En nuestro ejemplo, el valor del resto es . 8 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 , que no es la misma que la que buscamos, por lo que el mapa seguirá iterando. El siguiente elemento tiene la clave , que es exactamente la que necesitamos. El valor correspondiente es . 50 256 256 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 , lo que indicaría que la clave no existe. end 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 será demasiado alto (por ejemplo, 80 %) y el mapa hash decidirá volver a realizar el hash. Aumentará la matriz preasignada (por ejemplo, de a elementos), volverá a calcular los hashes para todos los elementos existentes y colocará los elementos en los nuevos contenedores. factor de carga 8 16 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 . 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. direccionamiento abierto Mapas hash de terceros es una increíble biblioteca que proporciona una amplia gama de implementaciones de mapas hash. Boost.Unordered Existen , , y , que son análogos de los contenedores , 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. boost::unordered_set boost::unordered_map boost::unordered_multiset boost::unordered_multimap std La biblioteca también proporciona , , y , que son contenedores de direccionamiento abierto. La estructura interna es diferente de las variantes de direccionamiento abierto: boost::unordered_node_set boost::unordered_node_map boost::unordered_flat_set boost::unordered_flat_map Puedes leer más sobre la estructura interna . en esta entrada del blog Los contenedores basados en nodos ( , ) siguen utilizando nodos, a los que apuntan los contenedores. Estos contenedores proporcionan la misma estabilidad de iteración y referencia garantizada que los contenedores y también proporcionan la misma API para la manipulación de nodos (es decir, el método ). boost::unordered_node_set boost::unordered_node_map std extract En los contenedores planos ( , ), 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 son grandes. boost::unordered_flat_set boost::unordered_flat_map sizeof Otra biblioteca de terceros que implementa contenedores de direccionamiento abierto es (proporcionada por Meta). Hay algunas variantes de diccionario que son muy similares a los contenedores de la biblioteca Boost descritos anteriormente: Folly F14 es lo mismo que , es lo mismo que . folly::F14NodeSet boost::unordered_node_set folly::F14NodeMap boost::unordered_node_map es lo mismo que , y es lo mismo que . folly::F14ValueSet boost::unordered_flat_set folly::F14ValueMap boost::unordered_flat_map / mantienen las claves/valores empaquetados en una matriz contigua, y los contenedores contienen índices en esa matriz. folly::F14VectorMap folly::F14VectorSet / es una clase general. Elige la implementación más eficiente (ya sea o ) en función de los parámetros que especifique (como los tipos de clave y valor). folly::F14FastMap folly::F14FastSet F14Value F14Vector Una característica interesante de eficiencia adicional de los mapas hash F14 es . 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 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 ( ). el prehashing F14HashToken prehash enlace Puedes leer más sobre la estructura interna de los contenedores hash F14 en . esta publicación del blog de FB (proporcionada por Google) también implementa contenedores de hash planos y basados en nodos de direccionamiento abierto: , , , . Son similares a los de Boost y F14. Puedes leer más sobre ellos y . La biblioteca Abseil Swiss Tables absl::flat_hash_map absl::flat_hash_set absl::node_hash_map absl::node_hash_set aquí aquí Una biblioteca menos conocida ( ) 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 ( ). 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. ankerl github publicación de blog 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 . 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 . O(1) avalancha Lamentablemente, algunas implementaciones de funciones hash de punteros y enteros de la biblioteca estándar de C++ no son de avalancha. Por ejemplo, simplemente devuelve el valor de puntero o entero directamente sin ninguna transformación adicional: . libstdc++ github Las tablas hash avanzadas, como las implementaciones y , se ocupan de este problema introduciendo el rasgo . 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 . Boost usa el nombre de propiedad y la propiedad F14 se llama . Lo ideal es que agregue ambos. boost F14 hash_is_avalanching este ejemplo is_avalanching folly_is_avalanching Si utiliza los tipos de clave admitidos de fábrica (por ejemplo, , , punteros) y las funciones hash predeterminadas proporcionadas por o , 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. string int boost F14 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 . Todos los métodos que no sean pueden modificar el contenedor. Tenga en cuenta que no es y modificará el contenedor. Un error común en el código multiproceso es: const const operator[] const 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 es . Sin embargo, la al si aún no está allí. El valor recién añadido se establecerá en el valor predeterminado ( 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: key true map["key"] añadirá key map false 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, y 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 . find end map.contains("key") Mapas desordenados seguros para subprocesos Hay algunas implementaciones de mapas hash seguros para subprocesos. Una opción es y de la . Los contenedores Boost proporcionan una API basada en visitas que es muy diferente de la API proporcionada por la biblioteca estándar de C++. boost::concurrent_flat_set boost::concurrent_flat_map biblioteca Boost.Unordered Otra opción es ( ). Folly intenta mantener su API lo más cercana posible a los contenedores desordenados estándar de C++. folly::ConcurrentHashMap github es una gran biblioteca de contenedores sin bloqueos que proporciona varias implementaciones de mapas hash sin bloqueos (por ejemplo, , , , , ). 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 MichaelHashMap SkipListMap SkipListSet FeldmanHashMap FeldmanHashSet 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 ; de lo contrario, utilice un . mapa 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 , , o (como , , o ). y probablemente serán los más eficientes. std boost folly abseil std::unordered_map boost::unordered_map boost::unordered_node_map folly::F14NodeMap boost::unordered_node_... folly 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 o ). boost::unordered_flat_map folly::F14FastMap Los contenedores planos utilizan más memoria que los basados en nodos, especialmente cuando de la clave o el valor es grande. Si el uso de la memoria es un problema, utilice contenedores basados en nodos. sizeof 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.
