शब्दकोश को आंतरिक रूप से कैसे बनाए रखा जाता है?

Question

जब मैं कहता हूँ

Dictionary<int,string> 

यह इस तरह के रूप में दो अलग अलग सरणियों के बराबर है:

int[] keys =new int[] { 1, 2, 3 }; 
string[] values=new string[]{"val1","val2","val3"}; 

Answer 1

यह बहुत दूर नहीं है। परावर्तक में स्रोत कोड को देखते हुए, ऐसा लगता है तीन आंतरिक संग्रह किया जाता है: वहाँ भी

private Entry<TKey, TValue>[] entries; 
private KeyCollection<TKey, TValue> keys; 
private ValueCollection<TKey, TValue> values; 

ध्यान दें कि एक int[] bucketsbuckets हैश कोड टकराव के मामले में आवश्यक का ट्रैक रखने के चर।

इन चर के उद्देश्यों को सभी स्पष्ट रूप से आत्म-व्याख्यात्मक होना चाहिए। यह विशेष रूप से आश्चर्यजनक नहीं है, वैसे भी, Dictionary वर्ग को ज्ञात और दस्तावेज (आदर्श रूप से, एक आइटम प्रति बाल्टी के साथ) O(1) लुकअप समय प्रदान करने के लिए जाना जाता है।

Answer 2

नहीं, यह एक हैश तालिका है। वैसे यह वास्तव में एक हैश तालिका नहीं है, लेकिन यह वास्तव में निकटता से संबंधित है।

http://en.wikipedia.org/wiki/Hash_table।

http://www.kirupa.com/net/dictionary_hashtable.htm

Answer 3

यह सब स्पष्ट रूप से MSDN पर लिखा है:

शब्दकोश (TKey, TValue के) सामान्य वर्ग मानों का एक सेट की चाबी का एक सेट से एक मानचित्रण प्रदान करता है। शब्दकोश के प्रत्येक जोड़े में एक मान और इसकी संबद्ध कुंजी होती है। इसकी कुंजी का उपयोग कर एक मूल्य प्राप्त करना बहुत तेज़ है, ओ (1) के करीब, क्योंकि शब्दकोश (टीकेई, टीवीएयू) वर्ग को हैश टेबल के रूप में लागू किया जाता है।

Answer 4

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

शब्दकोश (हैशटेबल) की एल्गोरिदमिक जटिलता ओ (1) है और सबसे खराब स्थिति ओ (लॉग (एन)) (सबसे खराब मामला मतलब है कि हम केवल टकराव के साथ सौदा करते हैं), जहां एन शब्दकोश में कई तत्व हैं।