ეს არის სერიის მეორე ნაწილი C++23-ში ყველაზე შესაფერისი ასოციაციური კონტეინერის (ლექსიკონის) არჩევის შესახებ. , ამ ნაწილში კი დეტალურად განვიხილავთ შეუკვეთებელს. პირველ ნაწილში დავაფარეთ შეკვეთილი კონტეინერები შეუკვეთავი კონტეინერები ეს კონტეინერები არ იძლევა რაიმე განსაზღვრულ წესრიგს მათი გასაღებებისთვის. უფრო მეტიც, გასაღების თანმიმდევრობა შეიძლება შეიცვალოს ყოველი მოდიფიკაციით, ამიტომ პროგრამა არასოდეს უნდა დაეყრდნოს მას. ასეთი კონტეინერები ყოველთვის განხორციელდება ჰეშის რუქების სახით. ზოგადად, გასაღების დამატების, ამოღებისას ან ძიებისას, ჰეშის რუკა პირველ რიგში გამოთვლის ჰეშის გარკვეულ მნიშვნელობას ამ გასაღებიდან ჰეშის ფუნქციის გამოყენებით. ჰეში (უფრო სწორად მისი ნაწილი) შემდეგ გამოიყენება როგორც ინდექსი მიმდებარე წინასწარ გამოყოფილ მასივში. ამ მასივში თითოეულ ჩანაწერს ეწოდება. ამ მასივში ზოგიერთი ჩანაწერი ცარიელი იქნება, ზოგი შეიცავს ერთ ელემენტს, ზოგი კი შესაძლოა ერთზე მეტ ელემენტზე აისახოს ჰეშის შეჯახების გამო. ეს ხდება მაშინ, როდესაც სხვადასხვა გასაღებს აქვს ჰეშის მნიშვნელობები, რომლებიც მიუთითებს იმავე მასივის ინდექსზე. ჰეშის რუქები იყენებს სხვადასხვა სტრატეგიას ჰეშის შეჯახების მოსაგვარებლად (იხილეთ ). ჰეშ რუკაში ელემენტების რაოდენობას, რომელიც იყოფა მასივის მთლიან ზომაზე, ეწოდება . რაც უფრო მაღალია დატვირთვის კოეფიციენტი, მით მეტია შესაძლო ჰეშის შეჯახება ყოველ ახლად ჩასმულ ელემენტთან. ბუკეტი ეს ვიკიპედიის სტატია დატვირთვის ფაქტორი შეკვეთილი კონტეინერებისგან განსხვავებით, ჰეშის რუქებს არ გააჩნიათ დიაპაზონის მოთხოვნების, რანგის/არჩევის ოპერაციების მხარდაჭერა, კლავიშებზე გამეორება თანმიმდევრობით და კლავიშების ძიება, რომელიც მოცემულ კლავიშზე უფრო მცირე/დიდია. სანაცვლოდ, ჰეშის რუქები აღწევს საუკეთესო მიღწევად შესრულებას: ძიების/ჩასმის/ამოღების ოპერაციების დროის სირთულე . აქ ვამბობ "ამორტიზებულს", რადგან როდესაც ელემენტების რაოდენობა ძალიან დიდი ხდება, ჰეშ რუკას სჭირდება მისი შინაარსის ხელახლა გადახედვა, რათა შეამციროს დატვირთვის ფაქტორი (ეფექტურად გაზარდოს თაიგულების მასივი). განმეორების დროის სირთულე არის . თუმცა, მოსალოდნელია, რომ ეს იშვიათად მოხდეს, ასე რომ, საშუალოდ, თითოეული ოპერაცია კვლავ . პოტენციურად შემცირებული შესრულების კიდევ ერთი მიზეზი არის ჰეშის ფუნქცია ცუდი განაწილებით, რაც გაზრდის შეჯახების სიხშირეს. ამორტიზებულია O(1) O(n) O(1) სტანდარტული ჰეშის რუქები C++11-დან დაწყებული, სტანდარტული ბიბლიოთეკა გთავაზობთ შემდეგ ჰეშ რუქებს: ( ), ( ), ( ) და ( ). აკავშირებს გასაღებს მნიშვნელობასთან, ხოლო ინახავს მხოლოდ გასაღებს და გამოსადეგია იმის შესამოწმებლად, არის თუ არა გასაღები კონტეინერში, მაგრამ არ მოიპოვება დაკავშირებული მნიშვნელობა. კონტეინერი საშუალებას გაძლევთ შეინახოთ რამდენიმე დუბლიკატი გასაღები. std::unordered_map ბმული std::unordered_set ბმული std::unordered_multimap ბმული std::unordered_multiset ბმული Maps კომპლექტები მრავალ ყველა სტანდარტული შეუკვეთავი კონტეინერი კვანძზეა დაფუძნებული და იყენებს ჰეშის შეჯახების მოსაგვარებლად, რაც ნიშნავს, რომ ისინი ინახავს თითოეულ კლავიშს ან გასაღები-მნიშვნელობის წყვილს ცალკე დაკავშირებულ სიის კვანძში. თითოეული ახალი კვანძისთვის მეხსიერება გამოყოფილია ინდივიდუალურად, რაც არ არის განსაკუთრებით ეფექტური. ეს ასევე ხდის მონაცემთა სტრუქტურას არა CPU-ს ქეში, რადგან თითოეული გასაღების წვდომა მოითხოვს დამატებით არამიმართულებას. აი, როგორ შეიძლება გამოიყურებოდეს შიდა სტრუქტურა: ცალკეულ ჯაჭვობას unordered_map მარცხნივ არის თაიგულების მასივი, რომელიც წინასწარ არის გამოყოფილი რაღაც ფიქსირებულ ზომაზე (ჩვენს მაგალითში ). თავდაპირველად, ყველა თაიგული ცარიელია. როდესაც ჩვენ დავიწყებთ ელემენტების დამატებას ჰეშის რუკაზე, ზოგიერთი თაიგულები დაიკავებს. ზემოთ მოყვანილ მაგალითში არის ელემენტი კლავიშით (რომელიც მოხვდა თაიგულ ში), და ორი ელემენტი კლავიშებით და , ორივე ერთსა და იმავე ვედროში რადგან მათი ჰეშის მნიშვნელობები ერთმანეთს შეეჯახა. ასევე არის ელემენტი გასაღებით, რომელიც დაეშვა ვედრო ში. თითოეული თაიგული მიუთითებს დაკავშირებულ სიაზე, რომელიც იდეალურად შეიცავს არაუმეტეს ერთ ელემენტს. თაიგულები , , , და ცარიელია და მიუთითებენ ზე. 8 10 1 50 256 3 3 6 0 2 4 5 7 nullptr დავუშვათ, რომ უნდა ვიპოვოთ გასაღების მნიშვნელობა. 256 პირველ რიგში, რუკა ითვლის გასაღების ჰეშს და იღებს ნარჩენს ჰეშის მნიშვნელობის გაყოფისას თაიგულების მთლიან რაოდენობაზე (ჩვენს შემთხვევაში ). ჩვენს მაგალითში, დარჩენილი მნიშვნელობა არის . 8 3 ამის შემდეგ, რუკა იწყებს ის თაიგულით მითითებულ დაკავშირებული სიის ელემენტების კითხვას. 3 პირველ ელემენტს აქვს გასაღები , რომელიც არ არის იგივე, რაც ჩვენ ვეძებთ , ასე რომ რუკა გააგრძელებს გამეორებას. შემდეგ ელემენტს აქვს გასაღები , რომელიც ზუსტად ისაა, რაც ჩვენ გვჭირდება. შესაბამისი მნიშვნელობა არის . 50 256 256 xyz გასაღები რომ არ ყოფილიყო ლექსიკონში, რუკა ან ცარიელ თაიგულში მოხვდებოდა ან ბოლომდე იმეორებდა დაკავშირებულ სიას. ორივე შემთხვევაში, რუკა დააბრუნებს იტერატორს, რაც მიუთითებს, რომ გასაღები არ არსებობს. end თქვენ შეიძლება შეამჩნიოთ, რომ თითოეული სიის ბოლო ელემენტი მიუთითებს შემდეგი სიის პირველ ელემენტზე. ეს კეთდება ზოგიერთ განხორციელებაში გამეორების ეფექტურობის გასაუმჯობესებლად. იმის ნაცვლად, რომ შევამოწმოთ თაიგულ-ვედრო ყველა ჰეშის რუკის ელემენტზე გამეორებისას, ჩვენ შეგვიძლია გამოვიყენოთ ეს კავშირები ერთი არა ცარიელი დაკავშირებული სიიდან მეორეზე ბევრად უფრო სწრაფად გადასასვლელად. თუ ზემოთ მოცემულ ჰეშის რუკაზე მეტი ელემენტების დამატებას გავაგრძელებთ, რაღაც მომენტში ძალიან მაღალი გახდება (მაგალითად, 80%) და ჰეშის რუკა გადაწყვეტს ხელახლა გასწორებას. ის გაზრდის წინასწარ გამოყოფილ მასივს (მაგ. დან ელემენტამდე), ხელახლა გამოთვლის ჰეშებს ყველა არსებული ელემენტისთვის და ჩადებს ელემენტებს ახალ თაიგულებში. დატვირთვის ფაქტორი 8 16 სტანდარტული კონტეინერები იძლევა საცნობარო და განმეორებითი სტაბილურობის გარანტიებს, მაგრამ ისინი უფრო სუსტია, ვიდრე შეკვეთილი კონტეინერების მიერ შემოთავაზებული. არსებულ ელემენტებზე მითითებები არასოდეს ბათილდება. არსებული ელემენტების იტერატორები შეიძლება გაუქმდეს მხოლოდ მაშინ, როდესაც ახალი ელემენტის დამატება იწვევს ხელახლა გამოსწორებას, ან როდესაც ხელახალი გასწორება ხდება ხელით: #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-დან მოყოლებული, შეუკვეთავი კონტეინერები იძლევა კვანძის მანიპულირების საშუალებას: შესაძლებელია კვანძის აღება ერთი რუკიდან და გადატანა სხვა რუკაზე გასაღებისა და მნიშვნელობის კოპირების გარეშე: #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"; } } აი, რა ხდება ზემოთ მოცემულ პროგრამაში: ჰეშის შეჯახებასთან გამკლავების კიდევ ერთი სტრატეგია ეწოდება . ღია მისამართის ჰეშის რუქებში, თითოეული თაიგული ინახავს მაქსიმუმ ერთ ელემენტს. თუ bucket უკვე დაკავებულია, ელემენტი იგივე ჰეშის მნიშვნელობით მიდის სხვა უფასო თაიგულში. ასეთი ჰეშის რუქები ცდილობენ დააჯგუფონ ელემენტები მიმდებარე მეხსიერების ბლოკებში, რათა გააუმჯობესონ ეფექტურობა და მონაცემთა სტრუქტურა უფრო მოსახერხებელი გახადონ CPU-ს ქეში. C++ სტანდარტული ბიბლიოთეკა არ იძლევა ღია მისამართის ჰეშის რუქებს, მაგრამ არსებობს მესამე მხარის უამრავი ალტერნატივა. ღია მისამართით მესამე მხარის ჰეშის რუქები არის გასაოცარი ბიბლიოთეკა, რომელიც უზრუნველყოფს ჰეშის რუქების განხორციელების ფართო სპექტრს. Boost.Unordered არის , , და , რომლებიც ანალოგები არიან კონტეინერებისთვის და ყველაფერი რაც ზემოთ არის დაწერილი ეხება მათ. ეს კონტეინერები იყენებენ ცოტა უფრო რთულ შიდა სტრუქტურას "bucket ჯგუფებთან" გამეორების ეფექტურობის გასაუმჯობესებლად. boost::unordered_set boost::unordered_map boost::unordered_multiset boost::unordered_multimap std ბიბლიოთეკა ასევე უზრუნველყოფს , , და , რომლებიც ღია მისამართის კონტეინერებია. შიდა სტრუქტურა განსხვავდება ღია მისამართის ვარიანტებისგან: boost::unordered_node_set boost::unordered_node_map boost::unordered_flat_set boost::unordered_flat_map თქვენ შეგიძლიათ წაიკითხოთ მეტი შიდა სტრუქტურის შესახებ . ამ ბლოგ პოსტში კვანძზე დაფუძნებული კონტეინერები ( , ) კვლავ იყენებენ კვანძებს, რომლებზეც მითითებულია თაიგულები. ეს კონტეინერები უზრუნველყოფენ იგივე გამეორებას და მითითების სტაბილურობას გარანტირებულად, როგორც კონტეინერები და ასევე უზრუნველყოფენ იგივე API კვანძების მანიპულირებისთვის (ანუ მეთოდი). boost::unordered_node_set boost::unordered_node_map std extract ბრტყელ კონტეინერებში ( , ) კლავიშები და მნიშვნელობები ინახება უშუალოდ თაიგულის მასივში. ბრტყელი კონტეინერები ყველაზე ეფექტურია, მაგრამ იძლევა ყველაზე სუსტ გარანტიებს: გამეორებები და ყველა ელემენტის მითითება გაუქმებულია, როდესაც ხელახალი გასწორება ხდება. კვანძების მანიპულირების API საერთოდ არ არის მოწოდებული. ბრტყელი კონტეინერები შეიძლება გამოიყენონ მეტი მეხსიერება, ვიდრე კვანძებზე დაფუძნებული კონტეინერები, განსაკუთრებით თუ გასაღები ან მნიშვნელობის დიდია. boost::unordered_flat_set boost::unordered_flat_map sizeof მესამე მხარის კიდევ ერთი ბიბლიოთეკა, რომელიც ახორციელებს ღია მისამართის კონტეინერებს, არის (მოწოდებული Meta-ს მიერ). არსებობს ლექსიკონის რამდენიმე ვარიანტი, რომლებიც ძალიან ახლოსაა ზემოთ აღწერილ Boost ბიბლიოთეკის კონტეინერებთან: Folly F14 იგივეა, რაც , იგივეა, რაც . folly::F14NodeSet boost::unordered_node_set folly::F14NodeMap boost::unordered_node_map იგივეა, რაც , და იგივეა, რაც . folly::F14ValueSet boost::unordered_flat_set folly::F14ValueMap boost::unordered_flat_map / ინახავს გასაღებებს/მნიშვნელობებს შეფუთულ მიმდებარე მასივში და თაიგულები შეიცავს ინდექსებს ამ მასივში. folly::F14VectorMap folly::F14VectorSet / არის ქოლგის კლასი. ის ირჩევს ყველაზე ეფექტურ განხორციელებას (ან ან ) თქვენს მიერ მითითებულ პარამეტრებზე (როგორიცაა გასაღები და მნიშვნელობის ტიპები). folly::F14FastMap folly::F14FastSet F14Value F14Vector F14 ჰეშის რუქების საინტერესო დამატებითი ეფექტურობის მახასიათებელია . მაგალითად, თუ თქვენ გჭირდებათ ერთი და იგივე გასაღების რამდენჯერმე ძიება და მისი ჰეშირება ძვირია (მაგ. გასაღები არის სტრიქონი), შეგიძლიათ წინასწარ გაშალოთ იგი ერთხელ და შემდეგ გამოიყენოთ ყველა ჰეშ რუკაზე ზარებში, რათა თავიდან აიცილოთ ხელახალი ერთი და იგივე გასაღების მრავალჯერ ჰეშირება. ამოსავალი წერტილი არის მეთოდი ( ). წინასწარ გაშრობა F14HashToken prehash ბმული შეგიძლიათ მეტი წაიკითხოთ F14 ჰეშის კონტეინერების შიდა სტრუქტურის შესახებ . ამ FB ბლოგ პოსტში (მოწოდებული Google-ის მიერ) ასევე ახორციელებს ღია მისამართების კვანძზე დაფუძნებულ და ბრტყელ ჰეშის კონტეინერებს: , , , . ისინი მსგავსია Boost-ისა და F14-ის. მათ შესახებ მეტი შეგიძლიათ წაიკითხოთ და . Abseil Swiss Tables ბიბლიოთეკა absl::flat_hash_map absl::flat_hash_set absl::node_hash_map absl::node_hash_set აქ აქ ნაკლებად ცნობილი ბიბლიოთეკა ( ) აცხადებს, რომ ძალიან ეფექტურია უმეტეს სცენარებში. ამ ბიბლიოთეკის ავტორი იძლევა ვრცელ საორიენტაციო შედეგებს მრავალი ჰეშის რუქისთვის სხვადასხვა გამოყენების შემთხვევაში ( ). შეგიძლიათ მიჰყვეთ ამ შედეგებს, მაგრამ მიიღეთ ისინი მარილის მარცვლებთან ერთად. ყოველთვის შეამოწმეთ თქვენს მიერ არჩეული ჰეშის რუკა საწარმოო გარემოში. ბენჩმარკები ყოველთვის სინთეზურია და არ მოიცავს შემთხვევებს, როდესაც CPU და მეხსიერება ასრულებენ სხვა სამუშაოებს გარდა ჰეშ რუკის ოპერაციებისა. ბენჩმარკები ასევე არ მოიცავს შემთხვევებს, როდესაც ჰეშის რუქის მეხსიერების სხვადასხვა ნაწილები არ არის CPU ქეშში, რაც ხშირად ხდება რეალურ პროგრამებში. ankerl github ბლოგის პოსტი ჰეშის ფუნქციის ხარისხი ჰეშის ფუნქციის ხარისხი მნიშვნელოვანია საძიებო ოპერაციების დროის სირთულის შესანარჩუნებლად. ბრტყელი ჰეშის რუქები განსაკუთრებით მგრძნობიარეა ჰეშის ფუნქციის ხარისხის მიმართ. იდეალური ჰეშის ფუნქცია შეიძლება განისაზღვროს ასე: თუ კლავიშში ერთი ბიტი იცვლება, შესაბამისი ჰეშის მნიშვნელობა შემთხვევით შეიცვლება მისი ბიტების ნახევარზე. ასეთ ჰეშ ფუნქციას ეწოდება . O(1) ზვავი სამწუხაროდ, C++ სტანდარტის ბიბლიოთეკის ზოგიერთი დანერგვა მთელი რიცხვის და მაჩვენებლის ჰეშის ფუნქციების არ არის ზვავი. მაგალითად, უბრალოდ აბრუნებს მაჩვენებელს ან მთელ რიცხვს პირდაპირ ყოველგვარი დამატებითი გარდაქმნების გარეშე: . libstdc++ github გაფართოებული ჰეშის ცხრილები, როგორიცაა და განხორციელება, ამ საკითხს განიხილავს მახასიათებლის დანერგვით. თუ ჰეშის ფუნქცია არ აცხადებს თავს ზვავს, ჰეშის ცხრილი შეასრულებს დამატებით შერევის ნაბიჯს ჰეშის ხარისხის გასაუმჯობესებლად. ეს მოდის დამატებით ფასად. თუ თქვენ ახორციელებთ მორგებულ ჰეშის ფუნქციას და იცით, რომ ის ღირსეული ხარისხისაა, შეგიძლიათ მონიშნოთ ის ზვავიდან, როგორც ეს ნაჩვენებია . Boost იყენებს თვისების სახელს და F14 თვისებას ჰქვია . იდეალურ შემთხვევაში, თქვენ უნდა დაამატოთ ორივე. boost F14 hash_is_avalanching ამ მაგალითში is_avalanching folly_is_avalanching თუ იყენებთ გასაღებების ტიპებს, რომლებიც მხარდაჭერილია გარედან (მაგ. , , პოინტერები) და ნაგულისხმევი ჰეშის ფუნქციები, რომლებიც მოწოდებულია ან ით, ისინი უკვე სწორად იქნება მონიშნული საჭიროებისამებრ, და თქვენ არ დაგჭირდებათ ამაზე ფიქრი, თუ თქვენ გადაწყვიტეთ დანერგოთ პერსონალური კლავიშის ტიპი, რომელსაც დასჭირდება მორგებული ჰეშის ფუნქცია. string int boost F14 ძაფის უსაფრთხოება ყველა ზემოაღნიშნული კონტეინერი ზოგადად არ არის ნაკადისთვის უსაფრთხო და თქვენ მოგიწევთ განახორციელოთ გარე სინქრონიზაცია (მაგალითად, mutexes-ის გამოყენებით), თუ ერთმა ძაფმა შეიძლება შეცვალოს ჰეშის რუკა, როდესაც მასზე წვდება სხვა თემა. თუ ყველა თემა მხოლოდ რუკას კითხულობს, სინქრონიზაცია არ არის საჭირო. დარწმუნდით, რომ გამოიძახებთ მხოლოდ ით მონიშნულ მეთოდებს. ყველა მეთოდმა შეიძლება შეცვალოს კონტეინერი. გაითვალისწინეთ, რომ არ არის და შეცვლის კონტეინერს. მრავალწახნაგოვანი კოდის საერთო პრობლემაა: const const operator[] const std::unordered_map<std::string, bool> map; // ... if (map["key"]) { // ... } ზემოთ მოცემულ კოდში მიზანია შეამოწმოთ არის თუ არა შესაბამისი მნიშვნელობა . თუმცა, , თუ ის ჯერ არ არის. ახლად დამატებული მნიშვნელობა დაყენდება ნაგულისხმევად ( მაგალითში ზემოთ). ეს ნიშნავს, რომ ასეთი კოდი არ არის ძაფისთვის უსაფრთხო და არც ისე ოპტიმალურია. იგივე მდგომარეობის შესამოწმებლად უფრო ეფექტური და ძაფისთვის უსაფრთხო გზაა შემდეგი: key true map["key"] დაამატებს key map false if (auto it = map.find("key"); it != map.end() && it->second == true) { // ... } აქ, პირველ რიგში, ჩვენ მივიღებთ იტერატორს ელემენტზე, რომელიც იდენტიფიცირებულია "გასაღებით". შემდეგ ვამოწმებთ, არის თუ არა ელემენტი რუკაში ( ). it != map.end() თუ ასეა, ჩვენ საბოლოოდ ვამოწმებთ მის მნიშვნელობას ( ). it->second == true ამ მაგალითში, და არ ცვლის რუკას და ძიება ხდება ნაკადისთვის უსაფრთხო. თუ მიზანი იყო მხოლოდ იმის შემოწმება, არის თუ არა გასაღები რუკაზე, შეგიძლიათ უბრალოდ დარეკოთ . find end map.contains("key") ძაფით უსაფრთხო შეუკვეთავი რუქები არის ნაკადის უსაფრთხო ჰეშის რუქების რამდენიმე დანერგვა. ერთი ვარიანტია და . Boost კონტეინერები გთავაზობთ ვიზიტებზე დაფუძნებულ API-ს, რომელიც მნიშვნელოვნად განსხვავდება C++ სტანდარტული ბიბლიოთეკის მიერ მოწოდებული API-სგან. boost::concurrent_flat_set boost::concurrent_flat_map Boost.Unordered ბიბლიოთეკიდან კიდევ ერთი ვარიანტია ( ). Folly ცდილობს შეინარჩუნოს თავისი API რაც შეიძლება ახლოს C++ სტანდარტულ შეუკვეთავ კონტეინერებთან. folly::ConcurrentHashMap github არის დიდი დაბლოკვის გარეშე კონტეინერის ბიბლიოთეკა, რომელიც უზრუნველყოფს დაბლოკვის გარეშე ჰეშის რუქების რამდენიმე განხორციელებას (მაგ. , , , , ). ეს ბიბლიოთეკა დიდი ხანია არ განახლებულა და არ იძლევა დეტალურ დოკუმენტაციას, მაგრამ მე მაინც ვაზიარებ მას, რადგან მის მიერ შემოთავაზებული კონტეინერები უნიკალურია. თუ თქვენი გამოყენების შემთხვევა გულისხმობს დიდ წინააღმდეგობას ჰეშის რუკაზე, სცადეთ მიერ შემოთავაზებული ეს უბლოკო ლექსიკონები. libcds MichaelHashMap SkipListMap SkipListSet FeldmanHashMap FeldmanHashSet libcds თუ ეფექტურობა არ არის საზრუნავი, შეგიძლიათ წვდომის სინქრონიზაცია მოახდინოთ არა ძაფად უსაფრთხო რუქებზე mutexes-ის გამოყენებით. ალტერნატიულად, თქვენ შეგიძლიათ მთლიანად თავიდან აიცილოთ ერთდროული წვდომა, რაც ხშირად უფრო ეფექტურია, ვიდრე ძაფით უსაფრთხო კონტეინერების გამოყენება ან სინქრონიზაციის დამატება. რომელი გამოვიყენო? მოდით შევხედოთ შეჯამებულ პუნქტებს, რომლებიც განმარტავს, თუ როგორ უნდა აირჩიოთ ყველაზე შესაფერისი კონტეინერი. თუ გასაღების მნიშვნელობასთან დაკავშირება გჭირდებათ, აირჩიეთ , წინააღმდეგ შემთხვევაში გამოიყენეთ . რუკა ნაკრები თუ საჭიროა რუკაზე დუბლიკატი გასაღებების შენახვა, გამოიყენეთ კონტეინერი. მრავალ თუ თქვენ გჭირდებათ ყველაზე მკაცრი გამეორების და მითითების სტაბილურობის გარანტიები, გამოიყენეთ , , ან კვანძზე დაფუძნებული კონტეინერები (როგორიცაა , , , ან ). და ალბათ ყველაზე ეფექტური იქნება. std boost folly abseil std::unordered_map boost::unordered_map boost::unordered_node_map folly::F14NodeMap boost::unordered_node_... folly თუ იტერატორი და მითითების სტაბილურობა არ არის მნიშვნელოვანი (რაც ნიშნავს, თქვენ არ ინახავთ იტერატორებს, მითითებებს ან მაჩვენებლებს რუკის/დადგენის ელემენტების გარედან ან არ მოელით, რომ ისინი ძალაში დარჩებიან რუკის შეცვლის შემდეგ), აირჩიეთ ბრტყელი კონტეინერი (მაგ. როგორც ან ). boost::unordered_flat_map folly::F14FastMap ბრტყელი კონტეინერები უფრო მეტ მეხსიერებას იყენებენ, ვიდრე კვანძებზე დაფუძნებულ კონტეინერებს, განსაკუთრებით მაშინ, როდესაც გასაღების და/ან მნიშვნელობა დიდია. თუ მეხსიერების გამოყენება შემაშფოთებელია, გამოიყენეთ კვანძებზე დაფუძნებული კონტეინერები. sizeof F14 კონტეინერები უზრუნველყოფს წინასწარ გახეხვის ფუნქციას დამატებითი ეფექტურობისთვის. თუ რამდენჯერმე მოძებნით/დაამატებთ/აშორებთ იდენტურ გასაღებს, F14 შესაძლებელს გახდის დაზოგოთ ჰეშინგის ღირებულება კლავიშების წინასწარ გაშიშვლებით. ყველა ზემოაღნიშნული პუნქტი ეხება ერთნაკადიანი კონტეინერის გამოყენებას (ან მრავალნაკადიანი წაკითხვის წვდომას თანმხლები ცვლილებების გარეშე). თუ საჭიროა მრავალძაფიანი მოდიფიკაციები, აირჩიეთ ზემოთ ჩამოთვლილი ერთ-ერთი ძაფის უსაფრთხო ვარიანტი. მათ შეუძლიათ აჩვენონ განსხვავებული შესრულება რეალურ წარმოების კოდში, ამიტომ განიხილეთ მათი ტესტირება თქვენს აპლიკაციაში და შეადარეთ შედეგები.
