हैश मैप जटिलता प्राप्त करें/डाल दें

Question

हम कह रहे हैं कि HashMapget/put संचालन ओ (1) हैं। हालांकि यह हैश कार्यान्वयन पर निर्भर करता है। डिफ़ॉल्ट ऑब्जेक्ट हैश वास्तव में JVM ढेर में आंतरिक पता है। क्या हमें यकीन है कि यह दावा करने के लिए पर्याप्त है कि get/put ओ (1) हैं?

उपलब्ध स्मृति एक और मुद्दा है। जैसा कि मैं javadocs से समझता हूं, HashMapload factor 0.75 होना चाहिए। क्या होगा यदि हमारे पास JVM में पर्याप्त स्मृति नहीं है और load factor सीमा से अधिक है?

तो ऐसा लगता है कि ओ (1) की गारंटी नहीं है। क्या यह समझ में आता है या क्या मुझे कुछ याद आ रहा है?

Answer 1

यह कई चीजों पर निर्भर करता है। यह आमतौर पर ओ (1) है, जो एक सभ्य हैश है जो स्वयं स्थिर समय है ... लेकिन आपके पास हैश हो सकता है जो गणना करने के लिए लंबा समय लेता है, और यदि हैश मानचित्र में कई आइटम हैं जो वापस लौटाते हैं एक ही हैश कोड, get उन पर से प्रत्येक पर एक मैच खोजने के लिए equals पर कॉल करना होगा।

सबसे बुरे मामले में, HashMap में एक ही हैश बाल्टी में सभी प्रविष्टियों के माध्यम से चलने के कारण ओ (एन) लुकअप है (उदाहरण के लिए यदि उनके पास एक ही हैश कोड है)। सौभाग्य से, मेरे अनुभव में, वास्तविक जीवन में सबसे खराब मामला परिदृश्य अक्सर नहीं आता है। तो नहीं, ओ (1) निश्चित रूप से गारंटी नहीं है - लेकिन यह आमतौर पर आपको क्या लगता है जब एल्गोरिदम और डेटा संरचनाओं का उपयोग करने पर विचार करना चाहिए।

जेडीके 8, HashMap में tweaked किया गया है ताकि अगर चाबियों की ऑर्डर करने के लिए तुलना की जा सके, तो किसी भी घनी आबादी वाली बाल्टी को पेड़ के रूप में लागू किया जाता है, ताकि अगर एक ही हैश कोड के साथ बहुत सारी प्रविष्टियां हों, जटिलता ओ है (लॉग एन)। इससे समस्याएं पैदा हो सकती हैं यदि आपके पास एक महत्वपूर्ण प्रकार है जहां समानता और ऑर्डरिंग अलग-अलग हैं।

और हाँ, यदि आपके पास हैश मानचित्र के लिए पर्याप्त स्मृति नहीं है, तो आप परेशानी में होंगे ... लेकिन यह आपके द्वारा उपयोग की जाने वाली डेटा संरचना के सत्य होने जा रहा है।

Answer 2

मुझे यकीन नहीं है कि डिफ़ॉल्ट हैशकोड पता है - मैंने कुछ समय पहले हैशकोड पीढ़ी के लिए ओपनजेडीके स्रोत पढ़ा है, और मुझे याद है कि यह कुछ और जटिल है। अभी भी कुछ ऐसा नहीं है जो एक अच्छा वितरण की गारंटी देता है, शायद। हालांकि, यह कुछ हद तक मूक है, क्योंकि कुछ वर्ग जो आप हैशैप में कुंजी के रूप में उपयोग करते हैं, डिफ़ॉल्ट हैशकोड का उपयोग करते हैं - वे अपने स्वयं के कार्यान्वयन की आपूर्ति करते हैं, जो कि अच्छा होना चाहिए।

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

अंत में, तालिका ओवरलोड होने पर क्या होता है यह है कि यह समानांतर लिंक्ड सूचियों के सेट में गिरावट करता है - प्रदर्शन ओ (एन) बन जाता है। विशेष रूप से, ट्रांस्ड किए गए लिंक की संख्या औसतन भार कारक होगी।

Answer 3

यह पहले से ही उल्लेख किया गया है कि हैशैप्स O(n/m) औसत में हैं, यदि n आइटम की संख्या और m आकार है। यह भी उल्लेख किया गया है कि सिद्धांत रूप में पूरी चीज O(n) क्वेरी समय के साथ एक एकल लिंक्ड सूची में गिर सकती है। (यह सब मानते हैं कि हैश की गणना निरंतर समय है)।

हालांकि अक्सर उल्लेख नहीं किया जाता है कि कम से कम 1-1/n (इसलिए 1000 आइटम जो 99.9% मौका है) के लिए सबसे बड़ी बाल्टी O(logn) से अधिक नहीं भरी जाएगी! इसलिए बाइनरी खोज पेड़ की औसत जटिलता से मेल खाते हैं। (और निरंतर अच्छा है, एक कठोर बाध्य (log n)*(m/n) + O(1) है)।

सभी है कि इस सैद्धांतिक बाध्य लिए आवश्यक है कि आप एक उचित रूप से अच्छी हैश समारोह का उपयोग करें (विकिपीडिया देखें:। Universal Hashing यह a*x>>m के रूप में सरल किया जा सकता है)। और निश्चित रूप से वह व्यक्ति जो हैश को मान देता है, यह नहीं जानता कि आपने अपने यादृच्छिक स्थिरांक को कैसे चुना है।

टीएल; डीआर: बहुत अधिक संभावना के साथ सबसे खराब मामला हैशपैप की जटिलता/O(logn) है।

Answer 4

HashMap आपरेशन hashCode कार्यान्वयन की निर्भर कारक है। आदर्श परिदृश्य के लिए अच्छा हैश कार्यान्वयन कहता है जो प्रत्येक वस्तु (कोई हैश टकराव) के लिए अद्वितीय हैश कोड प्रदान करता है, तो सबसे अच्छा, सबसे खराब और औसत केस परिदृश्य ओ (1) होगा। चलो एक ऐसे परिदृश्य पर विचार करें जहां हैशकोड का खराब कार्यान्वयन हमेशा 1 या ऐसे हैश को लौटाता है जिसमें हैश टक्कर है। इस मामले में समय जटिलता ओ (एन) होगी।

अब स्मृति के बारे में प्रश्न के दूसरे भाग के लिए आ रहा है, तो हाँ स्मृति बाधा देखभाल JVM द्वारा लिया जाएगा।