Eli licandelo lesibini kuluhlu malunga nokukhetha eyona nto ifanelekileyo yokudibanisa i-container (isichazi-magama) kwi-C ++23. , kwaye kweli candelo, siza kuxoxa ngokungacwangciswanga ngokweenkcukacha. Kwinxalenye yokuqala, sigubungele izikhongozeli ezi-odolweyo Izikhongozeli ezingacwangciswanga Ezi zikhongozeli aziboneleli naluphi na ulandelelwano oluchaziweyo lwezitshixo zazo. Ngaphezu koko, i-oda ephambili inokutshintsha ngokuguqulwa ngalunye, ngoko ke inkqubo akufanele ithembele kuyo. Izikhongozeli ezinjalo zihlala ziphunyezwa njengeemephu ze-hash. Ngokubanzi, xa udibanisa, ususa, okanye ukhangela isitshixo, imephu ye-hash iqala ngokubala ixabiso lehash elidityanisiweyo ukusuka kwelo qhosha usebenzisa umsebenzi we-hash. I-hash (okanye indawo yayo) isetyenziswa njengesalathiso kuluhlu oludibeneyo olwabiwe kwangaphambili. Ungeno ngalunye kolu luhlu lubizwa ngokuba . Amanye amangeno kolo luhlu azakungabi nanto, amanye azakuqulatha into enye, kwaye amanye angenza imephu kwizinto ezingaphezulu kwesinye ngenxa yongquzulwano lwehash. Oku kwenzeka xa izitshixo ezahlukeneyo zinexabiso le-hash elalatha kwisalathiso soluhlu olufanayo. Iimephu zeHash zisebenzisa izicwangciso ezahlukeneyo zokujongana nokungqubana kwe-hash (bona ). Inani lezinto ezikwimephu ye-hash ezahlulwe ngobungakanani obupheleleyo boluhlu kuthiwa . Okukhona uphezulu umba womthwalo, kokukhona ungquzulwano lwe-hash lunokwenzeka ngento nganye esanda kufakwa. yibhakethi eli nqaku le-Wikipedia yimeko yomthwalo Ngokuchasene nezikhongozeli ezi-odolweyo, iimephu zehash aziyixhasi imibuzo yoluhlu, irenki/khetha imisebenzi, ukuphindaphinda izitshixo ngokulandelelana, kunye nokukhangela isitshixo esincinci/esikhulu kunesitshixo esinikiweyo. Ngembuyekezo, iimephu zehash zifikelela kowona msebenzi ufezekayo: ixesha elintsonkothileyo lophendlo/ukufaka/ukususwa kwemisebenzi . Ndithi "i-amortized" apha, kuba xa inani lezinto lisiba likhulu kakhulu, imephu ye-hash kufuneka iphinde ihlaziye imixholo yayo ukunciphisa umthamo womthwalo (ukukhulisa ngokufanelekileyo uluhlu lwebhakethi). Ubunzima bexesha lokuhlaziya kwakhona ngu . Nangona kunjalo, kulindeleke ukuba yenzeke ngokunqabileyo, ngoko ke ngokomyinge, umsebenzi ngamnye usengu . Esinye isizathu sokusebenza okunokuthi kuncitshiswe ngumsebenzi we-hash kunye nokusabalalisa okungahambi kakuhle, okuya kwandisa ukuphindaphinda kokungqubana. ihlawulelwe O(1) O(n) O(1) Iimephu zehash eziqhelekileyo Ukuqala nge-C++11, ilayibrari eqhelekileyo ibonelela ngezi mephu zilandelayo: ( ), ( ), ( ), kunye ( ). zinxulumanisa isitshixo nexabiso, ngelixa zigcina isitshixo kuphela kwaye ziluncedo ukujonga ukuba isitshixo sikhona na kwisingxobo, kodwa singabuyiseli ixabiso elinxulumeneyo. Izikhongozeli zivumela ukugcina izitshixo eziphindiweyo ezininzi. std::unordered_map ikhonkco std::unordered_set ikhonkco std::unordered_multimap ikhonkco std::unordered_multiset ikhonkco Iimephu iiseti ezininzi Zonke izikhongozeli ezisemgangathweni ezingacwangciswanga zisekwe kwi-node kwaye zisebenzisa ukujongana nokungqubana kwe-hash, okuthetha ukuba, zigcina isitshixo ngasinye okanye isitshixo sexabiso lesibini kwindawo yoluhlu oludityanisiweyo olwahlukileyo. Imemori yendawo nganye entsha yabelwe umntu ngamnye, nto leyo engasebenzi kakuhle. Oku kwenza ukuba ulwakhiwo lwedatha lungabi yi-CPU-cache-friendly, kuba ufikelelo ngalunye olungundoqo lufuna ulwalathiso olongezelelweyo. Nantsi indlela i isakhiwo sangaphakathi esinokujongeka ngayo: i-Separate chaining unordered_map Ngakwesobunxele, kukho uluhlu lweebhakethi, olwabelwe kwangaphambili kumlinganiselo othile osisigxina ( kumzekelo wethu). Ekuqaleni, zonke iibhakethi azinanto. Xa siqala ukongeza izinto kwimephu ye-hash, ezinye iibhakethi ziya kuhlala. Kulo mzekelo ungasentla, kukho into enesitshixo esingu- (esingene kwi-emele ), kunye neempawu ezimbini ezinezitshixo kunye , zombini ziphelele kwibhakethi enye yesi kuba amaxabiso ehashi ayangqubana. Kukwakho into eneqhosha lesi - , elithe lahlala kwibhakethi yesi . Ibhakethi ngalinye lalatha kuluhlu oludityanisiweyo, oluqulathe ngokufanelekileyo into engekho ngaphezu kwesinye. Iibhakethi , , , , no azinanto kwaye zikhomba kwi . 8 10 1 50 256 3 3 6 0 2 4 5 7 nullptr Makhe sicinge ukuba kufuneka sifumane ixabiso lesitshixo sama- . 256 Okokuqala, imephu ibala i-hash engundoqo kwaye ifumana intsalela xa isahlula ixabiso le-hash ngenani elipheleleyo leebhakethi ( kwimeko yethu). Kumzekelo wethu, ixabiso eliseleyo ngu . 8 3 Emva koko, imephu iqala ukufunda izinto zoluhlu oludityanisiweyo olukhonjwe ngebhakethi . 3 Into yokuqala inesitshixo esingu , esingafaniyo no- esikhangelayo, ngoko ke imephu iya kuqhubeka ukuphinda-phinda. Into elandelayo inesitshixo , eyilelo kanye esiyifunayo. Ixabiso elihambelanayo ngu . 50 256 256 xyz Ukuba isitshixo besingekho kwisichazi-magama, imephu ibinokubetha i-emele engenanto okanye iphindaphinde kuluhlu oludityanisiweyo kude kube sekupheleni. Kuzo zombini ezi meko, imephu ingabuyisela esichazayo, esibonisa ukuba isitshixo asikho. end Unokuqaphela ukuba inqaku lokugqibela loluhlu ngalunye lalatha kwinto yokuqala yoluhlu olulandelayo. Oku kwenziwa kwezinye iinkqubo zokuphumeza ukuphucula ukusebenza kakuhle kokuphindaphinda. Endaweni yokujonga ibhakethi ngebhakethi xa uphinda-phinda phezu kwayo yonke imephu yehash, sinokusebenzisa olo nxibelelwano ukutsiba ukusuka kuluhlu olungenanto oludityanisiweyo ukuya kolunye ngokukhawuleza okukhulu. Ukuba siqhubeka nokongeza izinto kwimephu ye-hash engentla, ngaxa lithile iya kuba phezulu kakhulu (umzekelo, 80%), kwaye imephu ye-hash iya kuthatha isigqibo sokuphinda ihoxise. Iza kukhulisa uluhlu olwabiwe kwangaphambili (umz. ukusuka kwisi ukuya kwi iielementi), buyisela i-hashes yazo zonke izinto ezikhoyo, kwaye ibeke izinto kwiibhakethi ezintsha. into yomthwalo 8 16 Izikhongozeli ezisemgangathweni zibonelela ngereferensi kunye neziqinisekiso zozinzo eziphindaphindayo, kodwa zibuthathaka kunezo zinikezelwa zizikhongozeli ezi-odolweyo. Iimbekiselo kwiziqalelo ezikhoyo azinakuze zingasebenzi. I-Iterators kwiziqalelo esele zikho zinokwenziwa zingasebenzi kuphela xa udibaniso lwento entsha ibangela ukuphinda-phinda, okanye xa ukurehasha kwakhona kuqalwa ngesandla: #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"; } Ukusukela kwi-C++17, izikhongozeli ezingacwangciswanga zivumela ukuqhathwa kwe-node: kuyenzeka ukuba uthathe i-node kwimephu enye kwaye uyise kwenye imephu ngaphandle kokukopa isitshixo kunye nexabiso: #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"; } } Oku kwenzeka kule nkqubo ingentla: Esinye isicwangciso sokujongana nokungqubana kwe-hash kuthiwa . Kwiimephu ezineedilesi ezivulekileyo ze-hash, ibhakethi ngalinye ligcina eyona nto inye. Ukuba ibhakethi sele lihleli, into enexabiso elifanayo le-hash iya kwelinye ibhakethi lasimahla. Ezo mephu ze-hash zizama ukuhlanganisa izinto kwiibhloko zememori ezidityanisiweyo ukuphucula ukusebenza kakuhle kunye nokwenza ulwakhiwo lwedatha lube lula ngakumbi kwi-CPU cache. Ithala leencwadi eliqhelekileyo le-C++ aliboneleli ngeedilesi ezivulekileyo zeemephu zehash, kodwa zininzi iindlela ezizezinye zomntu wesithathu. Vula idilesi Iimephu ze-hash zomntu wesithathu lithala leencwadi elimangalisayo elibonelela ngoluhlu olubanzi lokuphunyezwa kweemephu zehash. I-Boost.Unordered Kukho , , , kwaye , ezizianalogu zezikhongozeli , kwaye yonke into ebhaliweyo ngasentla iyasebenza kuzo. Ezi zikhongozeli zisebenzisa ubume obuntsonkothileyo bangaphakathi "namaqela amabhakethi" ukuphucula ukusebenza kakuhle kokuphindaphinda. boost::unordered_set boost::unordered_map boost::unordered_multiset boost::unordered_multimap std Ithala leencwadi likwabonelela , , , kunye ne , ezizikhongozeli zeedilesi ezivuliweyo. Ulwakhiwo lwangaphakathi lwahlukile kwiintlobo ngeentlobo zeedilesi ezivulekileyo: boost::unordered_node_set boost::unordered_node_map boost::unordered_flat_set boost::unordered_flat_map Unokufunda ngakumbi malunga nesakhiwo sangaphakathi . kule post blog Izikhongozeli ezisekelwe kwi-node ( , ) zisasebenzisa iindawo, ezikhonjwe ngamabhakethi. Ezi zikhongozeli zibonelela nge-iterator efanayo kunye nozinzo lwereferensi oluqinisekisiweyo njengezikhongozeli ze kwaye zibonelela nge-API efanayo yokuguqulwa kwe-node (okt indlela ). boost::unordered_node_set boost::unordered_node_map std extract Kwizikhongozeli ezisicaba ( , ), izitshixo kunye namaxabiso agcinwa ngokuthe ngqo kuluhlu lwebhakethi. Izikhongozeli ezisicaba zezona zisebenza kakuhle, kodwa zinika ezona ziqinisekiso zibuthathaka: iziqinisekiso kunye neembekiselo kuzo zonke iindawo azivumelekanga xa ukuhanjwa kwakhona kusenzeka. Node manipulation API ayibonelelwanga kwaphela. Izikhongozeli ezimcaba zinokusebenzisa inkumbulo eninzi kunezo zisekwe kwindawo ekuyi node, ngakumbi ukuba isitshixo okanye bexabiso bukhulu. boost::unordered_flat_set boost::unordered_flat_map sizeof Elinye ithala leencwadi lomntu wesithathu elisebenzisa izikhongozeli ezineedilesi ezivulekileyo yiFolly (ebonelelwe yiMeta). Kukho iinguqulelo ezimbalwa zesichazi-magama ezisondele kakhulu kwizikhongozeli zethala leencwadi le-Boost ezichazwe ngasentla: F14 iyafana ne , iyafana ne . folly::F14NodeSet boost::unordered_node_set folly::F14NodeMap boost::unordered_node_map iyafana , kunye iyafana ne . folly::F14ValueSet boost::unordered_flat_set folly::F14ValueMap boost::unordered_flat_map / gcina izitshixo/amaxabiso apakishwe kuluhlu oludityanisiweyo, kwaye amabhakethi aqulathe izalathisi kuloluhlu. folly::F14VectorMap folly::F14VectorSet / yiklasi yeambrela. Ikhetha olona phumezo lusebenzayo (ingaba okanye ) ngokusekelwe kwiiparamitha ozikhankanyayo (ezifana nezitshixo kunye neentlobo zexabiso). folly::F14FastMap folly::F14FastSet F14Value F14Vector Into enomdla eyongezelelweyo esebenzayo yeemephu ze-F14 ze-hash ku . Umzekelo, ukuba ufuna ukukhangela isitshixo esinye amaxesha amaninzi, kwaye i-hashing yayo iyabiza (umzekelo, isitshixo yintambo), ungayifaka kwangaphambili kube kanye, kwaye usebenzise i kuzo zonke iifowuni ze-hash emva kwexesha ukunqanda ukuphinda- Hashing iqhosha elifanayo amaxesha amaninzi. Indawo yokuqala yindlela ye ( ). -prehashing F14HashToken prehash ikhonkco Unokufunda ngakumbi malunga nolwakhiwo lwangaphakathi lwezikhongozeli ze-hash ze-F14 . kule post ye-blog ye-FB (ebonelelwe nguGoogle) likwasebenzisa iidilesi ezivulekileyo ezisekelwe kwi-node-based kunye nezikhongozeli zehashi ezisicaba: , , , . Zifana ne-Boost kunye ne-F14. Unokufunda ngakumbi malunga nabo kwaye . Ithala leencwadi le-Abseil Swiss Tables absl::flat_hash_map absl::flat_hash_set absl::node_hash_map absl::node_hash_set apha apha Ithala leencwadi elaziwayo kakhulu ( ) libanga ukuba lisebenza kakhulu kwiimeko ezininzi. Umbhali weli thala leencwadi ubonelela ngeziphumo ezibanzi zebenchmark kwiimephu ezininzi ze-hash kwiimeko ezahlukeneyo zokusetyenziswa ( ). Unokulandela ezi ziphumo, kodwa zithathe ngengqolowa yetyuwa. Soloko uvavanya imephu ye-hash oyikhethayo kwindawo yemveliso. Ibenchmarks zisoloko zenziwe kwaye azikhuphi iimeko xa i-CPU kunye nememori zisenza omnye umsebenzi ngaphandle kwemisebenzi yemephu yehash. Iibenchmarks nazo aziwaquki iimeko xa iindawo ezahlukeneyo zememori yemephu ye-hash zingekho kwi-cache ye-CPU, eya kwenzeka rhoqo kwiinkqubo zokwenyani. ankerl github isithuba seblogi Umgangatho womsebenzi weHash Umgangatho womsebenzi weHash ubalulekile ukugcina ukuntsonkotha kwexesha lemisebenzi yokujonga . Iimephu zehash ezisicaba zinobuntununtunu kumgangatho wokusebenza kwehashi. Umsebenzi we-hash ofanelekileyo unokuchazwa ngolu hlobo: ukuba isuntswana elinye kwisitshixo sitshintsha, ixabiso elihambelanayo le-hash liyakutshintsha isiqingatha samasuntswana alo ngokungakhethiyo. Umsebenzi onjalo we-hash ubizwa ngokuba . O(1) yi-avalanching Ngelishwa, ukuphunyezwa kwethala leencwadi eliqhelekileyo le-C++ lenani elipheleleyo kunye nemisebenzi ye-hash yesalathi asiyiyo i-avalanching. Umzekelo, ibuyisela ngokulula isalathisi okanye ixabiso elipheleleyo ngokuthe ngqo ngaphandle kotshintsho olongezelelweyo: . libstdc++ github Iitafile ze-hash eziphucukileyo, ezifana kunye nokuphunyezwa kwe , jongana nalo mba ngokwazisa i trait. Ukuba umsebenzi we-hash awuzichazi njenge-avalanching, itafile ye-hash iya kwenza inyathelo elongezelelweyo lokuxuba ukuphucula umgangatho we-hash. Oku kuza ngeendleko ezongezelelweyo. Ukuba uphumeza umsebenzi we-hash wesiko, kwaye uyazi ukuba ungowomgangatho ondilisekileyo, ungawuphawula ube shushu njengoko kubonisiwe . I-Boost isebenzisa igama lepropathi, kunye nepropati ye F14 ibizwa ngokuba . Ngokufanelekileyo, kufuneka udibanise zombini. boost F14 hash_is_avalanching kulo mzekelo is_avalanching folly_is_avalanching Ukuba usebenzisa iintlobo ezingundoqo ezixhaswayo ngaphandle kwebhokisi (umzekelo, , , izikhombisi) kunye nemisebenzi ye-hash engagqibekanga enikezwe yi okanye , ziya kuba sele ziphawulwe ngokuchanekileyo njengoko kufuneka, kwaye akuyi kufuneka ucinge ngale nto ngaphandle kokuba uthatha isigqibo sokuphumeza uhlobo lwesitshixo sesiko, oluya kufuna umsebenzi we-hash wesiko. string int boost F14 Ukhuseleko lomsonto Zonke ezi zikhongozeli zingentla azikho intambo-ekhuselekileyo ngokubanzi, kwaye kuya kufuneka uphumeze ungqamaniso lwangaphandle (umzekelo, usebenzisa imutexes) ukuba intambo enye inokuguqula imephu yehash xa omnye umsonto ufikelela kuyo. Ukuba yonke imisonto ifunda imephu kuphela, akukho lungqamaniso lufunekayo. Qinisekisa ukuba ubiza kuphela iindlela eziphawulwe nge . Zonke iindlela ezinokuthi zisiguqule isikhongozeli. Gcina ukhumbula ukuba akakho kwaye uya kuguqula isikhongozeli. Umhadi oqhelekileyo kwikhowudi enemisonto emininzi ngulo: const const operator[] const std::unordered_map<std::string, bool> map; // ... if (map["key"]) { // ... } Kwikhowudi engentla, injongo kukukhangela ukuba ixabiso elihambelana . Nangona kunjalo, ukuba ayikabikho. Ixabiso elitsha longezwa lizakumiselwa kokungagqibekanga ( kulo mzekelo ungentla). Oku kuthetha ukuba, ikhowudi enjalo ayikhuselekanga ngomsonto, kwaye ayilunganga kakhulu. Indlela esebenzayo nekhuselekileyo yokujonga imeko efanayo yile ilandelayo: key true map["key"] iyakongeza key map false if (auto it = map.find("key"); it != map.end() && it->second == true) { // ... } Apha, siqala sifumana i-iterator kwinto echongiweyo nge "key". Emva koko sijonga ukuba into ikhona kwimephu ( ). it != map.end() Ukuba kunjalo, ekugqibeleni sijonga ixabiso layo ( ). it->second == true Kulo mzekelo, kwaye musa ukuyiguqula imephu, kwaye uphendlo kuba imisonto-ekhuselekileyo. Ukuba injongo ibikukukhangela ukuba isitshixo sikhona na kwimephu, ungafowunela ngokulula . find end map.contains("key") Iimephu ezingacwangciswanga ngemisonto ekhuselekileyo Kukho umiliselo olumbalwa lweemephu zehashi ezikhuselekileyo. Olunye ukhetho lunyuso kunye esuka . Izikhongozeli zokunyusa zibonelela nge-API esekwe kutyelelo eyahluke kakhulu kwi-API ebonelelwa yilayibrari eqhelekileyo ye-C ++. boost::concurrent_flat_set boost::concurrent_flat_map kwiBoost.Ilayibrari engacwangciswanga Olunye ukhetho ( ). I-Folly izama ukugcina i-API yayo ikufutshane kangangoko kunokwenzeka kwizikhongozeli ze-C++ ezingacwangciswanga. folly::ConcurrentHashMap github yithala leencwadi elikhulu elingenazitshixo elinesingxobo esibonelela ngomiliselo oluninzi lweemephu zehashi ezingatshixwanga (umzekelo , , , , ). Eli thala leencwadi alikahlaziywa kangangexesha elithile kwaye aliboneleli ngamaxwebhu aneenkcukacha, kodwa ndisabelana ngalo kuba izikhongozeli elizinikezelayo zahlukile. Ukuba imeko yakho yosetyenziso ithetha ukruthakruthwano oluphezulu kwimephu yehash, zama ezi zichazi-magama zingatshixwanga zinikelwe zii . i-libcds MichaelHashMap SkipListMap SkipListSet FeldmanHashMap FeldmanHashSet libcds Ukuba ukusebenza kakuhle akuyongxaki, ungangqamanisa ufikelelo kwiimephu ezingakhuselekanga usebenzisa imutexes. Kungenjalo, unokukuphepha ngokupheleleyo ukufikelela ngaxeshanye, okuhlala kusebenza ngakumbi kunokusebenzisa izikhongozeli ezikhuselekileyo zomsonto okanye ukongeza ungqamaniso. Ndisebenzisa eyiphi? Makhe sijonge amanqaku ashwankathelweyo achaza indlela yokukhetha esona sikhongozeli sifanelekileyo. Ukuba ufuna ukudibanisa isitshixo kunye nexabiso, khetha , kungenjalo, sebenzisa . imephu isethi Ukuba kuyimfuneko ukugcina izitshixo eziphindwe kabini kwimephu, sebenzisa izikhongozeli . ezininzi Ukuba ufuna i-iterator engqongqo kunye neziqinisekiso zozinzo lwereferensi, sebenzisa , , , okanye node-based containers (ezifana ne , , , okanye ). kwaye buya kuba kobona busebenza kakuhle. std boost folly abseil std::unordered_map boost::unordered_map boost::unordered_node_map folly::F14NodeMap boost::unordered_node_... folly Ukuba i-iterator kunye nozinzo lwereferensi ayibalulekanga (oku kuthetha ukuba, awugcini iziphindaphindo, iimbekiselo, okanye izikhombisi kwimephu/ukuseta izinto ngaphandle okanye ungalindelanga ukuba zihlale zisemthethweni emva kokuba imephu ilungisiwe), emva koko khetha isikhongozeli esisicaba (esinjalo okanye ). boost::unordered_flat_map folly::F14FastMap Izikhongozeli ezimcaba zisebenzisa inkumbulo eninzi kunezo zisekwe kwindawo ekudityanwa kuzo, ngakumbi xa besitshixo kunye/okanye ixabiso likhulu. Ukuba usetyenziso lwememori yinkxalabo, sebenzisa izikhongozeli ezisekwe kwi-node endaweni yoko. sizeof Izikhongozeli ze-F14 zibonelela ngokusebenza kwangaphambili kokusebenza ngokufanelekileyo. Ukuba ukhangela/ukongeza/ususa izitshixo ezifanayo amaxesha amaninzi, F14 iyakwenza kube nokwenzeka ukugcina ixabiso le-hashing ngokuqalisa izitshixo. Onke la manqaku angasentla asebenza kusetyenziso lwesikhongozeli esinomsonto omnye (okanye ukufikelela kokufunda okunemisonto emininzi ngaphandle kohlengahlengiso olufanayo). Ukuba uhlengahlengiso oluneentambo ezininzi luyafuneka, khetha enye yeendlela ezikhuselekileyo ezidweliswe ngasentla. Bangabonisa ukusebenza okwahlukileyo kwikhowudi yokwenyani yokuvelisa, ngoko cinga ukubavavanya kwisicelo sakho kwaye uthelekise iziphumo.
