हैशसेट पर पुनरावृत्ति लागत क्या बैकिंग मानचित्र की क्षमता पर निर्भर करती है?

Question

HashSet की Javadocs से:

इस वर्ग मानते हुए हैश फंक्शन बाल्टी के बीच तत्व पूरी तरह disperses, बुनियादी आपरेशन (जोड़ने, हटाने, शामिल है और आकार) के लिए निरंतर समय प्रदर्शन प्रदान करता है। इस सेट पर इटरेटिंग के लिए हैशसेट उदाहरण के आकार (तत्वों की संख्या) के साथ-साथ बैकिंग हैशैप उदाहरण (बाल्टी की संख्या) की "क्षमता" के योग के अनुपात के लिए आनुपातिक समय की आवश्यकता होती है। इस प्रकार, यह क्यों यात्रा सेट + क्षमता में (तत्वों की संख्या योग के लिए समय आनुपातिक लेता है बहुत अधिक आरंभिक क्षमता (या बहुत कम लोड फैक्टर) अगर यात्रा प्रदर्शन महत्वपूर्ण

है स्थापित करने के लिए नहीं बहुत महत्वपूर्ण है बैकिंग मैप का) और न केवल सेट में तत्वों की संख्या के लिए?

।

Answer 1

HashSetHashMap का उपयोग करके लागू किया गया है जहां तत्व मानचित्र कुंजी हैं। चूंकि किसी मानचित्र में बाल्टी की परिभाषित संख्या होती है जिसमें एक या अधिक तत्व हो सकते हैं, पुनरावृत्ति को प्रत्येक बाल्टी की जांच करने की आवश्यकता होती है, चाहे इसमें तत्व हों या नहीं।

Answer 2

लिंक्ड हैशसेट का उपयोग प्रविष्टियों की "लिंक" सूची का पालन करता है ताकि रिक्त स्थान की कोई फर्क नहीं पड़ता। आम तौर पर आपके पास हैशसेट नहीं होगा जहां क्षमता वास्तव में उपयोग किए जाने वाले आकार से दोगुनी से अधिक है। यहां तक ​​कि अगर आप ऐसा करेंगे, एक लाख प्रविष्टियों स्कैनिंग, ज्यादातर null ज्यादा समय (मिली-सेकंड) नहीं ले

Answer 3

क्यों यात्रा योग के लिए समय आनुपातिक लेता है (सेट + समर्थन मानचित्र की क्षमता में तत्वों की संख्या) और न केवल सेट में तत्वों के संख्या के लिए?

तत्वों अंतर्निहित HashMap जो एक सरणी के द्वारा समर्थित है अंदर फैले हुए हैं।
तो यह ज्ञात नहीं है कि कौन सी बाल्टी पर कब्जा कर लिया गया है (लेकिन यह ज्ञात है कि कितने तत्व पूरी तरह से उपलब्ध हैं)।
तो सभी तत्वों सभी बाल्टी

Answer 4

जाँच की जानी चाहिए, तो आपकी चिंता बार यह सेट के चारों ओर पुनरावृति के लिए लेता है अधिक पुनरावृति करने के लिए, और आप जावा 6 या अधिक से अधिक उपयोग कर रहे हैं इस सुंदरता पर एक नज़र डालें:

ConcurrentSkipListSet