Ez a második része a C++23 nyelven a legmegfelelőbb asszociatív konténer (szótár) kiválasztásáról szóló sorozatnak. Az első részben a megrendelt konténerekkel foglalkoztunk , ebben a részben pedig a még nem rendelt konténerekről lesz szó.

Rendeletlen konténerek

Ezek a tárolók nem biztosítanak meghatározott sorrendet a kulcsaikhoz. Sőt, a kulcsok sorrendje minden módosítással változhat, így a program soha ne hagyatkozzon rá. Az ilyen konténereket mindig hash-térképként valósítják meg.

Általánosságban elmondható, hogy kulcs hozzáadásakor, eltávolításakor vagy keresésekor a hash-leképezés először a hash-függvény segítségével számít ki valamilyen integrált hash-értéket a kulcsból. A hash-t (vagy inkább annak részét) ezután indexként használják a szomszédos előre lefoglalt tömbben. Ebben a tömbben minden bejegyzést vödörnek nevezünk. A tömb egyes bejegyzései üresek, némelyik egyetlen elemet tartalmaz, néhány pedig több elemre is leképezhet a hash ütközések miatt. Ez akkor fordul elő, ha a különböző kulcsok hash értékei ugyanarra a tömbindexre mutatnak. A hash-térképek különféle stratégiákat használnak a hash-ütközések kezelésére (lásd ezt a Wikipédia-cikket ). A hash térkép elemeinek számát osztva a tömb teljes méretével terhelési tényezőnek nevezzük. Minél nagyobb a terhelési tényező, annál több lehetséges hash-ütközés lehetséges minden egyes újonnan beillesztett elemnél.

A rendezett konténerekkel ellentétben a hash térképek nem támogatják a tartománylekérdezéseket, a rangsorolási/kiválasztási műveleteket, a kulcsok sorrendjében történő iterációt és az adott kulcsnál kisebb/nagyobb kulcs keresését. Cserébe a hash térképek elérik az elérhető legjobb teljesítményt: a keresési/beszúrási/eltávolítási műveletek időbeli összetettsége amortizálódik O(1) . Itt azt mondom, hogy "amortizált", mert amikor az elemek száma túl nagy lesz, akkor a hash térképnek újra kell olvasnia a tartalmát, hogy csökkentse a terhelési tényezőt (hatékonyan növelje a vödör tömböt). Az újrafeldolgozás időbonyolultsága O(n) . Ez azonban várhatóan ritkán fordul elő, így átlagosan minden művelet még mindig O(1) . A potenciálisan csökkent teljesítmény másik oka a rossz eloszlású hash függvény, amely növeli az ütközések gyakoriságát.

Szabványos hash térképek

A C++11-től kezdve a szabványos könyvtár a következő hash-leképezéseket biztosítja: std::unordered_map ( link ), std::unordered_set ( link ), std::unordered_multimap ( link ) és std::unordered_multiset ( link ). A Maps kulcsot társít az értékhez, míg a készletek csak a kulcsot tárolják, és hasznosak annak ellenőrzésére, hogy a kulcs megtalálható-e a tárolóban, de nem kéri le a társított értéket. A több konténer lehetővé teszi több duplikált kulcs tárolását.

Minden szabványos rendezetlen konténer csomópont alapú, és külön láncolást használ a hash ütközések kezelésére, ami azt jelenti, hogy minden kulcsot vagy kulcs-érték párt külön csatolt listacsomópontban tárolja. A memóriát minden új csomóponthoz külön-külön osztják ki, ami nem különösebben hatékony. Emiatt az adatstruktúra nem is CPU-gyorsítótár-barát, mert minden egyes kulcshoz való hozzáférés extra közvetettséget igényel. Így nézhet ki az unordered_map belső szerkezete:

A bal oldalon van egy sor gyűjtőhely, amely előre hozzá van rendelve valamilyen rögzített mérethez (példánkban 8 ). Kezdetben minden vödör üres. Amikor elkezdünk elemeket hozzáadni a hash térképhez, néhány gyűjtőhely foglalt lesz. A fenti példában van egy 10 kulcsú elem (amely 1 tárolóba került), valamint két 50 és 256 os kulcsú elem, mindkettő ugyanabba a 3 gyűjtőbe került, mert a hash értékeik ütköztek. Van egy 3 kulcsú elem is, amely 6 vödörben landolt. Minden vödör a hivatkozott listára mutat, amely ideális esetben legfeljebb egy elemet tartalmaz. 0 , 2 , 4 , 5 és 7 csoport üres, és nullptr -re mutat.

Tegyük fel, hogy meg kell találnunk a 256 os kulcs értékét.

• Először is, a térkép kiszámítja a kulcskivonatot, és megkapja a maradékot, amikor elosztja a hash értékét a gyűjtők teljes számával (esetünkben 8 ). Példánkban a maradék értéke 3 .
• Ezután a térkép elkezdi olvasni a hivatkozott lista elemeit, amelyekre a vödör 3 mutat.
• Az első elemen az 50 kulcs található, ami nem ugyanaz, mint a keresett 256 , így a térkép folytatja az iterációt. A következő elem a 256 kulcsot tartalmazza, amelyre pontosan szükségünk van. A megfelelő érték xyz .
• Ha a kulcs nem lenne a szótárban, a térkép vagy egy üres vödörbe ütközne, vagy a linkelt listán a végéig iterálna. Mindkét esetben a térkép egy end ad vissza, jelezve, hogy a kulcs nem létezik.

Észreveheti, hogy az egyes listák utolsó eleme a következő lista első elemére mutat. Ezt egyes megvalósításokban az iteráció hatékonyságának javítása érdekében teszik. Ahelyett, hogy vödrönként ellenőriznénk, amikor az összes hash-térkép elemet iteráljuk, ezeket a kapcsolatokat használhatjuk arra, hogy az egyik nem üres hivatkozási listáról sokkal gyorsabban ugorjunk át a másikra.

Ha továbbra is további elemeket adunk a fenti hash-térképhez, egy ponton a terhelési tényező túl magas lesz (például 80%), és a hash-térkép az újrakivonatolás mellett dönt. Növeli az előre lefoglalt tömböt (pl. 8 -ról 16 elemre), újraszámítja az összes meglévő elem hash-jét, és az elemeket az új gyűjtőhelyekbe helyezi.

A szabványos konténerek referencia- és iterátor-stabilitási garanciákat nyújtanak, de gyengébbek, mint a megrendelt konténerek. A meglévő elemekre való hivatkozások soha nem érvénytelenek. A meglévő elemek iterátorai csak akkor érvényteleníthetők, ha egy új elem hozzáadása újrafeldolgozást okoz, vagy ha az újrakivonatolást manuálisan indítják el:

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

A C++17 óta a rendezetlen konténerek lehetővé teszik a csomópontok manipulálását: lehetséges egy csomópontot az egyik térképről áthelyezni egy másik térképre anélkül, hogy a kulcsot és az értéket másolnánk:

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

Ez történik a fenti programban:

Egy másik stratégia a hash ütközések kezelésére a nyílt címzés. A nyílt címzésű hash-térképekben minden gyűjtőzóna legfeljebb egy elemet tárol. Ha a vödör már foglalt, akkor az azonos hash értékkel rendelkező elem egy másik szabad tárolóba kerül. Az ilyen hash-leképezések megpróbálják az elemeket összefüggő memóriablokkokban csoportosítani, hogy javítsák a hatékonyságot és az adatstruktúrát CPU-gyorsítótár-barátabbá tegyék. A C++ szabványos könyvtár nem biztosít nyílt címzési hash-térképeket, de számos harmadik féltől származó alternatíva létezik.

Harmadik féltől származó hash térképek

A Boost.Unordered egy fantasztikus könyvtár, amely a hash-térkép-megvalósítások széles skáláját kínálja.

Vannak boost::unordered_set , boost::unordered_map , boost::unordered_multiset és boost::unordered_multimap , amelyek az std konténerek analógjai, és minden, ami fent van, vonatkozik rájuk. Ezek a konténerek egy kicsit bonyolultabb belső struktúrát használnak "vödörcsoportokkal" az iterációs hatékonyság javítása érdekében.

A könyvtár boost::unordered_node_set , boost::unordered_node_map , boost::unordered_flat_set és boost::unordered_flat_map szolgáltatást is tartalmazza, amelyek nyitott címzési tárolók. A belső szerkezet eltér a nyílt címzési változatoktól:

A belső felépítésről bővebben ebben a blogbejegyzésben olvashat.

A csomópont alapú konténerek ( boost::unordered_node_set , boost::unordered_node_map ) továbbra is használnak csomópontokat, amelyekre a gyűjtőhelyek mutatnak. Ezek a tárolók ugyanazt az iterátor és referencia stabilitást biztosítják, mint az std konténerek, és ugyanazt az API-t biztosítják a csomópontok manipulálásához (azaz extract módszerhez).

Lapos tárolókban ( boost::unordered_flat_set , boost::unordered_flat_map ) a kulcsok és értékek közvetlenül a vödörtömbben tárolódnak. A lapos konténerek a leghatékonyabbak, de a leggyengébb garanciákat nyújtják: az iterátorok és az összes elemre való hivatkozás érvénytelenítésre kerül, amikor újrafeldolgozás történik. Csomópont-manipulációs API egyáltalán nem biztosított. A lapos tárolók több memóriát igényelhetnek, mint a csomópont-alapúak, különösen akkor, ha a kulcs vagy a sizeof nagy.

Egy másik, nyílt címzésű konténereket megvalósító, harmadik féltől származó könyvtár a Folly F14 (a Meta szolgáltatója). Van néhány szótárváltozat, amelyek nagyon közel állnak a fent leírt Boost könyvtári tárolókhoz:

• folly::F14NodeSet ugyanaz, mint boost::unordered_node_set , folly::F14NodeMap ugyanaz, mint boost::unordered_node_map .
• folly::F14ValueSet ugyanaz, mint boost::unordered_flat_set , és folly::F14ValueMap ugyanaz, mint boost::unordered_flat_map .
• folly::F14VectorMap / folly::F14VectorSet a kulcsokat/értékeket egy összefüggő tömbbe csomagolva tartja, és a gyűjtőhelyek indexeket tartalmaznak ebbe a tömbbe.
• folly::F14FastMap / folly::F14FastSet egy esernyőosztály. Kiválasztja a leghatékonyabb megvalósítást ( F14Value vagy F14Vector ) az Ön által megadott paraméterek (például kulcs- és értéktípusok) alapján.

Az F14 hash térképek érdekes extra hatékonysági jellemzője az előkivonatolás . Például, ha többször kell keresni ugyanazt a kulcsot, és a kivonatolása drága (pl. egy kulcs egy karakterlánc), akkor egyszer előzetesen kivonatozhatja, majd később az F14HashToken minden hash map hívásnál használhatja, hogy elkerülje az újra ugyanazt a kulcsot többször is kivonatolja. A kiindulópont a prehash módszer ( link ).

Az F14 hash konténerek belső felépítéséről ebben az FB blogbejegyzésben olvashat bővebben.

Az Abseil Swiss Tables könyvtár (a Google által biztosított) nyílt címzésű csomópont-alapú és lapos hash-tárolókat is megvalósít: absl::flat_hash_map , absl::flat_hash_set , absl::node_hash_map , absl::node_hash_set . Hasonlóak a Boosthoz és az F14-hez. Bővebben itt és itt olvashat róluk.

Egy kevésbé ismert ankerl könyvtár ( github ) azt állítja, hogy a legtöbb esetben nagyon hatékony. Ennek a könyvtárnak a szerzője kiterjedt benchmark eredményeket kínál számos hash-térképhez különböző használati esetekben ( blogbejegyzés ). Követheti ezeket az eredményeket, de vegye őket egy szem sóval. Mindig tesztelje a kiválasztott hash térképet az éles környezetben. A benchmarkok mindig szintetikusak, és nem fedik le azokat az eseteket, amikor a CPU és a memória a hash-leképezési műveleteken kívül más munkát is végez. A benchmarkok nem fedik le azokat az eseteket sem, amikor a hash térképmemória egyes részei nincsenek a CPU gyorsítótárában, ami gyakran előfordul valós programokban.

Hash függvény minősége

A hash függvény minősége fontos az O(1) keresési műveletek időbeli összetettségének megőrzéséhez. A lapos hash térképek különösen érzékenyek a hash függvény minőségére. Egy ideális hash függvényt így definiálhatunk: ha a kulcs egyetlen bitje megváltozik, a megfelelő hash érték a bitek felét véletlenszerűen megváltoztatja. Az ilyen hash függvényt lavinázásnak nevezzük.

Sajnos egyes C++ szabványos könyvtári megvalósítások az egész számok és a mutató hash függvényei nem lavinaszerűek. Például libstdc++ egyszerűen visszaadja a mutatót vagy az egész értéket, további átalakítások nélkül: github .

A speciális hash táblák, például boost és F14 implementációk a hash_is_avalanching tulajdonság bevezetésével kezelik ezt a problémát. Ha a hash függvény nem lavinaként írja ki magát, a hash tábla további keverési lépést hajt végre a hash minőségének javítása érdekében. Ez külön költséggel jár. Ha egyéni hash-függvényt valósít meg, és tudja, hogy az megfelelő minőségű, akkor lavinaként jelölheti meg, amint az ebben a példában látható . A Boost az is_avalanching tulajdonságnevet használja, az F14 tulajdonság neve pedig folly_is_avalanching . Ideális esetben mindkettőt hozzá kell adni.

Ha a gyárilag támogatott kulcstípusokat (pl. string , int , pointers) és a boost vagy F14 által biztosított alapértelmezett hash függvényeket használod, akkor ezek már szükség szerint megfelelően meg lesznek jelölve, és nem kell ezen gondolkodnod, hacsak nem úgy dönt, hogy egyéni kulcstípust implementál, amelyhez egyéni hash függvényre lesz szükség.

Menetbiztonság

A fenti tárolók általában nem szálbiztosak, és külső szinkronizálást kell végrehajtania (például mutexek használatával), ha az egyik szál módosíthatja a hash-leképezést, amikor egy másik szál hozzáfér.

Ha az összes szál csak a térképet olvassa, nincs szükség szinkronizálásra. Ügyeljen arra, hogy csak const jellel jelölt metódusokat hívja meg. Minden nem const metódus módosíthatja a tárolót. Ne feledje, hogy operator[] nem const , és módosítja a tárolót. A többszálú kód gyakori buktatója:

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

A fenti kódban a cél annak ellenőrzése, hogy a key megfelelő érték true e. map["key"] azonban hozzáadja a key a map , ha még nincs ott. Az újonnan hozzáadott érték alapértelmezettre lesz állítva ( false a fenti példában). Ez azt jelenti, hogy az ilyen kód nem szálbiztos, és nem túl optimális. Egy hatékonyabb és szálbiztosabb módszer ugyanazon állapot ellenőrzésére a következő:

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

• Itt először eljuttatjuk az iterátort a "kulcs" által azonosított elemhez.
• Ezután ellenőrizzük, hogy az elem létezik-e a térképen ( it != map.end() ).
• Ha igen, akkor végül ellenőrizzük az értékét ( it->second == true ).

Ebben a példában find és end nem módosítja a térképet, és a keresés szálbiztossá válik. Ha csak az volt a cél, hogy ellenőrizze, hogy a kulcs létezik-e a térképen, egyszerűen meghívhatja map.contains("key") .

Szálbiztos rendezetlen térképek

A szálbiztos hash-térképeknek van néhány megvalósítása.

• Az egyik lehetőség boost::concurrent_flat_set és boost::concurrent_flat_map a Boost.Unordered könyvtárból . A Boost tárolók látogatásalapú API-t biztosítanak, amely nagymértékben különbözik a C++ szabványkönyvtár által biztosított API-tól.
• Egy másik lehetőség a folly::ConcurrentHashMap ( github ). A Folly igyekszik az API-ját a lehető legközelebb tartani a C++ szabványos rendezetlen konténerekhez.
• A libcds egy nagy, zárolás nélküli konténerkönyvtár, amely számos zárolásmentes hash-leképezést biztosít (pl. MichaelHashMap , SkipListMap , SkipListSet , FeldmanHashMap , FeldmanHashSet ). Ez a könyvtár egy ideje nem frissült, és nem nyújt részletes dokumentációt, de továbbra is megosztom, mert az általa kínált tárolók egyediek. Ha az Ön használati esete nagy versengésre utal egy hash térképen, próbálja ki ezeket a zárolás nélküli szótárakat, amelyeket libcds kínál.
• Ha a hatékonyság nem aggodalomra ad okot, mutexek segítségével szinkronizálhatja a hozzáférést a nem szálbiztos térképekhez. Alternatív megoldásként teljesen elkerülheti az egyidejű hozzáféréseket, ami gyakran hatékonyabb, mint a szálbiztos tárolók használata vagy a szinkronizálás hozzáadása.

Melyiket használjam?

Nézzük meg azokat az összefoglaló pontokat, amelyek elmagyarázzák, hogyan válasszuk ki a legmegfelelőbb tartályt.

• Ha kulcsot kell társítania az értékhez, válasszon egy térképet , ellenkező esetben használjon egy készletet .
• Ha duplikált kulcsokat kell tartani a térképen, használjon több tárolót.
• Ha a lehető legszigorúbb iterátor- és referenciastabilitási garanciákra van szüksége, használjon std , boost , folly vagy abseil csomópont alapú tárolókat (például std::unordered_map , boost::unordered_map , boost::unordered_node_map vagy folly::F14NodeMap ). boost::unordered_node_... és folly valószínűleg a leghatékonyabb.
• Ha az iterátor és a referencia stabilitása nem fontos (ami azt jelenti, hogy nem tárolja az iterátorokat, hivatkozásokat vagy mutatókat külső leképezési/beállítási elemekhez, vagy nem várja el, hogy a térkép módosítása után is érvényesek maradjanak), akkor válasszon egy lapos tárolót (pl. mint boost::unordered_flat_map vagy folly::F14FastMap ).
• A lapos tárolók több memóriát használnak, mint a csomópont-alapúak, különösen akkor, ha a kulcs sizeof és/vagy az érték nagy. Ha a memóriahasználat aggodalomra ad okot, használjon helyette csomópont-alapú tárolókat.
• Az F14 konténerek előtörlő funkciót biztosítanak az extra hatékonyság érdekében. Ha ugyanazokat a kulcsokat többször keresi/adja hozzá/eltávolítja, az F14 lehetővé teszi a kivonatolási költségek megtakarítását a kulcsok előzetes tördelésével.
• A fenti pontok mindegyike az egyszálú tárolóhasználatra vonatkozik (vagy többszálú olvasási hozzáférésre, párhuzamos módosítások nélkül). Ha többszálas módosításokra van szükség, válassza ki a fent felsorolt szálbiztos opciók egyikét. Változó teljesítményt mutathatnak a valós gyártási kódban, ezért fontolja meg, hogy tesztelje őket az alkalmazásban, és hasonlítsa össze az eredményeket.