இது C++23 இல் மிகவும் பொருத்தமான துணை கொள்கலனை (அகராதி) தேர்ந்தெடுப்பது பற்றிய தொடரின் இரண்டாம் பகுதி. முதல் பகுதியில், ஆர்டர் செய்யப்பட்ட கொள்கலன்களை நாங்கள் உள்ளடக்கியுள்ளோம் , மேலும் இந்த பகுதியில், வரிசைப்படுத்தப்படாதவற்றை விரிவாக விவாதிப்போம்.

ஆர்டர் செய்யப்படாத கொள்கலன்கள்

இந்த கொள்கலன்கள் அவற்றின் விசைகளுக்கு வரையறுக்கப்பட்ட வரிசையை வழங்கவில்லை. மேலும், ஒவ்வொரு மாற்றத்திலும் முக்கிய வரிசை மாறலாம், எனவே நிரல் அதை ஒருபோதும் நம்பக்கூடாது. அத்தகைய கொள்கலன்கள் எப்போதும் ஹாஷ் வரைபடங்களாக செயல்படுத்தப்படுகின்றன.

பொதுவாக, ஒரு விசையைச் சேர்க்கும்போது, அகற்றும்போது அல்லது தேடும்போது, ஹாஷ் மேப் முதலில் ஹாஷ் செயல்பாட்டைப் பயன்படுத்தி அந்த விசையிலிருந்து சில ஒருங்கிணைந்த ஹாஷ் மதிப்பைக் கணக்கிடுகிறது. ஹாஷ் (அல்லது அதற்குப் பதிலாக அதன் பகுதி) பின்னர் தொடர்ச்சியான முன் ஒதுக்கப்பட்ட வரிசையில் ஒரு குறியீட்டாகப் பயன்படுத்தப்படுகிறது. இந்த வரிசையில் உள்ள ஒவ்வொரு நுழைவும் ஒரு வாளி என்று அழைக்கப்படுகிறது. அந்த வரிசையில் சில உள்ளீடுகள் காலியாக இருக்கும், சில ஒற்றை உறுப்பு கொண்டிருக்கும், மேலும் சில ஹாஷ் மோதல்கள் காரணமாக ஒன்றுக்கு மேற்பட்ட உறுப்புகளுக்கு வரைபடமாக இருக்கலாம். வெவ்வேறு விசைகள் ஒரே அணிவரிசை குறியீட்டை சுட்டிக்காட்டும் ஹாஷ் மதிப்புகளைக் கொண்டிருக்கும்போது இது நிகழ்கிறது. ஹாஷ் வரைபடங்கள் ஹாஷ் மோதல்களைச் சமாளிக்க பல்வேறு உத்திகளைப் பயன்படுத்துகின்றன ( இந்த விக்கிபீடியா கட்டுரையைப் பார்க்கவும்). ஹாஷ் வரைபடத்தில் உள்ள உறுப்புகளின் எண்ணிக்கை வரிசையின் மொத்த அளவால் வகுக்கப்படுவது சுமை காரணி எனப்படும். சுமை காரணி அதிகமாக இருந்தால், புதிதாகச் செருகப்பட்ட ஒவ்வொரு உறுப்புக்கும் ஹாஷ் மோதல்கள் சாத்தியமாகும்.

ஆர்டர் செய்யப்பட்ட கொள்கலன்களுக்கு மாறாக, ஹாஷ் வரைபடங்கள் வரம்பு வினவல்களை ஆதரிக்காது, தரவரிசை/தேர்ந்தெடுக்கப்பட்ட செயல்பாடுகள், விசைகளை வரிசைப்படுத்துதல் மற்றும் கொடுக்கப்பட்ட விசையை விட சிறிய/பெரிய விசையைத் தேடுதல். பதிலுக்கு, ஹாஷ் வரைபடங்கள் சிறந்த அடையக்கூடிய செயல்திறனை அடைகின்றன: தேடல்/செருகுத்தல்/அகற்றுதல் செயல்பாடுகளின் நேரச் சிக்கலானது O(1) குறைக்கப்பட்டது . நான் இங்கே "அமோர்டைஸ்" என்று சொல்கிறேன், ஏனென்றால் தனிமங்களின் எண்ணிக்கை மிக அதிகமாக இருக்கும்போது, சுமை காரணியைக் குறைக்க ஹாஷ் வரைபடம் அதன் உள்ளடக்கங்களை மீண்டும் மாற்ற வேண்டும் (பக்கெட் வரிசையை திறம்பட வளர்க்கிறது). ரீஹாஷிங்கின் நேரம் சிக்கலானது O(n) . இருப்பினும், இது அரிதாக நடக்கும் என்று எதிர்பார்க்கப்படுகிறது, எனவே சராசரியாக, ஒவ்வொரு செயல்பாடும் இன்னும் O(1) . செயல்திறன் குறைவதற்கான மற்றொரு காரணம் மோசமான விநியோகத்துடன் கூடிய ஹாஷ் செயல்பாடு ஆகும், இது மோதல்களின் அதிர்வெண்ணை அதிகரிக்கும்.

நிலையான ஹாஷ் வரைபடங்கள்

C++11 இல் தொடங்கி, நிலையான நூலகம் பின்வரும் ஹாஷ் வரைபடங்களை வழங்குகிறது: std::unordered_map ( இணைப்பு ), std::unordered_set ( இணைப்பு ), std::unordered_multimap ( இணைப்பு ), மற்றும் std::unordered_multiset ( இணைப்பு ). வரைபடங்கள் ஒரு விசையை மதிப்புடன் தொடர்புபடுத்துகின்றன, அதே சமயம் தொகுப்புகள் விசையை மட்டுமே சேமித்து வைக்கின்றன மற்றும் கொள்கலனில் விசை இருக்கிறதா என்பதைச் சரிபார்க்க பயனுள்ளதாக இருக்கும், ஆனால் தொடர்புடைய மதிப்பை மீட்டெடுக்க முடியாது. பல கொள்கலன்கள் பல நகல் விசைகளை சேமிக்க அனுமதிக்கின்றன.

அனைத்து நிலையான வரிசைப்படுத்தப்படாத கொள்கலன்களும் முனை அடிப்படையிலானவை மற்றும் ஹாஷ் மோதல்களைச் சமாளிக்க தனி சங்கிலியைப் பயன்படுத்துகின்றன, அதாவது, அவை ஒவ்வொரு விசை அல்லது முக்கிய மதிப்பு ஜோடியையும் தனித்தனி இணைக்கப்பட்ட பட்டியல் முனையில் சேமிக்கின்றன. ஒவ்வொரு புதிய முனைக்கும் நினைவகம் தனித்தனியாக ஒதுக்கப்படுகிறது, இது குறிப்பாக திறமையானது அல்ல. ஒவ்வொரு முக்கிய அணுகலுக்கும் கூடுதல் மறைமுகம் தேவைப்படுவதால், இது தரவு கட்டமைப்பை 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"; } }

மேலே உள்ள திட்டத்தில் இதுதான் நடக்கிறது:

ஹாஷ் மோதல்களைச் சமாளிப்பதற்கான மற்றொரு உத்தி திறந்த முகவரி என்று அழைக்கப்படுகிறது. திறந்த முகவரி ஹாஷ் வரைபடங்களில், ஒவ்வொரு வாளியும் அதிகபட்சம் ஒரு உறுப்பைச் சேமிக்கும். பக்கெட் ஏற்கனவே ஆக்கிரமிக்கப்பட்டிருந்தால், அதே ஹாஷ் மதிப்பைக் கொண்ட உறுப்பு வேறு சில இலவச பக்கெட்டுகளுக்குச் செல்லும். இத்தகைய ஹாஷ் வரைபடங்கள் செயல்திறனை மேம்படுத்தவும், தரவுக் கட்டமைப்பை மேலும் CPU கேச்-நட்பாகவும் மாற்ற, தொடர்ச்சியான நினைவகத் தொகுதிகளில் உள்ள கூறுகளைக் குழுவாக்க முயற்சிக்கின்றன. C++ நிலையான நூலகம் திறந்த முகவரி ஹாஷ் வரைபடங்களை வழங்காது, ஆனால் ஏராளமான மூன்றாம் தரப்பு மாற்றுகள் உள்ளன.

மூன்றாம் தரப்பு ஹாஷ் வரைபடங்கள்

Boost.Unordered என்பது ஒரு அற்புதமான நூலகமாகும், இது பரந்த அளவிலான ஹாஷ் வரைபட செயலாக்கங்களை வழங்குகிறது.

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 , இவை திறந்த முகவரி கொள்கலன்களையும் வழங்குகிறது. உள் அமைப்பு திறந்த முகவரி மாறுபாடுகளிலிருந்து வேறுபட்டது:

இந்த வலைப்பதிவு இடுகையில் உள் கட்டமைப்பைப் பற்றி மேலும் படிக்கலாம்.

முனை அடிப்படையிலான கொள்கலன்கள் ( boost::unordered_node_set , boost::unordered_node_map ) இன்னும் முனைகளைப் பயன்படுத்துகின்றன, அவை வாளிகளால் சுட்டிக்காட்டப்படுகின்றன. இந்தக் கொள்கலன்கள் std கண்டெய்னர்களுக்கு உத்தரவாதம் அளிக்கப்பட்ட அதே மறு செய்கை மற்றும் குறிப்பு நிலைத்தன்மையை வழங்குகின்றன, மேலும் முனை கையாளுதலுக்கான அதே API ஐ வழங்குகின்றன (அதாவது extract முறை).

தட்டையான கொள்கலன்களில் ( boost::unordered_flat_set , boost::unordered_flat_map ), விசைகள் மற்றும் மதிப்புகள் நேரடியாக பக்கெட் வரிசையில் சேமிக்கப்படும். தட்டையான கொள்கலன்கள் மிகவும் திறமையானவை, ஆனால் பலவீனமான உத்தரவாதங்களை வழங்குகின்றன: மறுசீரமைப்பு நிகழும்போது அனைத்து உறுப்புகளின் மறு செய்கைகள் மற்றும் குறிப்புகள் செல்லாதவை. முனை கையாளுதல் API வழங்கப்படவில்லை. தட்டையான கொள்கலன்கள் முனை அடிப்படையிலானவற்றை விட அதிக நினைவகத்தைப் பயன்படுத்தக்கூடும், குறிப்பாக விசை அல்லது மதிப்பு sizeof பெரியதாக இருந்தால்.

திறந்த முகவரி கொள்கலன்களை செயல்படுத்தும் மற்றொரு மூன்றாம் தரப்பு நூலகம் 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 முறை ( இணைப்பு ) ஆகும்.

இந்த FB வலைப்பதிவு இடுகையில் F14 ஹாஷ் கொள்கலன்களின் உள் கட்டமைப்பைப் பற்றி மேலும் படிக்கலாம்.

Abseil Swiss Tables நூலகம் (Google ஆல் வழங்கப்படுகிறது) முனை அடிப்படையிலான மற்றும் தட்டையான ஹாஷ் கொள்கலன்களையும் செயல்படுத்துகிறது: absl::flat_hash_map , absl::flat_hash_set , absl::node_hash_map , absl::node_hash_set . அவை பூஸ்ட் மற்றும் எஃப் 14 போன்றவை. நீங்கள் அவர்களைப் பற்றி மேலும் படிக்கலாம் இங்கே மற்றும் இங்கே .

அதிகம் அறியப்படாத ankerl நூலகம் ( கிதுப் ) பெரும்பாலான காட்சிகளில் மிகவும் திறமையானது எனக் கூறுகிறது. இந்த நூலகத்தின் ஆசிரியர் பல ஹாஷ் வரைபடங்களுக்கு வெவ்வேறு பயன்பாட்டு நிகழ்வுகளில் ( வலைப்பதிவு இடுகை ) விரிவான பெஞ்ச்மார்க் முடிவுகளை வழங்குகிறது. இந்த முடிவுகளை நீங்கள் பின்பற்றலாம், ஆனால் அவற்றை உப்பு தானியத்துடன் எடுத்துக் கொள்ளுங்கள். தயாரிப்பு சூழலில் நீங்கள் தேர்ந்தெடுக்கும் ஹாஷ் வரைபடத்தை எப்போதும் சோதிக்கவும். பெஞ்ச்மார்க்குகள் எப்பொழுதும் செயற்கையானவை மற்றும் CPU மற்றும் நினைவகம் ஹாஷ் வரைபட செயல்பாடுகளைத் தவிர மற்ற வேலைகளைச் செய்யும்போது நிகழ்வுகளை உள்ளடக்காது. ஹாஷ் மேப் நினைவகத்தின் பல்வேறு பகுதிகள் CPU தற்காலிக சேமிப்பில் இல்லாதபோதும், இது உண்மையான நிரல்களில் அடிக்கடி நிகழும் நிகழ்வுகளையும் வரையறைகள் உள்ளடக்காது.

ஹாஷ் செயல்பாடு தரம்

லுக்-அப் செயல்பாடுகளின் நேர சிக்கலைத் தக்கவைக்க ஹாஷ் செயல்பாட்டின் தரம் முக்கியமானது O(1) . பிளாட் ஹாஷ் வரைபடங்கள் ஹாஷ் செயல்பாட்டின் தரத்திற்கு குறிப்பாக உணர்திறன் கொண்டவை. ஒரு சிறந்த ஹாஷ் செயல்பாட்டை இப்படி வரையறுக்கலாம்: விசையில் ஒரு பிட் மாறினால், அதனுடன் தொடர்புடைய ஹாஷ் மதிப்பு அதன் பிட்களில் பாதியை தோராயமாக மாற்றும். இத்தகைய ஹாஷ் செயல்பாடு பனிச்சரிவு என்று அழைக்கப்படுகிறது.

துரதிர்ஷ்டவசமாக, முழு எண் மற்றும் சுட்டி ஹாஷ் செயல்பாடுகளின் சில C++ நிலையான நூலக செயலாக்கங்கள் பனிச்சரிவு அல்ல. எடுத்துக்காட்டாக, libstdc++ கூடுதல் மாற்றங்கள் இல்லாமல் நேரடியாக சுட்டிக்காட்டி அல்லது முழு எண் மதிப்பை வழங்குகிறது: github .

boost மற்றும் F14 செயலாக்கங்கள் போன்ற மேம்பட்ட ஹாஷ் அட்டவணைகள், hash_is_avalanching பண்பை அறிமுகப்படுத்துவதன் மூலம் இந்தச் சிக்கலைச் சமாளிக்கின்றன. ஹாஷ் செயல்பாடு தன்னை பனிச்சரிவு என குறிப்பிடவில்லை என்றால், ஹாஷ் டேபிள் ஹாஷ் தரத்தை மேம்படுத்த கூடுதல் கலவை படியை செய்யும். இது கூடுதல் செலவில் வருகிறது. நீங்கள் ஒரு தனிப்பயன் ஹாஷ் செயல்பாட்டைச் செயல்படுத்தினால், அது ஒழுக்கமான தரம் வாய்ந்தது என்று உங்களுக்குத் தெரிந்தால், இந்த எடுத்துக்காட்டில் காட்டப்பட்டுள்ளபடி அதை பனிச்சரிவு எனக் குறிக்கலாம். பூஸ்ட் is_avalanching சொத்துப் பெயரைப் பயன்படுத்துகிறது, மேலும் F14 பண்பு folly_is_avalanching என்று பெயரிடப்பட்டது. வெறுமனே, நீங்கள் இரண்டையும் சேர்க்க வேண்டும்.

பெட்டிக்கு வெளியே ஆதரிக்கப்படும் முக்கிய வகைகளையும் (எ.கா. string , int , சுட்டிகள்) மற்றும் boost அல்லது F14 வழங்கும் இயல்புநிலை ஹாஷ் செயல்பாடுகளை நீங்கள் பயன்படுத்தினால், அவை ஏற்கனவே தேவைக்கேற்ப சரியாகக் குறிக்கப்படும், மேலும் இதைப் பற்றி நீங்கள் சிந்திக்கத் தேவையில்லை. தனிப்பயன் விசை வகையைச் செயல்படுத்த நீங்கள் முடிவு செய்கிறீர்கள், இதற்கு தனிப்பயன் ஹாஷ் செயல்பாடு தேவைப்படும்.

நூல் பாதுகாப்பு

மேலே உள்ள அனைத்து கொள்கலன்களும் பொதுவாக நூல்-பாதுகாப்பானவை அல்ல, மேலும் ஒரு நூல் மற்றொரு நூல் அணுகும்போது ஹாஷ் வரைபடத்தை மாற்றினால், வெளிப்புற ஒத்திசைவை (உதாரணமாக, மியூடெக்ஸ்களைப் பயன்படுத்தி) செயல்படுத்த வேண்டும்.

எல்லா நூல்களும் வரைபடத்தை மட்டுமே படித்தால், ஒத்திசைவு தேவையில்லை. const என்று குறிக்கப்பட்ட முறைகளை மட்டுமே அழைக்கிறீர்கள் என்பதை உறுதிப்படுத்தவும். அனைத்து const முறைகளும் கொள்கலனை மாற்றலாம். operator[] const அல்ல, கொள்கலனை மாற்றும் என்பதை நினைவில் கொள்ளவும். மல்டித்ரெட் குறியீட்டில் உள்ள பொதுவான ஆபத்து:

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

மேலே உள்ள குறியீட்டில், key தொடர்புடைய மதிப்பு true என்பதைச் சரிபார்ப்பதே இலக்காகும். இருப்பினும், map["key"] இன்னும் map இல்லை எனில் key சேர்க்கும் . புதிதாக சேர்க்கப்பட்ட மதிப்பு இயல்புநிலையாக அமைக்கப்படும் (மேலே உள்ள எடுத்துக்காட்டில் 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::concurrent_flat_set மற்றும் boost::concurrent_flat_map Boost.Unordered நூலகத்தில் இருந்து. பூஸ்ட் கொள்கலன்கள் வருகை அடிப்படையிலான API ஐ வழங்குகின்றன, இது C++ தரநிலை நூலகத்தால் வழங்கப்படும் API இலிருந்து மிகவும் வேறுபட்டது.
• மற்றொரு விருப்பம் folly::ConcurrentHashMap ( github ). ஃபோலி அதன் API ஐ C++ நிலையான வரிசைப்படுத்தப்படாத கொள்கலன்களுக்கு முடிந்தவரை நெருக்கமாக வைத்திருக்க முயற்சிக்கிறது.
• libcds என்பது லாக்-ஃப்ரீ ஹாஷ் வரைபடங்களின் (எ.கா. MichaelHashMap , SkipListMap , SkipListSet , FeldmanHashMap , FeldmanHashSet ) பல செயலாக்கங்களை வழங்கும் ஒரு பெரிய பூட்டு இல்லாத கொள்கலன் நூலகம் ஆகும். இந்த நூலகம் சிறிது காலத்திற்குள் புதுப்பிக்கப்படவில்லை மற்றும் விரிவான ஆவணங்களை வழங்கவில்லை, ஆனால் இது வழங்கும் கன்டெய்னர்கள் தனித்துவமானது என்பதால் நான் இன்னும் அதைப் பகிர்கிறேன். உங்கள் பயன்பாட்டு வழக்கு ஹாஷ் வரைபடத்தில் அதிக சர்ச்சையைக் குறிக்கிறது என்றால், libcds வழங்கும் இந்த லாக்-ஃப்ரீ அகராதிகளை முயற்சிக்கவும்.
• செயல்திறன் கவலை இல்லை என்றால், மியூடெக்ஸ்களைப் பயன்படுத்தி த்ரெட்-பாதுகாப்பான வரைபடங்களுக்கான அணுகல்களை நீங்கள் ஒத்திசைக்கலாம். மாற்றாக, நீங்கள் ஒரே நேரத்தில் அணுகல்களை முற்றிலும் தவிர்க்கலாம், இது நூல்-பாதுகாப்பான கொள்கலன்களைப் பயன்படுத்துவதை விட அல்லது ஒத்திசைவைச் சேர்ப்பதைக் காட்டிலும் மிகவும் திறமையானது.

நான் எதைப் பயன்படுத்துவது?

மிகவும் பொருத்தமான கொள்கலனை எவ்வாறு தேர்வு செய்வது என்பதை விளக்கும் சுருக்கமான புள்ளிகளைப் பார்ப்போம்.

• மதிப்புடன் விசையை இணைக்க வேண்டும் என்றால், ஒரு வரைபடத்தைத் தேர்ந்தெடுக்கவும், இல்லையெனில், ஒரு தொகுப்பைப் பயன்படுத்தவும்.
• வரைபடத்தில் நகல் விசைகளை வைத்திருப்பது அவசியமானால், பல கொள்கலன்களைப் பயன்படுத்தவும்.
• உங்களுக்கு கடுமையான சாத்தியமுள்ள மறு செய்கை மற்றும் குறிப்பு நிலைப்புத்தன்மை உத்தரவாதங்கள் தேவைப்பட்டால், 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 ஆனது ஹாஷிங் செலவைச் சேமிக்கும்.
• மேலே உள்ள அனைத்து புள்ளிகளும் ஒற்றை-திரிக்கப்பட்ட கொள்கலன் பயன்பாட்டிற்கு பொருந்தும் (அல்லது ஒரே நேரத்தில் மாற்றங்கள் இல்லாமல் பல-திரிக்கப்பட்ட வாசிப்பு அணுகல்). பல-திரிக்கப்பட்ட மாற்றங்கள் தேவைப்பட்டால், மேலே பட்டியலிடப்பட்டுள்ள நூல்-பாதுகாப்பான விருப்பங்களில் ஒன்றைத் தேர்ந்தெடுக்கவும். அவை உண்மையான உற்பத்திக் குறியீட்டில் மாறுபட்ட செயல்திறனைக் காட்டலாம், எனவே அவற்றை உங்கள் பயன்பாட்டில் சோதித்து முடிவுகளை ஒப்பிட்டுப் பார்க்கவும்.