Ovo je drugi dio u nizu o odabiru najpogodnijeg asocijativnog spremnika (rječnika) u C++23. U prvom dijelu smo obrađivali naručene kontejnere , au ovom dijelu ćemo detaljnije govoriti o nenaručenim.

Nenaručeni kontejneri

Ovi kontejneri ne daju nikakav definisani redosled za svoje ključeve. Štaviše, redoslijed ključeva se može promijeniti sa svakom modifikacijom, tako da se program nikada ne smije oslanjati na njega. Takvi kontejneri se uvijek implementiraju kao hash mape.

Generalno, prilikom dodavanja, uklanjanja ili traženja ključa, hash mapa prvo izračunava neku integralnu heš vrijednost iz tog ključa koristeći hash funkciju. Heš (ili bolje rečeno njegov dio) se tada koristi kao indeks u susjednom unaprijed dodijeljenom nizu. Svaki unos u ovom nizu naziva se bucket . Neki unosi u tom nizu će biti prazni, neki će sadržavati jedan element, a neki će se možda mapirati na više od jednog elementa zbog hash kolizija. Ovo se dešava kada različiti ključevi imaju heš vrijednosti koje upućuju na isti indeks niza. Hash mape koriste različite strategije za rješavanje heš kolizija (pogledajte ovaj članak na Wikipediji ). Broj elemenata u hash mapi podijeljen s ukupnom veličinom niza naziva se faktor opterećenja . Što je veći faktor opterećenja, to je veći broj mogućih sudara heša sa svakim novoumetnutim elementom.

Za razliku od uređenih kontejnera, hash mape ne podržavaju upite opsega, operacije rangiranja/odabira, iteraciju preko ključeva po redoslijedu i traženje ključa koji je manji/veći od zadanog ključa. Zauzvrat, hash mape postižu najbolje moguće performanse: vremenska složenost operacija pretraživanja/umetanja/uklanjanja se amortizuje O(1) . Ovdje kažem "amortizirano", jer kada broj elemenata postane prevelik, hash mapa treba da ponovo hashira svoj sadržaj kako bi se smanjio faktor opterećenja (efikasno povećavajući polje bucket-a). Vremenska složenost ponavljanja je O(n) . Međutim, očekuje se da će se to dogoditi rijetko, tako da je u prosjeku svaka operacija i dalje O(1) . Drugi razlog za potencijalno smanjene performanse je hash funkcija sa lošom distribucijom, što će povećati učestalost sudara.

Standardne hash mape

Počevši od C++11, standardna biblioteka pruža sljedeće hash mape: std::unordered_map ( link ), std::unordered_set ( link ), std::unordered_multimap ( link ) i std::unordered_multiset ( link ). Mape povezuju ključ sa vrijednošću, dok skupovi pohranjuju samo ključ i korisni su za provjeru da li je ključ prisutan u kontejneru, ali ne i za preuzimanje pridružene vrijednosti. Više kontejnera omogućava pohranjivanje višestrukih duplikata ključeva.

Svi standardni neuređeni kontejneri su bazirani na čvorovima i koriste odvojeno ulančavanje za rješavanje heš kolizija, što znači da pohranjuju svaki ključ ili par ključ-vrijednost u zasebnom povezanom čvoru liste. Memorija za svaki novi čvor se dodjeljuje pojedinačno, što nije posebno efikasno. Ovo također čini strukturu podataka neprikladnom za CPU keš, jer svaki pristup ključu zahtijeva dodatnu indirektnost. Evo kako unutrašnja struktura unordered_map može izgledati:

Na lijevoj strani se nalazi niz kantica, koji je unaprijed dodijeljen nekoj fiksnoj veličini ( 8 u našem primjeru). U početku su sve kante prazne. Kada počnemo da dodajemo elemente na hash mapu, neke kante će postati zauzete. U gornjem primjeru, postoji element s ključem 10 (koji je ušao u kantu 1 ), i dva elementa s ključevima 50 i 256 , oba su završila u istoj kanti 3 jer su se njihove hash vrijednosti sudarile. Tu je i element sa ključem 3 , koji je sletio u kantu 6 . Svaki segment pokazuje na povezanu listu, koja idealno ne sadrži više od jednog elementa. Buckets 0 , 2 , 4 , 5 i 7 su prazne i pokazuju na nullptr .

Pretpostavimo da trebamo pronaći vrijednost za ključ 256 .

• Prvo, mapa izračunava heš ključa i dobija ostatak kada se heš vrednost podeli sa ukupnim brojem bucketa ( 8 u našem slučaju). U našem primjeru, vrijednost ostatka je 3 .
• Zatim, mapa počinje čitati elemente povezane liste na koje ukazuje bucket 3 .
• Prvi element ima ključ 50 , koji nije isti kao 256 koji tražimo, tako da će mapa nastaviti da se ponavlja. Sljedeći element ima ključ 256 , koji je upravo onaj koji nam treba. Odgovarajuća vrijednost je xyz .
• Da ključ nije u rječniku, mapa bi ili pogodila praznu kantu ili bi iterirala preko povezane liste do kraja. U oba slučaja, mapa bi vratila end iterator, što ukazuje da ključ ne postoji.

Možda ćete primijetiti da posljednji element svake liste ukazuje na prvi element sljedeće liste. Ovo se radi u nekim implementacijama kako bi se poboljšala efikasnost iteracije. Umjesto da provjeravamo segment po segment pri iteraciji preko svih elemenata hash mape, možemo koristiti te veze da skočimo s jedne neprazne povezane liste na drugu mnogo brže.

Ako nastavimo da dodajemo više elemenata na gornju hash mapu, u nekom trenutku faktor opterećenja će postati previsok (na primjer, 80%), a hash mapa će odlučiti da ponovo hashira. Povećat će unaprijed dodijeljeni niz (npr. sa 8 na 16 elemenata), ponovo izračunati hešove za sve postojeće elemente i staviti elemente u nove kutije.

Standardni kontejneri daju garanciju stabilnosti referenci i iteratora, ali su slabiji od onih koje nude naručeni kontejneri. Reference na postojeće elemente se nikada ne poništavaju. Iteratori postojećih elemenata mogu biti poništeni samo kada dodavanje novog elementa izazove rehash ili kada se ponovno haširanje pokrene ručno:

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

Od C++17, neuređeni kontejneri dozvoljavaju manipulaciju čvorom: moguće je uzeti čvor s jedne karte i premjestiti ga na drugu mapu bez kopiranja ključa i vrijednosti:

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

Evo šta se dešava u gornjem programu:

Druga strategija za rješavanje heš kolizija se zove Otvoreno adresiranje . U hash mapama otvorenog adresiranja, svaki segment pohranjuje najviše jedan element. Ako je bucket već zauzet, element sa istom hash vrijednošću ide u neki drugi slobodni segment. Takve hash mape pokušavaju grupirati elemente u susjedne memorijske blokove kako bi poboljšali efikasnost i učinili strukturu podataka ugodnijom za CPU keš memoriju. C++ standardna biblioteka ne pruža otvorene adrese hash mapa, ali postoji mnogo alternativa treće strane.

Heš mape trećih strana

Boost.Unordered je sjajna biblioteka koja pruža širok spektar implementacija hash mapa.

Postoje boost::unordered_set , boost::unordered_map , boost::unordered_multiset , i boost::unordered_multimap , koji su analozi za std kontejnere, i sve što je gore napisano se odnosi na njih. Ovi kontejneri koriste malo složeniju unutrašnju strukturu sa "bucket grupama" za poboljšanje efikasnosti iteracije.

Biblioteka također pruža boost::unordered_node_set , boost::unordered_node_map , boost::unordered_flat_set i boost::unordered_flat_map , koji su otvoreni kontejneri za adresiranje. Interna struktura se razlikuje od otvorenih varijanti adresiranja:

Više o unutrašnjoj strukturi možete pročitati u ovom blog postu .

Kontejneri zasnovani na čvorovima ( boost::unordered_node_set , boost::unordered_node_map ) i dalje koriste čvorove, na koje ukazuju kante. Ovi kontejneri obezbeđuju isti iterator i referentnu stabilnost zagarantovanu kao std kontejneri i takođe pružaju isti API za manipulaciju čvorom (tj. metodu extract ).

U ravnim kontejnerima ( boost::unordered_flat_set , boost::unordered_flat_map ), ključevi i vrijednosti se pohranjuju direktno u polje bucket. Ravni kontejneri su najefikasniji, ali daju najslabije garancije: iteratori i reference na sve elemente su nevažeći kada se ponovi haširanje. API za manipulaciju čvorovima uopće nije dostupan. Flat kontejneri mogu koristiti više memorije od onih baziranih na čvorovima, posebno ako je ključ ili veličina sizeof velika.

Još jedna biblioteka treće strane koja implementira kontejnere otvorenog adresiranja je Folly F14 (dobavlja Meta). Postoji nekoliko varijanti rječnika koje su vrlo bliske gore opisanim kontejnerima biblioteke Boost:

• folly::F14NodeSet je isto što i boost::unordered_node_set , folly::F14NodeMap je isto što i boost::unordered_node_map .
• folly::F14ValueSet je isto što i boost::unordered_flat_set , a folly::F14ValueMap je isto što i boost::unordered_flat_map .
• folly::F14VectorMap / folly::F14VectorSet drže ključeve/vrijednosti upakovane u neprekidni niz, a kante sadrže indekse u tom nizu.
• folly::F14FastMap / folly::F14FastSet je krovna klasa. On bira najefikasniju implementaciju (bilo F14Value ili F14Vector ) na osnovu parametara koje navedete (kao što su tipovi ključa i vrijednosti).

Zanimljiva dodatna efikasna karakteristika F14 hash mapa je prehaširanje . Na primjer, ako trebate tražiti isti ključ više puta, a njegovo heširanje je skupo (npr. ključ je niz), možete ga unaprijed hashirati jednom, a zatim koristiti F14HashToken u svim kasnijim pozivima hash mape kako biste izbjegli ponovno heširanje istog ključa više puta. Polazna tačka je prehash metoda ( link ).

Više o internoj strukturi F14 hash kontejnera možete pročitati u ovom postu na FB blogu .

Biblioteka Abseil Swiss Tables (koju obezbjeđuje Google) također implementira otvoreno adresiranje bazirane na čvorovima i ravni hash kontejnere: absl::flat_hash_map , absl::flat_hash_set , absl::node_hash_map , absl::node_hash_set . Slični su Boost i F14. Više o njima možete pročitati ovdje i ovdje .

Manje poznata ankerl biblioteka ( github ) tvrdi da je vrlo efikasna u većini scenarija. Autor ove biblioteke pruža opsežne benchmark rezultate za mnoge hash mape u različitim slučajevima upotrebe ( post na blogu ). Možete pratiti ove rezultate, ali ih uzmite sa rezervom. Uvijek testirajte hash mapu koju odaberete u proizvodnom okruženju. Mjerila su uvijek sintetička i ne pokrivaju slučajeve kada CPU i memorija obavljaju drugi posao osim heš mapiranja. Benchmarks također ne pokrivaju slučajeve kada različiti dijelovi memorije hash mapa nisu u kešu procesora, što će se često dešavati u stvarnim programima.

Kvalitet hash funkcije

Kvalitet hash funkcije je važan za održavanje vremenske složenosti operacija traženja O(1) . Ravne hash mape su posebno osjetljive na kvalitet hash funkcije. Idealna heš funkcija može se definirati ovako: ako se promijeni jedan bit u ključu, odgovarajuća heš vrijednost će nasumično promijeniti polovinu svojih bitova. Takva hash funkcija se zove lavinska .

Nažalost, neke implementacije C++ standardne biblioteke celobrojnih i heš funkcija pokazivača nisu lavine. Na primjer, libstdc++ jednostavno vraća pokazivač ili cjelobrojnu vrijednost direktno bez ikakvih dodatnih transformacija: github .

Napredne hash tablice, kao što su boost i F14 implementacije, rješavaju ovaj problem uvođenjem osobine hash_is_avalanching . Ako se hash funkcija ne navede kao lavina, hash tablica će izvršiti dodatni korak miješanja kako bi poboljšala kvalitet heširanja. Ovo dolazi uz dodatnu cijenu. Ako implementirate prilagođenu hash funkciju, a znate da je pristojnog kvaliteta, možete je označiti kao lavinu kao što je prikazano u ovom primjeru . Boost koristi ime svojstva is_avalanching , a svojstvo F14 se zove folly_is_avalanching . U idealnom slučaju, trebali biste dodati oba.

Ako koristite tipove ključeva koji su podržani izvan kutije (npr. string , int , pokazivači) i zadane hash funkcije koje obezbjeđuje boost ili F14 , oni će već biti ispravno označeni prema potrebi i nećete morati razmišljati o tome osim ako odlučite implementirati prilagođeni tip ključa, za koji će biti potrebna prilagođena hash funkcija.

Sigurnost niti

Svi gore navedeni kontejneri općenito nisu sigurni za niti i morat ćete implementirati vanjsku sinkronizaciju (na primjer, korištenjem muteksa) ako jedna nit može modificirati hash mapu kada joj pristupi druga nit.

Ako sve niti čitaju samo mapu, sinkronizacija nije potrebna. Uvjerite se da pozivate samo metode označene sa const . Sve metode koje nisu const mogu modificirati kontejner. Imajte na umu da operator[] nije const i da će modificirati kontejner. Uobičajena zamka u višenitnom kodu je:

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

U kodu iznad, cilj je provjeriti da li je vrijednost koja odgovara key true . Međutim, map["key"] će dodati key na map ako još nije tamo. Novododata vrijednost će biti postavljena na zadanu vrijednost ( false u gornjem primjeru). To znači da takav kod nije siguran niti je previše optimalan. Efikasniji i sigurniji način za provjeru istog stanja je sljedeći:

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

• Ovde prvo dobijamo iterator do elementa identifikovanog "ključem".
• Zatim provjeravamo da li element postoji u mapi ( it != map.end() ).
• Ako jeste, konačno provjeravamo njegovu vrijednost ( it->second == true ).

U ovom primjeru, find i end ne modificiraju mapu, a pretraga postaje sigurna niti. Ako je cilj bio samo provjeriti postoji li ključ na mapi, mogli biste jednostavno pozvati map.contains("key") .

Neuređene mape sigurne niti

Postoji nekoliko implementacija thread-safe hash mapa.

• Jedna opcija je boost::concurrent_flat_set i boost::concurrent_flat_map iz biblioteke Boost.Unordered . Boost kontejneri pružaju API baziran na posjetima koji se znatno razlikuje od API-ja koji pruža standardna biblioteka C++.
• Druga opcija je folly::ConcurrentHashMap ( github ). Folly pokušava da zadrži svoj API što je bliže moguće C++ standardnim neuređenim kontejnerima.
• libcds je velika biblioteka kontejnera bez zaključavanja koja pruža nekoliko implementacija hash mapa bez zaključavanja (npr. MichaelHashMap , SkipListMap , SkipListSet , FeldmanHashMap , FeldmanHashSet ). Ova biblioteka već neko vrijeme nije ažurirana i ne pruža detaljnu dokumentaciju, ali je i dalje dijelim jer su spremnici koje nudi jedinstveni. Ako vaš slučaj upotrebe implicira veliku raspravu na hash mapi, isprobajte ove rječnike bez zaključavanja koje nudi libcds .
• Ako efikasnost nije zabrinjavajuća, možete sinkronizirati pristupe mapama koje nisu sigurne niti koristeći mutekse. Alternativno, možete u potpunosti izbjeći istovremene pristupe, što je često efikasnije od korištenja nit-sigurnih kontejnera ili dodavanja sinhronizacije.

Koji da koristim?

Pogledajmo sažete tačke koje objašnjavaju kako odabrati najprikladniji kontejner.

• Ako trebate da povežete ključ sa vrijednošću, odaberite mapu , u suprotnom koristite set .
• Ako je potrebno zadržati duple ključeve na mapi, koristite više kontejnera.
• Ako su vam potrebne najstrože moguće garancije stabilnosti iteratora i referenci, koristite kontejnere zasnovane na std , boost , folly ili abseil čvorovima (kao što su std::unordered_map , boost::unordered_map , boost::unordered_node_map ili folly::F14NodeMap ). boost::unordered_node_... i folly će vjerovatno biti najefikasnija.
• Ako stabilnost iteratora i reference nije važna (što znači da ne pohranjujete iteratore, reference ili pokazivače za mapiranje/postavljanje elemenata izvana ili ne očekujete da će ostati važeći nakon što se mapa modificira), tada odaberite ravni kontejner (kao što je kao boost::unordered_flat_map ili folly::F14FastMap ).
• Flat kontejneri koriste više memorije od onih baziranih na čvorovima, posebno kada je sizeof ključa i/ili vrijednost velika. Ako je upotreba memorije problem, umjesto toga koristite kontejnere bazirane na čvorovima.
• F14 kontejneri pružaju funkciju prethodnog heširanja za dodatnu efikasnost. Ako više puta pretražujete/dodajete/uklanjate identične ključeve, F14 će omogućiti uštedu na troškovima heširanja tako što ćete prethodno heširati ključeve.
• Sve gore navedene tačke se odnose na jednonitnu upotrebu kontejnera (ili višenitni pristup za čitanje bez istovremenih modifikacija). Ako su potrebne modifikacije s više niti, odaberite jednu od gore navedenih opcija sigurnih u niti. Oni mogu pokazati različite performanse u stvarnom proizvodnom kodu, pa razmislite o njihovom testiranju u svojoj aplikaciji i upoređivanju rezultata.