Aquesta és la segona part de la sèrie sobre l'elecció del contenidor associatiu (diccionari) més adequat en C++23. A la primera part, vam cobrir els contenidors ordenats i, en aquesta part, parlarem dels contenidors no ordenats amb detall.

Contenidors no ordenats

Aquests contenidors no proporcionen cap ordre definit per a les seves claus. A més, l'ordre de les claus pot canviar amb cada modificació, de manera que el programa mai no hauria de confiar-hi. Aquests contenidors sempre s'implementen com a mapes hash.

Generalment, quan s'afegeix, s'elimina o es cerca una clau, un mapa hash primer calcula algun valor hash integral a partir d'aquesta clau mitjançant la funció hash. El hash (o més aviat la seva part) s'utilitza com a índex a la matriu pre-assignada contigua. Cada entrada d'aquesta matriu s'anomena cub . Algunes entrades d'aquesta matriu estaran buides, algunes contindran un sol element i algunes podrien mapar a més d'un element a causa de col·lisions hash. Això passa quan diferents claus tenen valors hash que apunten al mateix índex de matriu. Els mapes hash utilitzen diverses estratègies per fer front a les col·lisions hash (vegeu aquest article de la Viquipèdia ). El nombre d'elements del mapa hash dividit per la mida total de la matriu s'anomena factor de càrrega . Com més gran sigui el factor de càrrega, més possibles col·lisions es produiran amb cada element nou inserit.

A diferència dels contenidors ordenats, els mapes hash no admeten consultes d'interval, operacions de classificació/selecció, iteració de claus en ordre i cerqueu la clau més petita/més gran que la clau donada. A canvi, els mapes hash aconsegueixen el millor rendiment possible: la complexitat temporal de les operacions de cerca/inserció/eliminació s'amortitza O(1) . Dic "amortitzat" aquí, perquè quan el nombre d'elements es fa massa gran, un mapa hash ha de repetir el seu contingut per reduir el factor de càrrega (augmentant de manera efectiva la matriu de cubs). La complexitat temporal de la repetició és O(n) . Tanmateix, s'espera que succeeixi poques vegades, de manera que, de mitjana, cada operació encara és O(1) . Un altre motiu del rendiment potencialment reduït és una funció hash amb una distribució deficient, que augmentarà la freqüència de col·lisions.

Mapes hash estàndard

A partir de C++11, la biblioteca estàndard proporciona els mapes hash següents: std::unordered_map ( enllaç ), std::unordered_set ( enllaç ), std::unordered_multimap ( enllaç ) i std::unordered_multiset ( enllaç ). Els mapes associen una clau amb el valor, mentre que els conjunts només emmagatzemen la clau i són útils per comprovar si la clau està present al contenidor, però no recuperar el valor associat. Els contenidors múltiples permeten emmagatzemar múltiples claus duplicades.

Tots els contenidors estàndard no ordenats es basen en nodes i utilitzen l'encadenament separat per fer front a les col·lisions hash, el que significa que emmagatzemen cada parell clau o valor-clau en un node de llista enllaçat independent. La memòria per a cada nou node s'assigna individualment, cosa que no és especialment eficient. Això també fa que l'estructura de dades no sigui amigable amb la memòria cau de la CPU, perquè cada accés de clau requereix una indirecta addicional. Així és com pot semblar l'estructura interna unordered_map :

A l'esquerra, hi ha una matriu de cubs, que s'assignen prèviament a una mida fixa ( 8 al nostre exemple). Inicialment, tots els cubs estan buits. Quan comencem a afegir elements al mapa hash, alguns cubs estaran ocupats. A l'exemple anterior, hi ha un element amb la clau 10 (que va entrar al cub 1 ) i dos elements amb les claus 50 i 256 , tots dos van acabar al mateix cub 3 perquè els seus valors hash van xocar. També hi ha un element amb la clau 3 , que va aterrar a la galleda 6 . Cada cub apunta a la llista enllaçada, que idealment no conté més d'un element. Els cubs 0 , 2 , 4 , 5 i 7 estan buits i apunten a nullptr .

Suposem que hem de trobar el valor de la clau 256 .

• En primer lloc, el mapa calcula el hash de la clau i obté la resta quan es divideix el valor hash pel nombre total de cubs ( 8 en el nostre cas). En el nostre exemple, el valor de la resta és 3 .
• Aleshores, el mapa comença a llegir els elements de la llista enllaçada apuntada pel cub 3 .
• El primer element té la clau 50 , que no és la mateixa que la 256 que busquem, de manera que el mapa continuarà iterant. El següent element té la clau 256 , que és exactament la que necessitem. El valor corresponent és xyz .
• Si la clau no estigués al diccionari, el mapa tocava un cub buit o repetiria la llista enllaçada fins al final. En ambdós casos, el mapa retornaria un iterador end , indicant que la clau no existeix.

Podeu observar que l'últim element de cada llista apunta al primer element de la llista següent. Això es fa en algunes implementacions per millorar l'eficiència de la iteració. En lloc de comprovar cub per cub en iterar tots els elements del mapa hash, podem utilitzar aquestes connexions per saltar d'una llista enllaçada no buida a una altra molt més ràpid.

Si continuem afegint més elements al mapa hash anterior, en algun moment el factor de càrrega es farà massa alt (per exemple, el 80%) i el mapa hash decidirà repetir. Creixerà la matriu prèviament assignada (per exemple, de 8 a 16 elements), tornarà a calcular hash per a tots els elements existents i posarà elements als nous cubs.

Els contenidors estàndard ofereixen garanties d'estabilitat de referència i iterador, però són més febles que els que ofereixen els contenidors demanats. Les referències als elements existents mai són invalidades. Els iteradors dels elements existents només es poden invalidar quan l'addició d'un element nou provoca un refresc o quan el repetit s'activa manualment:

 #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"; }

Des de C++17, els contenidors no ordenats permeten la manipulació de nodes: és possible agafar un node d'un mapa i moure'l a un altre mapa sense copiar la clau i 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"; } }

Això és el que passa en el programa anterior:

Una altra estratègia per fer front a les col·lisions hash s'anomena adreçament obert . En els mapes hash d'adreçament obert, cada cub emmagatzema com a màxim un element. Si el cub ja està ocupat, l'element amb el mateix valor hash passa a un altre cub lliure. Aquests mapes hash intenten agrupar elements en blocs de memòria contigus per millorar l'eficiència i fer que l'estructura de dades sigui més amigable amb la memòria cau de la CPU. La biblioteca estàndard de C++ no ofereix mapes hash d'adreces obertes, però hi ha moltes alternatives de tercers.

Mapes hash de tercers

Boost.Unordered és una biblioteca fantàstica que ofereix una àmplia gamma d'implementacions de mapes hash.

Hi ha boost::unordered_set , boost::unordered_map , boost::unordered_multiset i boost::unordered_multimap , que són anàlegs per als contenidors std , i tot el que s'ha escrit anteriorment s'aplica a ells. Aquests contenidors utilitzen una estructura interna una mica més complexa amb "grups de cubs" per millorar l'eficiència de la iteració.

La biblioteca també proporciona boost::unordered_node_set , boost::unordered_node_map , boost::unordered_flat_set i boost::unordered_flat_map , que són contenidors d'adreçament oberts. L'estructura interna és diferent de les variants d'adreçament obert:

Podeu llegir més sobre l'estructura interna en aquesta entrada del blog .

Els contenidors basats en nodes ( boost::unordered_node_set , boost::unordered_node_map ) encara utilitzen nodes, als quals assenyalen els cubs. Aquests contenidors proporcionen el mateix iterador i estabilitat de referència garantida que els contenidors std i també proporcionen la mateixa API per a la manipulació de nodes (és a dir, el mètode extract ).

En contenidors plans ( boost::unordered_flat_set , boost::unordered_flat_map ), les claus i els valors s'emmagatzemen directament a la matriu de cubs. Els contenidors plans són els més eficients, però ofereixen les garanties més febles: els iteradors i les referències a tots els elements queden invalidats quan es produeix el refresc. L'API de manipulació de nodes no es proporciona en absolut. Els contenidors plans poden utilitzar més memòria que els basats en nodes, especialment si la clau o el valor sizeof és gran.

Una altra biblioteca de tercers que implementa contenidors d'adreçament obert és Folly F14 (proporcionat per Meta). Hi ha algunes variants de diccionari molt properes als contenidors de la biblioteca Boost descrits anteriorment:

• folly::F14NodeSet és el mateix que boost::unordered_node_set , folly::F14NodeMap és el mateix que boost::unordered_node_map .
• folly::F14ValueSet és el mateix que boost::unordered_flat_set , i folly::F14ValueMap és el mateix que boost::unordered_flat_map .
• folly::F14VectorMap / folly::F14VectorSet manté les claus/valors empaquetats en una matriu contigua i els cubs contenen índexs en aquesta matriu.
• folly::F14FastMap / folly::F14FastSet és una classe paraigua. Tria la implementació més eficient (ja sigui F14Value o F14Vector ) en funció dels paràmetres que especifiqueu (com ara els tipus de clau i valor).

Una característica extra d'eficiència interessant dels mapes hash F14 és el prehash . Per exemple, si necessiteu cercar la mateixa clau diverses vegades i el seu hash és car (p. ex., una clau és una cadena), podeu fer-ne un prehash una vegada i, a continuació, utilitzar el F14HashToken en totes les trucades de mapes hash més tard per evitar que es repeteixi. fent hash la mateixa clau diverses vegades. El punt de partida és el mètode prehash ( enllaç ).

Podeu llegir més sobre l'estructura interna dels contenidors hash F14 en aquesta publicació del bloc de FB .

La biblioteca Abseil Swiss Tables (proporcionada per Google) també implementa contenidors de hash pla i basats en nodes d'adreçament obert: absl::flat_hash_map , absl::flat_hash_set , absl::node_hash_map , absl::node_hash_set . Són semblants als Boost i F14. Podeu llegir més sobre ells aquí i aquí .

Una biblioteca ankerl menys coneguda ( github ) afirma ser molt eficient en la majoria dels escenaris. L'autor d'aquesta biblioteca proporciona amplis resultats de referència per a molts mapes hash en diferents casos d'ús ( entrada al bloc ). Podeu seguir aquests resultats, però preneu-los amb un gra de sal. Proveu sempre el mapa hash que trieu a l'entorn de producció. Els benchmarks són sempre sintètics i no cobreixen els casos en què la CPU i la memòria fan altres tasques a més de les operacions de mapes hash. Els punts de referència tampoc cobreixen els casos en què diverses parts de la memòria del mapa hash no es troben a la memòria cau de la CPU, cosa que passa sovint en programes reals.

Qualitat de la funció hash

La qualitat de la funció hash és important per mantenir la complexitat temporal de les operacions de cerca O(1) . Els mapes hash plans són especialment sensibles a la qualitat de la funció hash. Una funció hash ideal es pot definir així: si un sol bit a la clau canvia, el valor hash corresponent canviarà la meitat dels seus bits aleatòriament. Aquesta funció hash s'anomena allaus .

Malauradament, algunes implementacions de biblioteques estàndard de C++ de funcions hash d'enter i punter no són avalançant. Per exemple, libstdc++ simplement retorna el punter o el valor enter directament sense cap transformació addicional: github .

Les taules hash avançades, com ara les implementacions boost i F14 , tracten aquest problema introduint el tret hash_is_avalanching . Si la funció hash no s'indica com a allau, la taula hash realitzarà un pas addicional de barreja per millorar la qualitat del hash. Això té un cost addicional. Si implementeu una funció hash personalitzada i sabeu que és de qualitat decent, podeu marcar-la com a allau com es mostra en aquest exemple . Boost utilitza el nom de la propietat is_avalanching i la propietat F14 s'anomena folly_is_avalanching . Idealment, hauríeu d'afegir tots dos.

Si utilitzeu els tipus de clau admesos fora de la caixa (per exemple, string , int , punters) i les funcions hash per defecte proporcionades per boost o F14 , ja estaran marcades correctament segons sigui necessari, i no haureu de pensar en això tret que decidiu implementar un tipus de clau personalitzat, que necessitarà una funció hash personalitzada.

Seguretat del fil

Tots els contenidors anteriors no són segurs per a fils en general, i haureu d'implementar la sincronització externa (per exemple, utilitzant mutex) si un fil pot modificar el mapa hash quan un altre fil hi accedeix.

Si tots els fils només llegeixen el mapa, no cal sincronitzar. Assegureu-vos que només truqueu als mètodes marcats amb const . Tots els mètodes no const poden modificar el contenidor. Tingueu en compte que operator[] no és const i modificarà el contenidor. Un error comú en el codi multifil és:

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

Al codi anterior, l'objectiu és comprovar si el valor corresponent a la key és true . Tanmateix, map["key"] afegirà la key al map si encara no hi és. El valor afegit recentment s'establirà com a predeterminat ( false a l'exemple anterior). Això vol dir que aquest codi no és segur per a fils i no és massa òptim. Una manera més eficient i segura de comprovar la mateixa condició és la següent:

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

• Aquí, primer obtenim l'iterador a l'element identificat per la "clau".
• A continuació, comprovem si l'element existeix al mapa ( it != map.end() ).
• Si ho fa, finalment comprovem el seu valor ( it->second == true ).

En aquest exemple, find i end no modifiquen el mapa i la cerca esdevé segura. Si l'objectiu era només comprovar si la clau existeix al mapa, simplement podríeu trucar a map.contains("key") .

Mapes no ordenats sense fils

Hi ha algunes implementacions de mapes hash segurs per a fils.

• Una opció és boost::concurrent_flat_set i boost::concurrent_flat_map de la biblioteca Boost.Unordered . Els contenidors Boost proporcionen una API basada en visites que és molt diferent de l'API proporcionada per la biblioteca estàndard de C++.
• Una altra opció és folly::ConcurrentHashMap ( github ). Folly intenta mantenir la seva API el més a prop possible dels contenidors no ordenats estàndard de C++.
• libcds és una gran biblioteca de contenidors sense bloqueig que proporciona diverses implementacions de mapes hash sense bloqueig (per exemple, MichaelHashMap , SkipListMap , SkipListSet , FeldmanHashMap , FeldmanHashSet ). Aquesta biblioteca fa temps que no s'actualitza i no ofereix documentació detallada, però encara la comparteixo perquè els contenidors que ofereix són únics. Si el vostre cas d'ús implica una gran contenció en un mapa hash, proveu aquests diccionaris sense bloqueig que ofereix libcds .
• Si l'eficiència no és una preocupació, podeu sincronitzar els accessos a mapes que no són segurs per a fils mitjançant mutex. Alternativament, podeu evitar completament els accessos concurrents, que sovint són més eficients que utilitzar contenidors segurs per a fils o afegir sincronització.

Quin faig servir?

Vegem els punts resumits que expliquen com escollir el contenidor més adequat.

• Si necessiteu associar una clau amb el valor, trieu un mapa , en cas contrari, utilitzeu un conjunt .
• Si és necessari mantenir les claus duplicades al mapa, utilitzeu diversos contenidors.
• Si necessiteu les garanties d'iteració i estabilitat de referència més estrictes possibles, utilitzeu contenidors basats en nodes std , boost , folly o abseil (com ara std::unordered_map , boost::unordered_map , boost::unordered_node_map o folly::F14NodeMap ). boost::unordered_node_... i folly probablement serà la més eficient.
• Si l'estabilitat de l'iterador i de la referència no és important (és a dir, no emmagatzemeu iteradors, referències o punters per a mapes/establir elements externament o no espereu que siguin vàlids després de modificar el mapa), trieu un contenidor pla (com ara com boost::unordered_flat_map o folly::F14FastMap ).
• Els contenidors plans utilitzen més memòria que els basats en nodes, especialment quan sizeof de la clau i/o el valor és gran. Si l'ús de la memòria és un problema, utilitzeu contenidors basats en nodes.
• Els contenidors F14 proporcionen una funcionalitat de prehashing per obtenir una eficiència addicional. Si cerqueu/afegiu/elimineu claus idèntiques diverses vegades, F14 us permetrà estalviar en el cost de la funció hash fent prehashing les claus.
• Tots els punts anteriors s'apliquen a l'ús de contenidors d'un sol fil (o a l'accés de lectura de diversos fils sense modificacions concurrents). Si calen modificacions de diversos fils, seleccioneu una de les opcions de seguretat de fils que s'indiquen més amunt. Poden mostrar un rendiment variable en el codi de producció real, així que considereu provar-los a la vostra aplicació i comparar-ne els resultats.