क्या unordered_map वास्तव में unordered है?

Question

मैं 'unordered_map' नाम से बहुत उलझन में हूं। नाम से पता चलता है कि चाबियाँ बिल्कुल ऑर्डर नहीं की जाती हैं। लेकिन मैंने हमेशा सोचा कि उन्हें उनके हैश मूल्य द्वारा आदेश दिया गया है। या यह गलत है (क्योंकि नाम का तात्पर्य है कि उन्हें आदेश नहीं दिया गया है)?

या यह अलग डाल करने के लिए: इस

typedef map<K, V, HashComp<K> > HashMap; 

template<typename T> 
struct HashComp { 
    bool operator<(const T& v1, const T& v2) const { 
     return hash<T>()(v1) < hash<T>()(v2); 
    } 
}; 

ही साथ

typedef unordered_map<K, V> HashMap; 

रूप

है? (ठीक है, नहीं बिल्कुल, एसटीएल यहां शिकायत के कारण उसकी कुंजी k1, k2 और न k1 < k2 और न ही k2 < k1 हो सकता है आप multimap का उपयोग करें और ऊपर लिख बराबर की जांच करने की आवश्यकता होगी।।)

या फिर अलग ढंग से: जब मैं उनके माध्यम से पुनरावृत्ति करता हूं, तो क्या मैं मान सकता हूं कि कुंजी-सूची उनके हैश मान द्वारा आदेशित है?

Answer 1

आपके संपादित प्रश्न के उत्तर में, उन दो स्निपेट बिल्कुल समान नहीं हैं। std::map एक वृक्ष संरचना में नोड्स स्टोर करता है, unordered_map उन्हें एक हैशटेबल * में संग्रहीत करता है।

कुंजी उनके "हैश मान" के क्रम में संग्रहीत नहीं हैं क्योंकि वे में पर किसी ऑर्डर में संग्रहीत नहीं हैं। उन्हें बदले में "बाल्टी" में रखा जाता है जहां प्रत्येक बाल्टी हैश मानों की एक श्रृंखला से मेल खाती है। असल में, कार्यान्वयन इस प्रकार है:

function add_value(object key, object value) { 
    int hash = key.getHash(); 

    int bucket_index = hash % NUM_BUCKETS; 
    if (buckets[bucket_index] == null) { 
     buckets[bucket_index] = new linked_list(); 
    } 
    buckets[bucket_index].add(new key_value(key, value)); 
} 

function get_value(object key) { 
    int hash = key.getHash(); 

    int bucket_index = hash % NUM_BUCKETS; 
    if (buckets[bucket_index] == null) { 
     return null; 
    } 

    foreach(key_value kv in buckets[bucket_index]) { 
     if (kv.key == key) { 
      return kv.value; 
     } 
    } 
} 

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

* तकनीकी तौर पर, std::map और unordered_map की आंतरिक कार्यान्वयन कार्यान्वयन से परिभाषित कर रहे हैं, लेकिन मानक है कि तात्पर्य उन आंतरिक कार्यान्वयन

Answer 2

यदि आप एक समानता चाहते हैं, तो अपनी पसंद के आरडीबीएमएस देखें।

यदि आप क्वेरी करते समय क्लॉज द्वारा ऑर्डर द्वारा निर्दिष्ट नहीं करते हैं, तो परिणाम "अनियंत्रित" लौटाए जाते हैं - यानी, डेटाबेस के जैसा भी आदेश लगता है। ऑर्डर निर्दिष्ट नहीं है, और सिस्टम उन्हें "ऑर्डर" करने के लिए स्वतंत्र है, हालांकि इसे सर्वश्रेष्ठ प्रदर्शन प्राप्त करने के लिए पसंद है।

Answer 3

आप सही हैं, unordered_map वास्तव में हैश आदेश दिया गया है। ध्यान दें कि अधिकांश मौजूदा कार्यान्वयन (पूर्व TR1) इसे hash_map कहते हैं।

आईबीएम C/C++ संकलक documentation टिप्पणी कि यदि आप एक इष्टतम हैश फंक्शन है, देखने, प्रविष्टि, और एक मनमाना तत्व को हटाने के दौरान प्रदर्शन किया आपरेशनों की संख्या तत्वों की संख्या पर अनुक्रम में निर्भर नहीं करता है , तो इसका मतलब यह है कि ऑर्डर इतना असामान्य नहीं है ...

अब, इसका क्या अर्थ है कि यह हैश ने का आदेश दिया है? जैसा कि हैश को अप्रत्याशित होना चाहिए, परिभाषा के अनुसार आप मानचित्र में तत्वों के क्रम के बारे में कोई धारणा नहीं ले सकते हैं। यही कारण है कि इसका नाम बदलकर टीआर 1 में किया गया: पुराने नाम ने एक आदेश का सुझाव दिया। अब हम जानते हैं कि एक आदेश वास्तव में उपयोग किया जाता है, लेकिन आप इसे अवहेलना कर सकते हैं क्योंकि यह अप्रत्याशित है।

Answer 4

"अनॉर्डर्ड" का मतलब यह नहीं है कि कार्यान्वयन में कहीं रैखिक अनुक्रम नहीं है। इसका मतलब है "आप इन तत्वों के आदेश के बारे में कुछ भी नहीं मान सकते हैं"।

उदाहरण के लिए, लोग अक्सर मानते हैं कि प्रविष्टियां उसी क्रम में हैश मैप से बाहर आ जाएंगी, लेकिन वे नहीं करते हैं, क्योंकि प्रविष्टियां अनियंत्रित होती हैं।

"उनके हैश मान द्वारा आदेशित" के लिए: हैश मान आम तौर पर पूर्णांक की पूरी श्रृंखला से लिया जाता है, लेकिन हैश मानचित्रों में 2 ** 32 स्लॉट नहीं होते हैं। हैश वैल्यू की रेंज स्लॉट्स की संख्या को मॉड्यूलो करके स्लॉट की संख्या में कम कर दी जाएगी। इसके अलावा, जब आप हैश मानचित्र में प्रविष्टियां जोड़ते हैं, तो यह नए मानों को समायोजित करने के लिए आकार बदल सकता है। इससे सभी पिछली प्रविष्टियों को फिर से रखा जा सकता है, जिससे उनका ऑर्डर बदल सकता है।

एक अनियंत्रित डेटा संरचना में, आप प्रविष्टियों के आदेश के बारे में कुछ भी नहीं मान सकते हैं।

Answer 5

नाम के रूप में unordered_map सुझाव देता है, सी ++ 0x मानक द्वारा कोई ऑर्डरिंग निर्दिष्ट नहीं है। एक unordered_map का स्पष्ट आदेश वास्तविक कार्यान्वयन के लिए जो कुछ भी सुविधाजनक है उस पर निर्भर करेगा।