एक हैशटेबल के माध्यम से पुनरावृत्त कैसे किया जा रहा है?

Question

मैं समझने की कोशिश कर रहा हूं कि एक हैशटेबल के माध्यम से पुनरावृत्ति कैसे किया जा रहा है। मैं बस कल्पना नहीं कर सकता। मैं विशेष रूप से इस तरह के पुनरावृत्ति की गति में रूचि रखता हूं। उदाहरण के लिए:

QHash<int, std::string> hashTable; 
... 
for (auto it = hashTable.begin(); it != hashTable.end(); ++it) 
    std::cout << it.value() << std::endl; 

यह एक O(hashTable.size()) आपरेशन है?

मैंने स्रोत कोड में खोदने की कोशिश की, लेकिन उचित परिभाषा नहीं मिली।

Answer 1

हैश टेबल के कुछ कार्यान्वयन भी तेजी से पुनरावृत्ति (एक तथाकथित "लिंक हैश-मैप") की अनुमति देने के लिए सभी प्रविष्टियों की एक लिंक सूची बनाए रखता है।

जब वे नहीं करते हैं, तो हैश टेबल की सभी बाल्टीओं पर फिर से चलने का एकमात्र तरीका है, जबकि प्रत्येक बाल्टी में तत्वों पर भी पुनरावृत्ति होती है।

इस ऑपरेशन की गति तालिका की भर स्थिति पर निर्भर करती है। जब यह बहुत कम होता है, तो बहुत सी खाली बाल्टी को फिर से चालू करने की आवश्यकता होती है, जो समय बर्बाद कर देती है। जब तालिका अच्छी तरह से भर जाती है, और प्रत्येक बाल्टी में एक या अधिक तत्व होते हैं, तो यह लगभग एक लिंक्ड सूची को पुन: स्थापित करने जैसा होता है। एक परिपूर्ण हैश मानचित्र पर जहां प्रत्येक बाल्टी में बिल्कुल एक तत्व होता है, यह एक सरणी को पुनरावर्तित करने जैसा है।