क्या होता है जब हैश टकराव शब्दकोश कुंजी में होता है?

Question

मैं अपने जीवन की सी ++ और जावा पूरी तरह से कोडिंग कर रहा हूं लेकिन सी # पर, मुझे लगता है कि यह एक बिल्कुल अलग जानवर है।

सी # में शब्दकोश कंटेनर में हैश टकराव के मामले में, यह क्या करता है? या यह टकराव का पता भी लगाता है?

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

[अद्यतन 10:56 एएम। 6/4/2010]

मैं प्रति उपयोगकर्ता प्रति काउंटर बनाने की कोशिश कर रहा हूं। और सेट उपयोगकर्ता # परिभाषित नहीं है, यह दोनों वृद्धि या कमी कर सकते हैं।

• तेजी से पहुँच अधिमानतः हे नहीं (एन), यह महत्वपूर्ण है कि मैं हे (1) कारण के करीब है: और मैं डेटा का आकार 1000 से अधिक

  तो, मैं चाहता हूँ होने की उम्मीद कर रहा हूँ आवश्यकता के लिए, मुझे यह सुनिश्चित करने की ज़रूरत है कि मैं चुपचाप निष्पादित करने में सक्षम होने से पहले लोगों को लॉग इन कर सकता हूं।

• गतिशील वृद्धि और सिकुड़ना।
• अद्वितीय डेटा।

HashMap मेरी समाधान था, और ऐसा लगता है शब्दकोश क्या सी # में HashMap के समान है ...

Answer 1

हैश टकराव सही ढंग से Dictionary<> द्वारा नियंत्रित किया जाता है।

सबसे पहले, आपको Dictionary<> आंतरिक रूप से काम करने के बारे में कोई धारणा नहीं लेनी चाहिए - यह एक कार्यान्वयन विवरण है जो समय के साथ बदल सकता है। कहा करने के बाद

क्या आप पर विचार करना होगा प्रकार आप चाबी के लिए उपयोग कर रहे हैं सही ढंग से GetHashCode() और Equals() को लागू है कि क्या है कि ....। मूल नियम हैं कि GetHashCode() को ऑब्जेक्ट के जीवनकाल के लिए वही मान वापस करना होगा, और Equals() को दोबारा एक ही ऑब्जेक्ट का प्रतिनिधित्व करने पर सत्य वापस करना होगा। जब तक आप इसे ओवरराइड नहीं करते हैं, Equals() संदर्भ समानता का उपयोग करता है - जिसका अर्थ है कि यह केवल सत्य लौटाता है यदि दो ऑब्जेक्ट वास्तव में एक ही उदाहरण हैं। आप Equals() कामों को ओवरराइड कर सकते हैं, लेकिन फिर आपको यह सुनिश्चित करना होगा कि दो ऑब्जेक्ट्स 'बराबर' हैं, वही हैश कोड भी उत्पन्न करते हैं।

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

Answer 2

मेरा मानना ​​है कि यह अंतर्निहित सरणी का आकार बदलेंगे दो बार आकार तो फिर से हैश होने के लिए और अधिक संभावना होगा एक खुली बाल्टी प्राप्त करें।

Answer 3

this article at MSDN के अनुसार, हैश टकराव के मामले में Dictionary कक्षा बाल्टी को एक लिंक्ड सूची में परिवर्तित करती है। दूसरी ओर, पुराने HashTable वर्ग, रीहैशिंग का उपयोग करता है।

Answer 4

चेक एक अच्छा विवरण के लिए इस लिंक: An Extensive Examination of Data Structures Using C# 2.0

मूल रूप से, एक ही हैश मान के साथ .NET सामान्य शब्दकोश चेन आइटम नहीं है। इतने लंबे समय के लिए एक वस्तु को लागू करता है के रूप में GetHashCode() और Equals() सही ढंग से, उचित उदाहरण शब्दकोश से लौटाया नहीं जाएगा कि में -

Answer 5

मैं किसी वैकल्पिक कोड उन्मुख जवाब दर्शाता है कि एक शब्दकोश अपवाद मुक्त और कार्यात्मक रूप से सही व्यवहार का प्रदर्शन करती है जब विभिन्न कुंजी के साथ दो आइटम जोड़ रहे हैं लेकिन चाबियाँ एक ही hashCode उत्पादन प्रदान करते हैं।

नेट 4.6 तार "699,391" और "1,241,308" पर एक ही hashCode का उत्पादन। निम्नलिखित कोड में क्या होता है?

myDictionary.Add("699391", "abc"); 
myDictionary.Add("1241308", "def"); 

निम्नलिखित कोड दर्शाता है कि एक .Net शब्दकोश विभिन्न कुंजी स्वीकार करता है जो हैश टकराव का कारण बनता है। कोई अपवाद फेंक दिया गया है और शब्दकोश कुंजी लुकअप अपेक्षित ऑब्जेक्ट देता है।

var hashes = new Dictionary<int, string>(); 
var collisions = new List<string>(); 

for (int i = 0; ; ++i) 
{ 
    string st = i.ToString(); 
    int hash = st.GetHashCode(); 

    if (hashes.TryGetValue(hash, out string collision)) 
    { 
     // On .Net 4.6 we find "699391" and "1241308". 
     collisions.Add(collision); 
     collisions.Add(st); 
     break; 
    } 
    else 
     hashes.Add(hash, st); 
} 
Debug.Assert(collisions[0] != collisions[1], "Check we have produced two different strings"); 
Debug.Assert(collisions[0].GetHashCode() == collisions[1].GetHashCode(), "Prove we have different strings producing the same hashcode"); 

var newDictionary = new Dictionary<string, string>(); 
newDictionary.Add(collisions[0], "abc"); 
newDictionary.Add(collisions[1], "def"); 

Console.Write("If we get here without an exception being thrown, it demonstrates a dictionary accepts multiple items with different keys that produce the same hash value."); 

Debug.Assert(newDictionary[collisions[0]] == "abc"); 
Debug.Assert(newDictionary[collisions[1]] == "def");