Akax payïr t’aqaw serie ukanx C++23 ukanx juk’amp aski asociativo contenedor (diccionario) ajlliñatakiwa. , ukat aka chiqanx jan ordenat contenedores ukanakat juk’amp qhanañcht’añäni. Nayrïr t’aqapanx ordenat contenedores ukanakatw uñakipt’apxta 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ä . 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 ( uñakipt’aña ). Mapa hash ukanx elementos ukanakax taqpach tamaparjam jaljatawa, ukax satawa. Factor de carga ukax juk’amp jach’awa, sapa machaq elemento ukamp chikt’atax juk’amp ch’axwawinakaw hash ukar puri. cubo satawa aka Wikipedia ukan qillqat factor de carga 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 . 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 ukhamawa. Ukampirus juk’akiw lurasiñap suyt’ata, ukhamax chika taypinx sapa operación ukax wali ukhamawa. Yaqha razón ukax potencialmente jisk’achata lurawix mä función hash ukawa jan suma jaljawimpi, ukax juk’ampiw ch’axwañanakax jilxatani. amortizado O(1) O(n) O(1) Mapas hash estándar ukanaka C++11 ukamp qalltasinx biblioteca estándar ukax aka hash mapas ukanakaw utji: ( ), ( ), ( ), ukatx ( ). mä llave ukarux valorampiw uñt’ayi, ukampirus llave ukakiw imaraki ukatx llave ukax contenedor ukan utjiti janicha uk uñakipañatakix wali askiwa, ukampis janiw asociado valor ukax apsutäkiti. contenedores ukanakax walja duplicados llaves ukanakaw imatäspa. std::unordered_map enlace std::unordered_set enlace std::unordered_multimap enlace std::unordered_multiset enlace Mapas ukax conjuntos ukax Walja Taqi jan ordenat contenedores estándar ukax nodo ukarjam luratawa ukatx 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 manqhankir uñstawix uñstaspa ukawa: Separate chaining ukampiw unordered_map Ch’iqa tuqinxa, mä matriz de cubos ukaw utji, ukax nayraqat mä tama fijo ukar uñt’ayatawa ( 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 (ukax cubo ukar mantawayi), ukatx pä elemento llaves ukat , panpachaniw pachpa cubo ukan tukuyapxi kunatix hash valores ukanakax ch’axwapxi. Ukhamaraki mä elemento llave ukampi, ukaxa cubo ukanwa uraqir puri. Sapa cubo ukax lista enlazada ukaruw uñacht’ayi, ukax wali askiwa, janiw mä elemento ukat sipans juk’ampïkiti. Cubos , , , , ukax ch’usakiwa ukatx ukar uñtatawa. 8 10 1 50 256 3 3 6 0 2 4 5 7 nullptr Jiwasax llave ukan valorap jikxatañaw wakisi sasin amuyt’añäni. 256 Nayraqatxa, mapa ukax hash clave ukaruw jakthapi ukatx qhipharux jikxati kunawsatix hash valor ukax taqpach cubos ukar jaljatäki ukhaxa ( jiwasan amuyusataki). Jiwasan uñacht’awisanx qhipharux ukhawa. 8 3 Ukatxa, mapa ukax elementos de la lista enlazada ukar uñakipañ qalltawayi, ukax cubo ukan uñacht’ayatawa. 3 Nayrïr elemento ukax llave ukaniwa, ukax janiw ukarjam thaqhatäkiti, ukhamax mapax iterat sarantaskakiniwa. Jutïr elementox llave ukampiw utji, ukax chiqpachapuniw jiwasatakix wakisi. Uka chimpuxa satawa. 50 256 256 xyz 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 ukar kutt’ayaspawa, ukax llavex janiw utjkiti sañ muni. end 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 sinti jach’aruw tukuni (santi, 80%), ukatx hash map ukax rehash lurañ amtaniwa. Ukax nayraqat asignat matriz (jan ukax ukat elementos) ukar jiltañapawa, taqi utjki uka elementonakatakix hashes ukanakax wasitat jakthapiñapawa, ukatx elementos ukanakax machaq cubos ukar uchañapawa. factor de carga ukax 8 16 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 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. Open addressing Kimsïr jaqinakan hash mapas ukanaka ukax mä muspharkañ biblioteca ukawa, ukax mä jach’a hash map implementaciones ukanakaw utji. Boost.Unordered Ukanx , , , ukat ukanakaw utji, ukax 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. boost::unordered_set boost::unordered_map boost::unordered_multiset boost::unordered_multimap std Ukhamaraki biblioteca ukaxa , , , ukhamaraki churaraki, ukaxa jist’aratawa direccionamiento contenedores. Manqhankir uñstawix mayj mayjawa, jist’arat direccionamiento variantes ukanakatxa: boost::unordered_node_set boost::unordered_node_map boost::unordered_flat_set boost::unordered_flat_map Uka manqhankir uñstawipatx juk'amp uñakipt'apxasmawa . aka blog tuqin Nodo-based contenedores ( , ) wali nodos apnaqapxi, ukax cubos ukanakamp uñacht’ayatawa. Aka contenedores ukaxa pachpa iterador ukhamaraki estabilidad de referencia garantizada ukhama contenedores ukampi ukhamaraki pachpa API manipulación de nodos ukataki (mä arunxa método ). boost::unordered_node_set boost::unordered_node_map std extract Plano contenedores ( , ), 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 ukax jach’ächi ukhaxa. boost::unordered_flat_set boost::unordered_flat_map sizeof Yaqha kimsïr biblioteca ukax jist’arat dirección ukan contenedores ukanakaruw phuqhi, ukax (Meta ukan churatawa). Mä qawqha diccionario variantes ukanakaw utji, ukax Boost biblioteca ukan contenedores ukanakarux wali jak’ankiwa, ukax akham uñt’ayatawa: Folly F14 ukax pachpakiwa ukampi , ukax ukampiw kikipa. folly::F14NodeSet boost::unordered_node_set folly::F14NodeMap boost::unordered_node_map ukax ukampiw kikipa, ukatx ukax ukampiw kikipa. folly::F14ValueSet boost::unordered_flat_set folly::F14ValueMap boost::unordered_flat_map / llaves/valores ukanakax mä matriz contiguo ukan packed ukhamawa, ukatx cubos ukanakax uka matriz ukarux índices ukanakaw utji. folly::F14VectorMap folly::F14VectorSet / ukax mä clase paraguas ukawa. Ukax juk’amp suma phuqhañ ajlli ( jan ukax ) ukax parámetros ukarjam uñt’ayatawa (kunjamatix llave ukat valor tipos ukanaka). folly::F14FastMap folly::F14FastSet F14Value F14Vector Mä interesante extra eficiencia ukax F14 hash maps ukanx 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 ukampiw taqi hash mapa jawsatanakan qhipat apnaqasispa, ukhamat jan mayamp pachpa llave walja kuti hashing. Qalltäwix uka thakhi ( ) ukawa. prehashing F14HashToken prehash enlace F14 hash contenedores ukan manqhan estructurapat juk'amp uñakipt'apxasmawa ukan . aka FB blog post (Google ukan churata) ukax jist’arat direccionamiento nodo-based ukat plano hash contenedores ukanakaruw phuqhayaraki: , , , . Jupanakax Boost ukat F14 ukanakar uñtasitawa. Jupanakat juk'amp yatxatapxasmawa ukhamarak . Abseil Swiss Tables biblioteca absl::flat_hash_map absl::flat_hash_set absl::node_hash_map absl::node_hash_set aka chiqan aka chiqan Mä juk’a uñt’at biblioteca ( ) ukax jilpach escenarios ukanx wali askiwa sasaw arsu. Aka biblioteca qillqirix walja hash mapas ukanakatakix kunayman apnaqañ utanakan jach’a chimpunak uñacht’ayi ( ). 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. ankerl github blog post Hash función ukax mä suma lurawiwa Hash función calidad ukaxa wali wakiskiriwa pacha complejidad uñakipañataki operaciones . 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 satawa. O(1) avalanching Ukampirus, yaqhip C++ biblioteca estándar implementaciones de funciones de hash entero ukat puntero ukax janiw avalanching ukhamäkiti. Amuyt’añataki, ukax mäkiw uñacht’ayir jan ukax taqpach jakhüw chimpunak chiqaparu kutt’ayaraki jan kuna yaqha mayjt’awinakampi: . libstdc++ github Tablas de hash avanzados, kunjamakitix ukat implementaciones, ukax aka jan walt’awiruw askichi, 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 uñacht’ayaski ukhama . Boost ukax uka propiedad sutimp apnaqi, ukatx F14 propiedad ukax sutimp uñt’atawa. Wali askixa, panpachaniw yapxatañama. boost F14 hash_is_avalanching aka uñacht’äwin is_avalanching folly_is_avalanching Ukax llave tipos ukanakax yanapt’atawa jan ukax (jan ukax , , punteros) ukat hash funciones predeterminadas ukanakax jan ukax 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. string int boost F14 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, ukampi chimpuntata métodos ukanakak jawsaña. Taqi jan lurawinakax uka phukhurux mayjt’ayaspawa. Amtañani ukax janiw ukat ukax contenedor ukar mayjt’ayañapawa. Mä jan walt’awix walja threaded codigo ukanx akanakawa: const const operator[] const std::unordered_map<std::string, bool> map; // ... if (map["key"]) { // ... } Aka pata tuqinkir código ukanx amtäwix ukar uñtasit valorax janicha uk uñakipañawa . Ukampirus, ukarux , ukax janiw jichhakamax utjkiti. Machaq yapxatat chimpunakax default ( 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: key true map["key"] key map yapxatañapawa false 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, ukat 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 ukaruw jawst’asma. find end map.contains("key") Thread-safe jan ordenat mapanaka Mä qawqha phuqhawinakaw thread-safe hash maps ukanakan utji. Mä amtawix ukat ukax ukankiwa. Boost contenedores ukax API ukar visitt’ir uñacht’ayi ukax API ukat sipanx wali mayjawa, ukax biblioteca estándar C++ ukan churatawa. boost::concurrent_flat_set boost::concurrent_flat_map Boost.Unordered biblioteca Yaqha amtawix ( ) ukawa. Folly ukax API ukax C++ estándar jan ordenat contenedores ukar jak’achasiñatakiw ch’amanchasi. folly::ConcurrentHashMap github ukax mä jach’a jan bloqueo-free contenedor biblioteca ukawa, ukax walja implementaciones de lock-free hash maps ukanakaw utji (jan ukax , , , , ). 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 ukan uñacht’ayat jan bloqueo ukan aru pirwanak yant’am. libcds MichaelHashMap SkipListMap SkipListSet FeldmanHashMap FeldmanHashSet libcds 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ä , jan ukhamäkanixa, mä apnaqañaw wakisi. mapa conjunto Mapanx duplicadas llaves ukanakax utjañapawa, contenedores ukanakamp apnaqaña. multi Iterador ukat referencia estabilidad garantias ukanakax juk’amp ch’amamp munaschi ukhax , , , jan ukax nodo ukarjam lurat contenedores ukanakamp apnaqañamawa (kunjamakitix , , , jan ukax ). ukat juk’amp askiwa. std boost folly abseil std::unordered_map boost::unordered_map boost::unordered_node_map folly::F14NodeMap boost::unordered_node_... folly 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 jan ukax ). boost::unordered_flat_map folly::F14FastMap Plano contenedores ukax juk’amp memoria apnaqapxi nodo-based ukanakat sipansa, juk’ampirus kunapachatix the key ukat/jan ukax valor ukax jach’a ukhax. Amuyu apnaqañax llakisiñawa, uka lantix nodo-based contenedores apnaqaña. sizeof 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.
