Ovo je drugi dio u nizu o odabiru najpogodnijeg asocijativnog spremnika (rječnika) u C++23. , au ovom dijelu ćemo detaljnije govoriti o nenaručenim. U prvom dijelu smo obrađivali naručene kontejnere 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 . 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 ). Broj elemenata u hash mapi podijeljen s ukupnom veličinom niza naziva se . Što je veći faktor opterećenja, to je veći broj mogućih sudara heša sa svakim novoumetnutim elementom. bucket ovaj članak na Wikipediji faktor opterećenja 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 . 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 . Međutim, očekuje se da će se to dogoditi rijetko, tako da je u prosjeku svaka operacija i dalje . Drugi razlog za potencijalno smanjene performanse je hash funkcija sa lošom distribucijom, što će povećati učestalost sudara. amortizuje O(1) O(n) O(1) Standardne hash mape Počevši od C++11, standardna biblioteka pruža sljedeće hash mape: ( ), ( ), ( ) i ( ). povezuju ključ sa vrijednošću, dok pohranjuju samo ključ i korisni su za provjeru da li je ključ prisutan u kontejneru, ali ne i za preuzimanje pridružene vrijednosti. kontejnera omogućava pohranjivanje višestrukih duplikata ključeva. std::unordered_map link std::unordered_set link std::unordered_multimap link std::unordered_multiset link Mape skupovi Više Svi standardni neuređeni kontejneri su bazirani na čvorovima i koriste 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 može izgledati: odvojeno ulančavanje unordered_map Na lijevoj strani se nalazi niz kantica, koji je unaprijed dodijeljen nekoj fiksnoj veličini ( 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 (koji je ušao u kantu ), i dva elementa s ključevima i , oba su završila u istoj kanti jer su se njihove hash vrijednosti sudarile. Tu je i element sa ključem , koji je sletio u kantu . Svaki segment pokazuje na povezanu listu, koja idealno ne sadrži više od jednog elementa. Buckets , , , i su prazne i pokazuju na . 8 10 1 50 256 3 3 6 0 2 4 5 7 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 ( u našem slučaju). U našem primjeru, vrijednost ostatka je . 8 3 Zatim, mapa počinje čitati elemente povezane liste na koje ukazuje bucket . 3 Prvi element ima ključ , koji nije isti kao koji tražimo, tako da će mapa nastaviti da se ponavlja. Sljedeći element ima ključ , koji je upravo onaj koji nam treba. Odgovarajuća vrijednost je . 50 256 256 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 iterator, što ukazuje da ključ ne postoji. end 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 će postati previsok (na primjer, 80%), a hash mapa će odlučiti da ponovo hashira. Povećat će unaprijed dodijeljeni niz (npr. sa na elemenata), ponovo izračunati hešove za sve postojeće elemente i staviti elemente u nove kutije. faktor opterećenja 8 16 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 . 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. Otvoreno adresiranje Heš mape trećih strana je sjajna biblioteka koja pruža širok spektar implementacija hash mapa. Boost.Unordered Postoje , , , i , koji su analozi za 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. boost::unordered_set boost::unordered_map boost::unordered_multiset boost::unordered_multimap std Biblioteka također pruža , , i , koji su otvoreni kontejneri za adresiranje. Interna struktura se razlikuje od otvorenih varijanti adresiranja: boost::unordered_node_set boost::unordered_node_map boost::unordered_flat_set boost::unordered_flat_map Više o unutrašnjoj strukturi možete pročitati . u ovom blog postu Kontejneri zasnovani na čvorovima ( , ) i dalje koriste čvorove, na koje ukazuju kante. Ovi kontejneri obezbeđuju isti iterator i referentnu stabilnost zagarantovanu kao kontejneri i takođe pružaju isti API za manipulaciju čvorom (tj. metodu ). boost::unordered_node_set boost::unordered_node_map std extract U ravnim kontejnerima ( , ), 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 velika. boost::unordered_flat_set boost::unordered_flat_map sizeof Još jedna biblioteka treće strane koja implementira kontejnere otvorenog adresiranja je (dobavlja Meta). Postoji nekoliko varijanti rječnika koje su vrlo bliske gore opisanim kontejnerima biblioteke Boost: Folly F14 je isto što i , je isto što i . folly::F14NodeSet boost::unordered_node_set folly::F14NodeMap boost::unordered_node_map je isto što i , a je isto što i . folly::F14ValueSet boost::unordered_flat_set folly::F14ValueMap boost::unordered_flat_map / drže ključeve/vrijednosti upakovane u neprekidni niz, a kante sadrže indekse u tom nizu. folly::F14VectorMap folly::F14VectorSet / je krovna klasa. On bira najefikasniju implementaciju (bilo ili ) na osnovu parametara koje navedete (kao što su tipovi ključa i vrijednosti). folly::F14FastMap folly::F14FastSet F14Value F14Vector Zanimljiva dodatna efikasna karakteristika F14 hash mapa je . 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 u svim kasnijim pozivima hash mape kako biste izbjegli ponovno heširanje istog ključa više puta. Polazna tačka je metoda ( ). prehaširanje F14HashToken prehash link Više o internoj strukturi F14 hash kontejnera možete pročitati u . ovom postu na FB blogu (koju obezbjeđuje Google) također implementira otvoreno adresiranje bazirane na čvorovima i ravni hash kontejnere: , , , . Slični su Boost i F14. Više o njima možete pročitati i . Biblioteka Abseil Swiss Tables absl::flat_hash_map absl::flat_hash_set absl::node_hash_map absl::node_hash_set ovdje ovdje Manje poznata biblioteka ( ) 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 ( ). 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. ankerl github post na blogu Kvalitet hash funkcije Kvalitet hash funkcije je važan za održavanje vremenske složenosti operacija traženja . 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 . O(1) lavinska Nažalost, neke implementacije C++ standardne biblioteke celobrojnih i heš funkcija pokazivača nisu lavine. Na primjer, jednostavno vraća pokazivač ili cjelobrojnu vrijednost direktno bez ikakvih dodatnih transformacija: . libstdc++ github Napredne hash tablice, kao što su i implementacije, rješavaju ovaj problem uvođenjem osobine . 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 . Boost koristi ime svojstva , a svojstvo F14 se zove . U idealnom slučaju, trebali biste dodati oba. boost F14 hash_is_avalanching ovom primjeru is_avalanching folly_is_avalanching Ako koristite tipove ključeva koji su podržani izvan kutije (npr. , , pokazivači) i zadane hash funkcije koje obezbjeđuje ili , 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. string int boost F14 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 . Sve metode koje nisu mogu modificirati kontejner. Imajte na umu da nije i da će modificirati kontejner. Uobičajena zamka u višenitnom kodu je: const const operator[] const std::unordered_map<std::string, bool> map; // ... if (map["key"]) { // ... } U kodu iznad, cilj je provjeriti da li je vrijednost koja odgovara . Međutim, će na ako još nije tamo. Novododata vrijednost će biti postavljena na zadanu vrijednost ( 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: key true map["key"] dodati key map false 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, i ne modificiraju mapu, a pretraga postaje sigurna niti. Ako je cilj bio samo provjeriti postoji li ključ na mapi, mogli biste jednostavno pozvati . find end map.contains("key") Neuređene mape sigurne niti Postoji nekoliko implementacija thread-safe hash mapa. Jedna opcija je i iz . Boost kontejneri pružaju API baziran na posjetima koji se znatno razlikuje od API-ja koji pruža standardna biblioteka C++. boost::concurrent_flat_set boost::concurrent_flat_map biblioteke Boost.Unordered Druga opcija je ( ). Folly pokušava da zadrži svoj API što je bliže moguće C++ standardnim neuređenim kontejnerima. folly::ConcurrentHashMap github je velika biblioteka kontejnera bez zaključavanja koja pruža nekoliko implementacija hash mapa bez zaključavanja (npr. , , , , ). 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 MichaelHashMap SkipListMap SkipListSet FeldmanHashMap FeldmanHashSet 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 , u suprotnom koristite . mapu set Ako je potrebno zadržati duple ključeve na mapi, koristite kontejnera. više Ako su vam potrebne najstrože moguće garancije stabilnosti iteratora i referenci, koristite kontejnere zasnovane na , , ili čvorovima (kao što su , , ili ). i će vjerovatno biti najefikasnija. std boost folly abseil std::unordered_map boost::unordered_map boost::unordered_node_map folly::F14NodeMap boost::unordered_node_... folly 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 ili ). boost::unordered_flat_map folly::F14FastMap Flat kontejneri koriste više memorije od onih baziranih na čvorovima, posebno kada je ključa i/ili vrijednost velika. Ako je upotreba memorije problem, umjesto toga koristite kontejnere bazirane na čvorovima. sizeof 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.
