Akax payïr t’aqaw serie ukanx C++23 ukanx juk’amp aski asociativo contenedor (diccionario) ajlliñatakiwa. Nayrïr t’aqapanx ordenat contenedores ukanakatw uñakipt’apxta , ukat aka chiqanx jan ordenat contenedores ukanakat juk’amp qhanañcht’añäni.

Jan ordenatäki uka phukhunaka

Aka phukhunakax janiw kuna orden definido ukanaks llavenakapatak churapkiti. Ukhamaraki, orden clave ukax sapa modificación ukampix mayjt’aspawa, ukhamax programax janipuniw ukaruw atinisiñapäkiti. Ukham contenedores ukanakax sapa kutiw hash maps ukham phuqhachasi.

Jilapachax mä llave yapxataña, apsuña jan ukax thaqhaña, mä hash mapa ukax nayraqat mä juk’a integral hash valor uka llave ukat hash función ukampiw jakthapi. Ukatx hash (jan ukax chiqapax) ukax mä índice ukhamaw apnaqasi, ukax contiguo pre-asignado matriz ukaruw apnaqasi. Aka matriz ukan sapa mantawix mä cubo satawa . Uka matriz ukan yaqhip qillqt’atanakax ch’usakïniwa, yaqhipanakax mä sapa elemento ukanïniwa, ukatx yaqhipanakax mä elementot sipans juk’amp elementonakaruw mapa lurapxaspa hash ch’axwawinakat. Ukax kunawsatix kunayman llaves ukanakax hash valores ukanipki ukhax pachpa índice de matriz ukar uñacht’ayi. Mapas de hash ukax kunayman estrategias ukanakaw hash ukan ch’axwawinakar saykatañatakix apnaqasi ( aka Wikipedia ukan qillqat uñakipt’aña ). Mapa hash ukanx elementos ukanakax taqpach tamaparjam jaljatawa, ukax factor de carga satawa. Factor de carga ukax juk’amp jach’awa, sapa machaq elemento ukamp chikt’atax juk’amp ch’axwawinakaw hash ukar puri.

Kunjamakitix ordenat contenedores ukanakat sipansa, mapas hash ukax janiw rango jiskt’awinak yanapt’kiti, rank/select operaciones, iteración sobre llaves ordenan, ukatx llave jisk’a/jach’a thaqhañaw churat llave ukat sipansa. Ukjamarus, hash mapas ukax suma phuqhañ lurawiruw puri: pacha complejidad de operaciones de búsqueda/inserción/remoción ukax amortizado O(1) . Nayax akanx "amortizado" sasaw sista, kunatix kunapachatix elementos ukanakax sinti jach'äxi ukhax mä mapa de hash ukax contenido ukar rehash lurañaw wakisi factor de carga ukar jisk'achañataki (efectivamente matriz de cubos ukar jiltayañataki). Rehashing ukan pacha complejidad ukax O(n) ukhamawa. Ukampirus juk’akiw lurasiñap suyt’ata, ukhamax chika taypinx sapa operación ukax wali O(1) ukhamawa. Yaqha razón ukax potencialmente jisk’achata lurawix mä función hash ukawa jan suma jaljawimpi, ukax juk’ampiw ch’axwañanakax jilxatani.

Mapas hash estándar ukanaka

C++11 ukamp qalltasinx biblioteca estándar ukax aka hash mapas ukanakaw utji: std::unordered_map ( enlace ), std::unordered_set ( enlace ), std::unordered_multimap ( enlace ), ukatx std::unordered_multiset ( enlace ). Mapas ukax mä llave ukarux valorampiw uñt’ayi, ukampirus conjuntos ukax llave ukakiw imaraki ukatx llave ukax contenedor ukan utjiti janicha uk uñakipañatakix wali askiwa, ukampis janiw asociado valor ukax apsutäkiti. Walja contenedores ukanakax walja duplicados llaves ukanakaw imatäspa.

Taqi jan ordenat contenedores estándar ukax nodo ukarjam luratawa ukatx Separate chaining ukampiw hash ch’axwawinakar saykatañatakix apnaqasi, ukax sañ muniw, sapa llave jan ukax clave-valor par par ukarux mä sapa nodo de lista enlazada ukan imasipxi. Sapa machaq nodo ukan amuyupax sapa mayniruw jaljasi, ukax janiw sinti askïkiti. Ukhamaraki, estructura de datos ukax janiw CPU caché-friendly ukhamäkiti, kunatix sapa clave ukar mantañax extra indirección ukaruw munaraki. Akax kunjams unordered_map manqhankir uñstawix uñstaspa ukawa:

Ch’iqa tuqinxa, mä matriz de cubos ukaw utji, ukax nayraqat mä tama fijo ukar uñt’ayatawa ( 8 jiwasan uñacht’äwisan). Qalltanx taqi cubos ukanakax ch’usakiwa. Kunawsatix elementos ukanakax hash map ukar yapxatañ qalltañäni ukhax yaqhip cubos ukanakax ocupados ukhamaw tukuni. Aka uñacht’awina, mä elemento llave 10 (ukax cubo 1 ukar mantawayi), ukatx pä elemento llaves 50 ukat 256 , panpachaniw pachpa cubo 3 ukan tukuyapxi kunatix hash valores ukanakax ch’axwapxi. Ukhamaraki mä elemento llave 3 ukampi, ukaxa cubo 6 ukanwa uraqir puri. Sapa cubo ukax lista enlazada ukaruw uñacht’ayi, ukax wali askiwa, janiw mä elemento ukat sipans juk’ampïkiti. Cubos 0 , 2 , 4 , 5 , 7 ukax ch’usakiwa ukatx nullptr ukar uñtatawa.

Jiwasax 256 llave ukan valorap jikxatañaw wakisi sasin amuyt’añäni.

• Nayraqatxa, mapa ukax hash clave ukaruw jakthapi ukatx qhipharux jikxati kunawsatix hash valor ukax taqpach cubos ukar jaljatäki ukhaxa ( 8 jiwasan amuyusataki). Jiwasan uñacht’awisanx qhipharux 3 ukhawa.
• Ukatxa, mapa ukax elementos de la lista enlazada ukar uñakipañ qalltawayi, ukax cubo 3 ukan uñacht’ayatawa.
• Nayrïr elemento ukax llave 50 ukaniwa, ukax janiw 256 ukarjam thaqhatäkiti, ukhamax mapax iterat sarantaskakiniwa. Jutïr elementox llave 256 ukampiw utji, ukax chiqpachapuniw jiwasatakix wakisi. Uka chimpuxa xyz satawa.
• Llavejj jan diccionarion utjkaspäna ukhajja, mapajj mä chʼusa cuboruw chʼalltʼaspa jan ukajj enlazat listaruw tukuyañkamajj mayamp mayamp mayamp mayamp mayamp mayamp mayamp mayamp mayamp istʼaspa. Panpachanx mapax mä iterador end ukar kutt’ayaspawa, ukax llavex janiw utjkiti sañ muni.

Inas amuyaraksta, sapa listan qhipa elementopax jutir listan nayrïr elementoparuw uñacht’ayi. Ukax yaqhip phuqhawinakanx lurasiwa, ukhamat iteración ukan suma sartañapataki. Taqi elementos de mapa hash ukar iteracionax cubo por cubo uñakipañat sipansa, uka conexiones ukanakamp mä jan ch’usat lista enlazada ukar yaqha ukar juk’amp jank’ak saltañatakix apnaqaraksnawa.

Jiwasatix juk’amp elementos ukanakamp hash mapa ukar yapxataskakiñäni ukhax mä juk’a pachax factor de carga ukax sinti jach’aruw tukuni (santi, 80%), ukatx hash map ukax rehash lurañ amtaniwa. Ukax nayraqat asignat matriz (jan ukax 8 ukat 16 elementos) ukar jiltañapawa, taqi utjki uka elementonakatakix hashes ukanakax wasitat jakthapiñapawa, ukatx elementos ukanakax machaq cubos ukar uchañapawa.

Contenedores estándares ukaxa referencia ukhamaraki iterador estabilidad ukanaka garantizatawa, ukampisa ukaxa juk’ampi ch’amawa kunatixa contenedores ordenados ukanakana churata ukanakatxa. Uka utjki uka elementonakat referencianakax janipuniw jan walt’ayatäkiti. Jichha utjki uka elementonakar iteradores ukanakax machaq elemento ukar yapxatañax mä rehash ukar puriyaspa ukhakiw jan chiqapar uñjatäspa, jan ukax rehashing ukax manual ukar ch’amanchatäspa ukhakiw jan walt’ayatäspa:

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

C++17 ukhatpachaxa, jan ordenat contenedores ukanakax nodo manipulación ukarux jaysapxiwa: mä mapa ukan nodo apsuñax wakisispawa ukat yaqha mapa ukar apayañax wakisispawa jan llave ukat valor ukar copiasa:

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

Akax aka pata wakichäwinx lurasi:

Yaqha estrategia ukax hash colisiones ukar saykatañatakix Open addressing satawa. Mapas hash abierto-direccionamiento ukanx sapa cubo ukax mä elemento ukjamaw imaraki. Uka cubo ukax nayratpach apnaqatäxi ukhaxa, pachpa hash valoran elemento ukax yaqha libre cubo ukaruw sararaki. Ukham hash mapas ukax elementos ukanakar bloques de memoria contiguos ukan tantacht’añ yant’apxi, ukhamat eficiencia ukar juk’amp askiptañataki ukhamarak estructura de datos ukar juk’amp CPU caché-friendly ukar tukuyañataki. C++ biblioteca estándar ukax janiw jist’arat direccionamiento hash mapas ukanak churkiti, ukampis walja kimsïr alternativas ukanakaw utji.

Kimsïr jaqinakan hash mapas ukanaka

Boost.Unordered ukax mä muspharkañ biblioteca ukawa, ukax mä jach’a hash map implementaciones ukanakaw utji.

Ukanx boost::unordered_set , boost::unordered_map , boost::unordered_multiset , ukat boost::unordered_multimap ukanakaw utji, ukax std contenedores ukanakatakix análogos ukanakawa, ukatx taqi kunatix alayax qillqt’atäki ukax jupanakaruw apnaqasi. Aka phukhunakax mä juk’a ch’amt’at manqhankir estructura ukampiw "cubo grupos" ukanakamp apnaqapxi, iteración ukan eficiencia ukar juk'amp askiptañataki.

Ukhamaraki biblioteca ukaxa boost::unordered_node_set , boost::unordered_node_map , boost::unordered_flat_set , ukhamaraki boost::unordered_flat_map churaraki, ukaxa jist’aratawa direccionamiento contenedores. Manqhankir uñstawix mayj mayjawa, jist’arat direccionamiento variantes ukanakatxa:

Uka manqhankir uñstawipatx juk'amp uñakipt'apxasmawa aka blog tuqin .

Nodo-based contenedores ( boost::unordered_node_set , boost::unordered_node_map ) wali nodos apnaqapxi, ukax cubos ukanakamp uñacht’ayatawa. Aka contenedores ukaxa pachpa iterador ukhamaraki estabilidad de referencia garantizada ukhama std contenedores ukampi ukhamaraki pachpa API manipulación de nodos ukataki (mä arunxa método extract ).

Plano contenedores ( boost::unordered_flat_set , boost::unordered_flat_map ), llaves ukat valores ukanakax chiqak cubo matriz ukan imatäxiwa. Contenedores planos ukax juk’amp askiwa, ukampis juk’amp jan ch’aman garantianak churapxi: iteradores ukat referencias taqi elementos ukanakax invalidadas ukhamawa kunapachatix rehashing ukax utjki ukhaxa. API de manipulación de nodos ukax janiw kunas churatäkiti. Plano contenedores ukax juk’amp memoria apnaqaspawa nodo-based ukanakat sipansa, juk’ampirus llave jan ukax valor sizeof ukax jach’ächi ukhaxa.

Yaqha kimsïr biblioteca ukax jist’arat dirección ukan contenedores ukanakaruw phuqhi, ukax Folly F14 (Meta ukan churatawa). Mä qawqha diccionario variantes ukanakaw utji, ukax Boost biblioteca ukan contenedores ukanakarux wali jak’ankiwa, ukax akham uñt’ayatawa:

• folly::F14NodeSet ukax pachpakiwa boost::unordered_node_set ukampi , folly::F14NodeMap ukax boost::unordered_node_map ukampiw kikipa.
• folly::F14ValueSet ukax boost::unordered_flat_set ukampiw kikipa, ukatx folly::F14ValueMap ukax boost::unordered_flat_map ukampiw kikipa.
• folly::F14VectorMap / folly::F14VectorSet llaves/valores ukanakax mä matriz contiguo ukan packed ukhamawa, ukatx cubos ukanakax uka matriz ukarux índices ukanakaw utji.
• folly::F14FastMap / folly::F14FastSet ukax mä clase paraguas ukawa. Ukax juk’amp suma phuqhañ ajlli ( F14Value jan ukax F14Vector ) ukax parámetros ukarjam uñt’ayatawa (kunjamatix llave ukat valor tipos ukanaka).

Mä interesante extra eficiencia ukax F14 hash maps ukanx prehashing ukawa. Amuyt’añataki, pachpa llave walja kuti thaqhañax wakisispa, ukat hashing ukax jila qullqini (jan ukax mä llavex mä cadena ukhamawa), mä kutiw prehash ukax lurasispa, ukatx F14HashToken ukampiw taqi hash mapa jawsatanakan qhipat apnaqasispa, ukhamat jan mayamp pachpa llave walja kuti hashing. Qalltäwix prehash uka thakhi ( enlace ) ukawa.

F14 hash contenedores ukan manqhan estructurapat juk'amp uñakipt'apxasmawa aka FB blog post ukan .

Abseil Swiss Tables biblioteca (Google ukan churata) ukax jist’arat direccionamiento nodo-based ukat plano hash contenedores ukanakaruw phuqhayaraki: absl::flat_hash_map , absl::flat_hash_set , absl::node_hash_map , absl::node_hash_set . Jupanakax Boost ukat F14 ukanakar uñtasitawa. Jupanakat juk'amp yatxatapxasmawa aka chiqan ukhamarak aka chiqan .

Mä juk’a uñt’at ankerl biblioteca ( github ) ukax jilpach escenarios ukanx wali askiwa sasaw arsu. Aka biblioteca qillqirix walja hash mapas ukanakatakix kunayman apnaqañ utanakan jach’a chimpunak uñacht’ayi ( blog post ). Uka yatxatawinakax arktasispawa, ukampis mä grano de sal ukampiw apsuñama. Sapa kutiw hash mapa ukax producción ukan ajllitäki uk yant’añama. Benchmarks ukax sintéticos ukhamawa ukatx janiw casos ukanakax CPU ukat memoria ukax yaqha lurawinakamp lurapkiti jan ukax hash map operaciones ukanakat sipanx. Ukhamaraki, benchmarks ukax janiw kuna pachatix kunayman chiqanakax hash map memoria ukax CPU caché ukan jan utjki ukanakx uñt’aykiti, ukax chiqpach programanakanx sapa kutiw lurasini.

Hash función ukax mä suma lurawiwa

Hash función calidad ukaxa wali wakiskiriwa pacha complejidad uñakipañataki operaciones O(1) . Mapas hash planos ukax juk’ampirus hash función calidad ukaruw uñt’ayasi. Mä función hash ideal ukax akham qhanañchasispawa: mä sapa bit ukax llave ukan mayjt’aspa ukhax correspondiente valor hash ukax chikat bits ukanakap aleatoriamente mayjt’ayaspa. Ukham hash función ukax avalanching satawa.

Ukampirus, yaqhip C++ biblioteca estándar implementaciones de funciones de hash entero ukat puntero ukax janiw avalanching ukhamäkiti. Amuyt’añataki, libstdc++ ukax mäkiw uñacht’ayir jan ukax taqpach jakhüw chimpunak chiqaparu kutt’ayaraki jan kuna yaqha mayjt’awinakampi: github .

Tablas de hash avanzados, kunjamakitix boost ukat F14 implementaciones, ukax aka jan walt’awiruw askichi, hash_is_avalanching uka rasgo uñt’ayasa. Función hash ukax jan avalanching ukham uñt’ayatäkchi ukhax tabla de hash ukax mä yaqha mistuñ thakhi luraniw hash ukan calidad ukar juk’amp askiptañataki. Ukax mä juk’a qullqimpiw juti. Mä función hash personalizada ukar phuqhasa, ukat yatiskta ukax decente calidad ukaniwa, ukax avalancha ukham chimpuntasmawa kunjamatix aka uñacht’äwin uñacht’ayaski ukhama . Boost ukax is_avalanching uka propiedad sutimp apnaqi, ukatx F14 propiedad ukax folly_is_avalanching sutimp uñt’atawa. Wali askixa, panpachaniw yapxatañama.

Ukax llave tipos ukanakax yanapt’atawa jan ukax (jan ukax string , int , punteros) ukat hash funciones predeterminadas ukanakax boost jan ukax F14 ukanakamp churatawa, ukax nayratpach chiqaparuw chimpuntatäni kunjamatix wakiski ukhamarjama, ukatx janiw uka tuqit amuyt’añax wakiskiti jan ukax ukax mä tipo de llave costumbre ukar phuqhañ amtatawa, ukax mä función hash costumbre ukaruw munasini.

Hilo seguridad ukaxa

Taqi uka patat uñt’atanakax janiw taqpach thread-safe ukhamäkiti, ukatx anqäx sincronización ukar phuqhañaw wakisini (santi, mutexes apnaqaña) mä thread ukax hash map ukar mayjt’ayaspawa kunapachatix yaqha thread ukar mantani ukhaxa.

Taqi hilos ukanakax mapa ukak uñakipapxi ukhax janiw sincronización ukax wakiskiti. Ukhamaraki, const ukampi chimpuntata métodos ukanakak jawsaña. Taqi jan const lurawinakax uka phukhurux mayjt’ayaspawa. Amtañani operator[] ukax janiw const ukat ukax contenedor ukar mayjt’ayañapawa. Mä jan walt’awix walja threaded codigo ukanx akanakawa:

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

Aka pata tuqinkir código ukanx amtäwix key ukar uñtasit valorax true janicha uk uñakipañawa . Ukampirus, map["key"] key map ukarux yapxatañapawa , ukax janiw jichhakamax utjkiti. Machaq yapxatat chimpunakax default ( false uñacht’äwinx uñacht’ayatawa). Ukax sañ muniwa, ukham código ukax janiw thread-safe ukhamäkiti, ukatx janiw sinti óptimo ukhamäkiti. Mä juk’amp suma ukat hilo-safe thakhix pachpa condición uñakipañatakix akanakawa:

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

• Aka tuqinxa, nayraqatax iterador ukaruw "llave" ukamp uñt'at elemento ukar puripxta.
• Ukatx uka elementox mapa ukan utjiti janicha uk uñakipapxta ( it != map.end() ).
• Ukhamächi ukhaxa, qhipharux valorap uñakipt’añäni ( it->second == true ).

Aka uñacht’awina, find ukat end janiw mapa ukar mayjt’aykiti, ukatx thakhix thread-safe ukhamaw tuku. Amtäwix mapa ukan llavex utjiti janicha uk uñakipañatakik ukhamäspa ukhax map.contains("key") ukaruw jawst’asma.

Thread-safe jan ordenat mapanaka

Mä qawqha phuqhawinakaw thread-safe hash maps ukanakan utji.

• Mä amtawix boost::concurrent_flat_set ukat boost::concurrent_flat_map ukax Boost.Unordered biblioteca ukankiwa. Boost contenedores ukax API ukar visitt’ir uñacht’ayi ukax API ukat sipanx wali mayjawa, ukax biblioteca estándar C++ ukan churatawa.
• Yaqha amtawix folly::ConcurrentHashMap ( github ) ukawa. Folly ukax API ukax C++ estándar jan ordenat contenedores ukar jak’achasiñatakiw ch’amanchasi.
• libcds ukax mä jach’a jan bloqueo-free contenedor biblioteca ukawa, ukax walja implementaciones de lock-free hash maps ukanakaw utji (jan ukax MichaelHashMap , SkipListMap , SkipListSet , FeldmanHashMap , FeldmanHashSet ). Aka biblioteca ukax mä juk’a pachatx janiw machaqar tukuyatäkiti ukatx janiw documentación detallada ukanakax utjkiti, ukampis nayax waliw uñt’ayaskta kunatix contenedores ukanakax uñacht’ayat ukanakax mayj mayjawa. Ukax mä hash mapa ukan jach’a ch’axwañ uñacht’ayi ukhax aka libcds ukan uñacht’ayat jan bloqueo ukan aru pirwanak yant’am.
• Eficiencia ukax jan llakisiñatakïkchi ukhax, sincronizar accesos ukanakax jan thread-safe mapas ukar mutexes ukamp apnaqasa. Jan ukax, taqpach jan concurrentes accesos ukanakat jark’aqasiñataki, ukax juk’amp askiwa thread-safe contenedores apnaqañat sipansa jan ukax sincronización yapxatañat sipansa.

¿Kawkïris apnaqta?

Kunjamsa juk’amp wakiskir phukhu apthapiñax uk qhanañcht’ir mä juk’a qhanañcht’at puntonak uñakipt’añäni.

• Mä llave ukax valor ukamp chikt’ayañax wakisispa ukhax mä mapa , jan ukhamäkanixa, mä conjunto apnaqañaw wakisi.
• Mapanx duplicadas llaves ukanakax utjañapawa, multi contenedores ukanakamp apnaqaña.
• Iterador ukat referencia estabilidad garantias ukanakax juk’amp ch’amamp munaschi ukhax std , boost , folly , jan ukax abseil nodo ukarjam lurat contenedores ukanakamp apnaqañamawa (kunjamakitix std::unordered_map , boost::unordered_map , boost::unordered_node_map , jan ukax folly::F14NodeMap ). boost::unordered_node_... ukat folly juk’amp askiwa.
• Iterador ukat referencia estabilidad ukax jan wakiskirïkchi ukhax (ukax sañ muniw, janiw iteradores, referencias, jan ukax punteros ukanakax mapa/conjunto elementos ukanakar anqäx tuqit imañakiti jan ukax janiw mapa mayjt’ayat qhipatx chiqap qhiparañapatak suyktati), ukatx mä plano contenedor ajlliñaw (ukham kunjamatix boost::unordered_flat_map jan ukax folly::F14FastMap ).
• Plano contenedores ukax juk’amp memoria apnaqapxi nodo-based ukanakat sipansa, juk’ampirus kunapachatix sizeof the key ukat/jan ukax valor ukax jach’a ukhax. Amuyu apnaqañax llakisiñawa, uka lantix nodo-based contenedores apnaqaña.
• F14 ukax mä funcionalidad prehashing ukampiw juk’amp eficiencia ukar churaraki. Walja kuti pachpa llavenak thaqhaña/yaqhachañ/apsuña, F14 ukax llaves prehashing ukampiw hashing costo ukx qhispiyañatak yanapt’ani.
• Taqi aka pata tuqinkir puntonakax mä rosca ukan contenedor apnaqañatakiw apnaqasi (jan ukax walja threaded uñakipañ mantañax jan mä pachan mayjt’ayata). Walja threaded mayjt’awinakax wakisispa ukhax mä thread-safe amtawinak ajlliñamawa, ukax akham uñt’ayatawa. Chiqpach código de producción ukanx kunayman lurawinak uñacht’ayapxaspaw, ukhamax aplicación ukan yant’añ amtañamawa ukat resultados ukanakamp chikancht’asiñ amtañamawa.