शब्दकोश में हैशिंग की प्रक्रिया कैसे काम करती है <TKey, TValue>

Question

शब्दकोश में हैशिंग की प्रक्रिया कैसे काम करती है? मैंने पढ़ा है कि शब्दकोश का उपयोग तेजी से देखो प्रदान करता है। लेकिन समझ में नहीं आया कैसे? इंडेक्स में हैशिंग और मैपिंग कैसे होती है? कोई अच्छा संदर्भ नहीं मिला।

संपादित करें: हैशिंग फ़ंक्शन के परिणाम से ऑब्जेक्ट संग्रहीत वास्तविक स्मृति स्थान कैसा है?

Answer 1

एक शब्दकोश में हैशिंग प्रक्रिया एक तकनीक का उपयोग करती है जिसे चेनिंग के रूप में प्रस्तुत किया जाता है। चेनिंग के साथ, किसी भी टकराव को पकड़ने के लिए एक माध्यमिक डेटा संरचना का उपयोग किया जाता है। विशेष रूप से, शब्दकोश में प्रत्येक स्लॉट में तत्वों की एक सरणी होती है जो बाल्टी को मैप करती है। टकराव की स्थिति में, टकराव तत्व बाल्टी की सूची में तैयार किया जाता है।

अधिक जानकारी के लिए एमएसडीएन पर this आलेख देखें।

Answer 2

एक कंप्यूटर विज्ञान अवधारणा का उपयोग करके Hash Map कहा जाता है। यह सूची खोजने से तेज़ी से काम करता है। यह एक सूची के माध्यम से खोज को फिर से शुरू करने की आवश्यकता से खोज को बनाए रखकर काम करता है जब तक कि यह एक मैच न मिल जाए। इसके बजाय कुंजी "hashed" है, और एक सूची में एक सूचकांक के रूप में उपयोग किया जाता है। यह हैशिंग फ़ंक्शन सूची खोजने से तुलना में लगभग हमेशा तेज होता है (एकाधिक तुलनाओं के साथ पुनरावृत्ति)।

Answer 3

आमतौर पर, हैश मान% सरणी आकार ले कर, जो टकराव उत्पन्न कर सकता है।

Answer 4

शब्दकोश लुकअप के लिए हैश कुंजी का उपयोग करता है क्योंकि मैंने my answer to your other question में व्याख्या करने की कोशिश की थी। तो यदि आपके पास कस्टम ऑब्जेक्ट प्रकार है क्योंकि कुंजी सब कुछ आपके कस्टम ऑब्जेक्ट के GetHashKey() कार्यान्वयन पर निर्भर करता है।

Answer 5

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

हैश तालिका में एक कुंजी-मूल्य जोड़ी डालने के लिए आपको पहले कुंजी के हैश कोड की गणना करनी होगी। .NET में सभी ऑब्जेक्ट्स में GetHashCode नामक एक विधि है जो उस विशेष ऑब्जेक्ट के लिए हैश कोड (32 बिट पूर्णांक) देता है। यह महत्वपूर्ण है कि समान वस्तुएं एक ही हैश कोड लौटाएं, लेकिन यदि विभिन्न ऑब्जेक्ट्स अलग हैश कोड लौटाते हैं तो भी बहुत उपयोगी होते हैं। गलत धारणा से सावधान रहें कि विभिन्न वस्तुएं एक ही हैश कोड वापस नहीं कर सकती हैं - वे कर सकते हैं, लेकिन इसके परिणामस्वरूप टकराव (नीचे देखें) होगा।

एक उदाहरण के रूप में दो तार के हैश कोड पर विचार करें:

 
"Boo" 0x598FD95A 
"Foo" 0x598FD8DE 

हालांकि तार बहुत समान वे विभिन्न हैश कोड होता है।

मैं हैश टेबल के महत्वपूर्ण पहलुओं पर ध्यान केंद्रित करने के लिए चीजों को सरल बना रहा हूं, इसलिए अब हम कहें कि आंतरिक Dictionary<TKey, TValue> एक सरणी में कुंजी-मूल्य जोड़े संग्रहीत करता है। इस सरणी में इंडेक्स का पता लगाने के लिए जहां कुंजी-मूल्य जोड़ी संग्रहीत की जाएगी, आपको सर मॉड्यूलो के सर मॉड्यूल के हैश कोड की गणना करना होगा।मान लें सरणी के आकार 5:

 
Index("Boo") = 0x598FD95A % 5 = 4 
Index("Foo") = 0x598FD8DE % 5 = 0 

यह इस आंतरिक हैश तालिका सरणी की ओर जाता है:

 
+---+---------+ 
| 0 | "Foo" | 
+---+---------+ 
| 1 | (empty) | 
+---+---------+ 
| 2 | (empty) | 
+---+---------+ 
| 3 | (empty) | 
+---+---------+ 
| 4 | "Boo" | 
+---+---------+ 

हैश तालिका में एक प्रविष्टि अवलोकन किया जा रहा बहुत तेजी से है। आपको केवल आंतरिक सरणी के आकार के मुख्य मॉड्यूल के हैश कोड की गणना करना होगा और उस अनुक्रमणिका में स्ट्रिंग को पुनर्प्राप्त करना होगा।

अब विचार करें कुंजी "चिड़ियाघर":

 
Index("Zoo") = 0x598FDC62 % 5 = 0 

यह कुंजी "बू" के समान सूची है। इसके परिणामस्वरूप टकराव कहा जाता है। हैश टेबल के उचित कार्यान्वयन को टकरावों को संभालना होगा और different strategies for doing that हैं। साथ ही, जैसा कि आंतरिक सरणी भर जाती है, वहां सरणी में कम और कम खाली तत्व होंगे जिसके परिणामस्वरूप टक्कर बढ़ती जा रही है। लोड फैक्टर आंतरिक तत्वों में प्रयुक्त तत्वों और कुल तत्वों के बीच अनुपात है। ऊपर दिए गए उदाहरण में लोड कारक 2/5 = 0.4 है। अधिकांश हैश टेबल कार्यान्वयन आंतरिक सरणी के आकार को बढ़ाएंगे जब लोड फैक्टर एक निश्चित दहलीज से अधिक हो जाता है।

यदि आप इनमें से कुछ अवधारणाओं के बारे में अधिक जानना चाहते हैं तो आपको अन्य उत्तरों में जुड़े कुछ अधिक व्यापक संसाधनों का अध्ययन करना होगा।