हैशटेबल और डिक्शनरी से संबंधित साक्षात्कार प्रश्न

Question

मुझे हाल ही में हैशटेबल्स के बारे में कुछ साक्षात्कारों में ड्रिल किया गया है और जब यह GetHashCode() को ओवरराइड करने में सक्षम है। जब तक मैंने तौलिया में फेंक दिया, तब तक चर्चा गहरी और गहरी हो रही थी।

अब मैं अगली बार तैयार होने के लिए सब कुछ कवर करने के लिए कुछ शोध कर रहा हूं।

मैं पाया है इस उत्कृष्ट लेख है कि मैं चाहते हैं साझा करने के लिए: http://msdn.microsoft.com/en-us/library/ms379571(VS.80).aspx#datastructures20_2_topic5

1) कुछ मैं के साथ बहुत सहज महसूस नहीं करते तथ्य यह है कि शब्दकोश हैश आधारित हैं, लेकिन जाहिरा तौर पर सूचियाँ नहीं हैं । क्या इसका मतलब यह है कि सूची <> और ऐरे [] में खोज करना रैखिक है, जबकि एक शब्दकोश या हैशटेबल में खोज करते समय निरंतर और इसलिए बहुत तेज़ है? क्या यह सब कुछ है?

2) यदि मैं किसी शब्दकोश में एक कुंजी के रूप में कक्षा का उपयोग करता हूं, तो मुझे किसी भी आवश्यक पहचान फ़ील्ड के आधार पर उस वर्ग पर GetHashcode() को ओवरराइड करने की आवश्यकता होती है ताकि उदाहरण अद्वितीय हो सकें। हालांकि यह अभी भी हो सकता है कि दोनों आईडी फ़ील्ड बराबर हैं और एक ही हैशकोड उत्पन्न होगा? यदि ऐसा ही होता है तो उसी हैशकोड के साथ दो उदाहरणों की टक्कर के दौरान क्या होता है?

3) टकराव कैसे हल किया जा सकता है? मैंने शब्दकोश के लिए हैशटेबल और चेनिंग के लिए टकराव के मामले में रीहैशिंग पद्धति के बारे में लेख में पढ़ा है। लेकिन मुझे अभी भी यकीन नहीं है कि यह वास्तव में कैसे काम करता है क्योंकि मैं गणित प्रतिभा नहीं हूं। : - \ क्या कोई इसे बेहतर समझा सकता है कि यह कैसे काम करता है?

कई धन्यवाद, Kave

Answer 1

1) सामान्यतः, हाँ, Dictionary<T> या HashSet<T> में निरंतर समय पहुंच है। एक अनसुलझा List<T> में किसी आइटम को ढूंढना या ऐरे को रैखिक रूप से किया जाना चाहिए। सॉर्ट किए गए संग्रह आपको ओ (लॉग एन) एक्सेस समय देने, बाइनरी खोज करने देते हैं।

2) यदि आप .NET में GetHashCode ओवरराइड करते हैं, तो आपको Equals विधि को ओवरराइड करना चाहिए। .NET Dictionary और HashSet में, आप समान वस्तुओं को सम्मिलित नहीं कर सकते हैं। हैश टकराव सामान्य मामले में अपरिहार्य हैं (जब तक कि आपने एक परिपूर्ण हैश गणना नहीं की हो)। टकराव को हल करने के कई तरीके हैं।

3) टकराव समाधान के बारे में अधिक जानकारी के लिए, http://en.wikipedia.org/wiki/Hash_table देखें।

Answer 2

एक हैश तालिका एक डेटा संरचना है। अधिक जानकारी when looking for more general information मिल सकती है।

1) सूचियों में एक डिफ़ॉल्ट खोज रैखिक हैं (सभी तत्वों को पार करने की आवश्यकता है)। बिल्कुल सही हैशिंग (कोई टक्कर नहीं) सबसे खराब मामले में निरंतर समय लुकअप की अनुमति देता है। अधिक टकराव का परिणाम धीमे लुकअप में होता है।

2) संभावित कुंजी के बड़े सेट के यादृच्छिक सबसेट को हश करते समय हैश टकराव व्यावहारिक रूप से अपरिहार्य हैं। इसलिए, अधिकांश हैश टेबल कार्यान्वयन में ऐसी घटनाओं को संभालने के लिए कुछ टकराव समाधान रणनीति है। .NET के हैशटेबल कार्यान्वयन का उपयोग double hashing का उपयोग करना प्रतीत होता है।

3) यह ऐसा कुछ है जिसके बारे में आपको चिंता नहीं करना चाहिए, जब तक आप उचित हैश कोड प्रदान करते हैं। रुचि रखते समय, हैश टेबल के बारे में विकी आलेख पढ़ें, जो कई तकनीकों को बताता है।

अद्यतन: टक्कर हैंडलिंग में हैशटेबल और शब्दकोश के कार्यान्वयन में a difference है। स्पष्ट रूप से हैशटेबल अप्रचलित है और Dictionary या HashSet को प्राथमिकता दी गई है।

जिम मिशेल का उल्लेख है, तो आपको GetHashCode के साथ-साथ बराबर होना चाहिए। समान वस्तुओं को सम्मिलित करना संभव नहीं है, लेकिन उसी हैशकोड वाले आइटम आपके द्वारा चुने गए संग्रह प्रकार द्वारा प्रबंधित किए जाते हैं।