जाओ: मानचित्र कुंजी के लिए पुनरावृत्ति आदेश निर्धारित करता है?

Question

Go Programming Language Specification का कहना है:

3. यात्रा के क्रम नक्शे से अधिक निर्दिष्ट नहीं है। [...]

यह उम्मीद की जा सकती है कि नक्शा प्रकार को हैश तालिका के रूप में लागू किया जा सकता है, या एक खोज पेड़ के रूप में, या कुछ अन्य डेटा संरचना के रूप में। लेकिन map वास्तव में गो में लागू किया गया है?

अलग ढंग से कहें तो क्या

for k, _ := range m { fmt.Println(k) } 

में चाबियों का यात्रा क्रम निर्धारित करता है मैं के बाद मैंने देखा कि string कुंजी के साथ एक नक्शे के जाहिरा तौर पर एक निश्चित यात्रा के क्रम है इस के बारे में सोच शुरू कर दिया। जैसे

package main 
import ("fmt"; "time"; "rand") 

func main() { 
    rand.Seed(time.Seconds()) 
    words := [...]string{"foo", "bar", "a", "b", "c", "hello", "world", 
     "0", "1", "10", "100", "123"} 
    stringMap := make(map[string]byte) 
    for i := range rand.Perm(len(words)) { 
     stringMap[words[i]] = byte(rand.Int()) 
    } 
    fmt.Print("stringMap keys:") 
    for k, _ := range stringMap { fmt.Print(" ", k) } 
    fmt.Println() 
} 

एक कार्यक्रम प्रिंट मेरी मशीन पर निम्न:

stringMap keys: a c b 100 hello foo bar 10 world 123 1 0 

परवाह किए बिना प्रविष्टि के आदेश की।

map[byte]byte मानचित्र के साथ समकक्ष प्रोग्राम भी एक शफल क्रम में कुंजी प्रिंट करता है, लेकिन यहां कुंजी आदेश सम्मिलन आदेश पर पर निर्भर करता है।

यह सब कैसे लागू किया गया है? map पूर्णांक और तारों के लिए विशिष्ट है?

Answer 1

मानचित्र को हैशप के रूप में गो में लागू किया गया है।

गो रन-टाइम एक सामान्य हैशप कार्यान्वयन का उपयोग करता है जिसे सी में लागू किया जाता है। map[string]T और map[byte]T के बीच केवल कार्यान्वयन अंतर हैं: हैश फ़ंक्शन, समकक्ष फ़ंक्शन और कॉपी फ़ंक्शन।

(कुछ) सी ++ मानचित्रों के विपरीत, गो मानचित्र पूर्णांक और तारों के लिए पूरी तरह से विशिष्ट नहीं हैं।

में रिलीज.आर 60, पुनरावृत्ति आदेश तब तक प्रविष्टि आदेश से स्वतंत्र है जब तक कि कोई महत्वपूर्ण टक्कर न हो। यदि टकराव हैं, तो पुनरावृत्ति आदेश सम्मिलन आदेश से प्रभावित होता है। कुंजी प्रकार के बावजूद यह सच है।इस संबंध में string प्रकार और byte प्रकार की कुंजी के बीच कोई अंतर नहीं है, इसलिए यह केवल एक संयोग है कि आपका प्रोग्राम हमेशा उसी क्रम में स्ट्रिंग कुंजी मुद्रित करता है। पुनरावृत्ति आदेश हमेशा तब तक समान होता है जब तक नक्शा संशोधित नहीं होता है।

हालांकि, नवीनतम में जाओ साप्ताहिक रिहाई (और में Go1 जो इस महीने जारी होने की उम्मीद की जा सकती है), यात्रा के क्रम बेतरतीबी से (यह एक छद्म अनियमित रूप से चुने कुंजी पर शुरू होता है, और hashCode गणना एक छद्म यादृच्छिक संख्या के साथ बीजित है)। यदि आप साप्ताहिक रिलीज (और गो 1 के साथ) के साथ अपने प्रोग्राम को संकलित करते हैं, तो हर बार जब आप अपना प्रोग्राम चलाते हैं तो पुनरावृत्ति आदेश अलग होगा। उस ने कहा, आपके प्रोग्राम को एक अनंत संख्या में चलाने से शायद कुंजी सेट के सभी संभावित क्रमपरिवर्तन मुद्रित नहीं होंगे। उदाहरण आउटपुट:

stringMap keys: b 0 hello c world 10 1 123 bar foo 100 a 
stringMap keys: hello world c 1 10 bar foo 123 100 a b 0 
stringMap keys: bar foo 123 100 world c 1 10 b 0 hello a 
... 

Answer 2

यदि चश्मे कहते हैं कि पुनरावृत्ति आदेश निर्दिष्ट नहीं है तो विशिष्ट मामलों में एक विशिष्ट आदेश से इनकार नहीं किया जाता है।

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

Answer 3

ध्यान दें कि चाबियों पर कुल क्रम होने पर सम्मिलन आदेश के बावजूद स्थिर होने के लिए यह अजीब नहीं है (क्योंकि अक्सर वे समरूप प्रकार के होते हैं); यदि कुछ और नहीं है, तो यह एक ही हैश उत्पन्न करने वाली चाबियों पर कुशल खोज की अनुमति दे सकता है।

यह एक अलग अंतर्निहित कार्यान्वयन को भी प्रतिबिंबित कर सकता है - विशेष रूप से, यह कुछ ऐसा है जो लोग तारों के लिए चाहते हैं, लेकिन पूर्णांक के लिए आप इसके बजाय एक स्पैस सरणी का उपयोग कर सकते हैं।