जा में हैश टेबल। कार्यान्वयन का विवरण

हम जेनरिक के बिना भाषा में मानचित्र के कार्यान्वयन पर चर्चा करेंगे, विचार करें कि हैश तालिका क्या है, इसे गो में कैसे व्यवस्थित किया जाता है, इस कार्यान्वयन के पेशेवरों और विपक्ष क्या हैं, और इस संरचना का उपयोग करते समय आपको क्या ध्यान देना चाहिए।

कट के तहत विवरण।

---

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

हैश टेबल क्या है

आरंभ करने के लिए, मैं आपको याद दिलाता हूं कि एक हैश तालिका क्या है। यह एक डेटा संरचना है जो आपको कुंजी-मूल्य जोड़े को संग्रहीत करने की अनुमति देता है, और, एक नियम के रूप में, कार्यों को रखने:

• मानचित्रण: map(key) → value
  
• आवेषण: insert(map, key, value)
  
• delete(map, key) : delete(map, key)
  
• खोज: lookup(key) → value
  

जा भाषा में हैश टेबल

गो भाषा में एक हैश टेबल को मैप कीवर्ड द्वारा दर्शाया जाता है और इसे नीचे दिए गए तरीकों में से एक घोषित किया जा सकता है (बाद में इनके बारे में):

  m := make(map[key_type]value_type) m := new(map[key_type]value_type) var m map[key_type]value_type m := map[key_type]value_type{key1: val1, key2: val2} 

मुख्य संचालन निम्नानुसार किए जाते हैं:

• सम्मिलित करें:
  
  

   m[key] = value 

  
  
• हटाने:
  
  

   delete(m, key) 

  
  
• खोज:
  
  

   value = m[key] 

  
  या
  
  

   value, ok = m[key] 

जाने में एक मेज के आसपास जाओ

निम्नलिखित कार्यक्रम पर विचार करें:

 package main import "fmt" func main() { m := map[int]bool{} for i := 0; i < 5; i++ { m[i] = ((i % 2) == 0) } for k, v := range m { fmt.Printf("key: %d, value: %t\n", k, v) } } 

लॉन्च 1:

 key: 3, value: false key: 4, value: true key: 0, value: true key: 1, value: false key: 2, value: true 

रन 2:

 key: 4, value: true key: 0, value: true key: 1, value: false key: 2, value: true key: 3, value: false 

जैसा कि आप देख सकते हैं, आउटपुट रन से भिन्न होता है। और सभी क्योंकि Go में मैप अनियंत्रित है, अर्थात ऑर्डर नहीं किया गया है। इसका मतलब यह है कि आपको आस-पास जाने पर ऑर्डर पर भरोसा करने की आवश्यकता नहीं है। कारण भाषा रनटाइम के स्रोत कोड में पाया जा सकता है:

 // mapiterinit initializes the hiter struct used for ranging over maps. func mapiterinit(t *maptype, h *hmap, it *hiter) {... // decide where to start r := uintptr(fastrand()) ... it.startBucket = r & bucketMask(hB)...} 

खोज स्थान को यादृच्छिक रूप से निर्धारित किया जाता है , इसे याद रखें! अफवाह यह है कि रनटाइम डेवलपर्स उपयोगकर्ताओं को आदेश पर भरोसा नहीं करने के लिए मजबूर कर रहे हैं।

जाओ तालिका खोज

चलो फिर से कोड का एक टुकड़ा देखें। मान लीजिए कि हम जोड़े "संख्या" बनाना चाहते हैं - "संख्या 10 बार":

 package main import ( "fmt" ) func main() { m := map[int]int{0: 0, 1: 10} fmt.Println(m, m[0], m[1], m[2]) } 

हम लॉन्च करते हैं:

 map[0:0 1:10] 0 10 0 

और हम देखते हैं कि जब हमने दो का मान प्राप्त करने की कोशिश की (जिसे हम रखना भूल गए) तो हमें 0. मिला। हम प्रलेखन में इस व्यवहार की व्याख्या करने वाली पंक्तियाँ पाते हैं: “मानचित्र में मौजूद नहीं होने वाली कुंजी के साथ एक मानचित्र मान प्राप्त करने का प्रयास शून्य मान लौटाएगा। नक्शे में प्रविष्टियों का प्रकार। ”, लेकिन रूसी में अनुवादित, इसका मतलब यह है कि जब हम मानचित्र से मूल्य प्राप्त करने की कोशिश करते हैं, लेकिन यह वहां नहीं है, तो हमें एक“ शून्य प्रकार मूल्य ”मिलता है, जो कि नंबर 0. के मामले में क्या करना है। अगर हम मामलों 0 और अनुपस्थिति 2 के बीच अंतर करना चाहते हैं? ऐसा करने के लिए, हम "एकाधिक असाइनमेंट" के एक विशेष रूप के साथ आए - एक ऐसा रूप जहां सामान्य एकल मूल्य के बजाय, नक्शा एक जोड़ी लौटाता है: मूल्य स्वयं और एक और बूलियन जो इस सवाल का उत्तर देता है कि क्या अनुरोधित कुंजी नक्शे में मौजूद है या नहीं।

सही ढंग से पिछले टुकड़े कोड की तरह दिखेगा:

 package main import ( "fmt" ) func main() { m := map[int]int{0: 0, 1: 10} m2, ok := m[2] if !ok { // somehow process this case m2 = 20 } fmt.Println(m, m[0], m[1], m2) } 

और स्टार्टअप पर हमें मिलता है:

map[0:0 1:10] 0 10 20


Go में एक टेबल बनाएं।

मान लीजिए कि हम प्रत्येक शब्द की घटनाओं की संख्या को एक स्ट्रिंग में गिनना चाहते हैं, इसके लिए एक शब्दकोश शुरू करें और इसके माध्यम से जाएं।

 package main func main() { var m map[string]int for _, word := range []string{"hello", "world", "from", "the", "best", "language", "in", "the", "world"} { m[word]++ } for k, v := range m { println(k, v) } } 

क्या आप एक गोफर को पकड़ते हैं? - और वह है!


जब हम इस तरह के कार्यक्रम को शुरू करने की कोशिश करते हैं, तो हमें एक घबराहट होती है और संदेश "शून्य मानचित्र में प्रवेश करने का असाइनमेंट" मिलता है। और सभी क्योंकि मेपा एक संदर्भ प्रकार है और यह एक चर घोषित करने के लिए पर्याप्त नहीं है, आपको इसे आरंभ करने की आवश्यकता है:

 m := make(map[string]int) 

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

  map[key_type]value_type{} 

और यदि आप चाहें, तो तुरंत मानों के साथ आरंभ भी कर सकते हैं, यह विधि भी मान्य है। जैसा कि नए प्रयोग से निर्माण के लिए - मेरी राय में, इसका कोई मतलब नहीं है, क्योंकि यह फ़ंक्शन चर के लिए मेमोरी आवंटित करता है और शून्य सूचक प्रकार से भरा एक पॉइंटर लौटाता है, जो कि नक्शे के मामले में शून्य होगा (हमें उसी के रूप में परिणाम मिलता है var में, अधिक सटीक रूप से इसका सूचक है)।

किसी फंक्शन को मैप कैसे पास किया जाता है

मान लीजिए हमारे पास एक फ़ंक्शन है जो उस संख्या को बदलने की कोशिश करता है जो इसे पारित किया गया था। आइए देखें कि कॉल से पहले और बाद में क्या होता है:

 package main func foo(n int) { n = 10 } func main() { n := 15 println("n before foo =", n) foo(n) println("n after foo =", n) } 

एक उदाहरण, मुझे लगता है, काफी स्पष्ट है, लेकिन अभी भी निष्कर्ष शामिल हैं:

 n before foo = 15 n after foo = 15 

जैसा कि आप शायद अनुमान लगाते हैं, एन फ़ंक्शन मूल्य से आया था, संदर्भ से नहीं, इसलिए मूल चर नहीं बदला है।

आइए करते हैं एक ऐसा ही मेपा ट्रिक:

 package main func foo(m map[int]int) { m[10] = 10 } func main() { m := make(map[int]int) m[10] = 15 println("m[10] before foo =", m[10]) foo(m) println("m[10] after foo =", m[10]) } 

और लो और निहारना:

 m[10] before foo = 15 m[10] after foo = 10 

मान बदल गया है। "ठीक है, मेपा को संदर्भ द्वारा पारित किया गया है?", आप पूछते हैं। नहीं। गो में कोई लिंक नहीं हैं। उदाहरण के लिए C ++ में 2 चरों को 1 पते के साथ बनाना असंभव है। लेकिन फिर आप एक ही पते पर इंगित करते हुए 2 चर बना सकते हैं (लेकिन ये संकेत हैं, और वे गो में हैं)।

मान लीजिए कि हमारे पास एक फ़ंक्शन fn है जो मैप m को इनिशियलाइज़ करता है। मुख्य फ़ंक्शन में, हम बस एक चर घोषित करते हैं, इसे इनिशियलाइज़ करने के लिए भेजते हैं और देखते हैं कि इसके बाद क्या हुआ।

 package main import "fmt" func fn(m map[int]int) { m = make(map[int]int) fmt.Println("m == nil in fn?:", m == nil) } func main() { var m map[int]int fn(m) fmt.Println("m == nil in main?:", m == nil) } 

निष्कर्ष:

m == nil in fn?: false
m == nil in main?: true

इसलिए, चर m को मान द्वारा पारित किया गया था, इसलिए, फ़ंक्शन के लिए एक नियमित इंट पास करने के मामले में, यह नहीं बदला (fn में मूल्य की स्थानीय प्रतिलिपि बदल गई)। फिर मी में पड़े मूल्य को ही क्यों बदला जाता है? इस प्रश्न का उत्तर देने के लिए, भाषा रनटाइम के कोड पर विचार करें:

 // A header for a Go map. type hmap struct { // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go. // Make sure this stays in sync with the compiler's definition. count int // # live cells == size of map. Must be first (used by len() builtin) flags uint8 B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items) noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details hash0 uint32 // hash seed buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0. oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated) extra *mapextra // optional fields } 

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



तस्वीर स्मृति में संरचना का एक योजनाबद्ध प्रतिनिधित्व दर्शाती है - इसमें एक हामप हेडर है, सूचक जो कि गो में एक नक्शा है (इसे var के साथ घोषित किए जाने पर बनाया जाता है, लेकिन इसे प्रारंभ नहीं किया जाता है, जो प्रोग्राम को डालने का प्रयास करते समय दुर्घटना का कारण बनता है)। बाल्टी फ़ील्ड कुंजी-मूल्य जोड़े का एक भंडार है, ऐसे कई बाल्टी हैं, प्रत्येक में 8 जोड़े हैं। पहले "बकेट" में अतिरिक्त हैश बिट्स के लिए स्लॉट होते हैं (e0..e7 को ई - क्योंकि अतिरिक्त हैश बिट्स कहा जाता है)। आगे सभी कुंजियों की सूची के रूप में कुंजियाँ और मान हैं, फिर सभी मानों की एक सूची है।

फ़ंक्शन के हैश के अनुसार, यह निर्धारित किया जाता है कि "बाल्टी" में हम मूल्य डालते हैं, प्रत्येक "बाल्टी" के अंदर 8 टकराव हो सकते हैं, प्रत्येक "बाल्टी" के अंत में एक अतिरिक्त के लिए एक पॉइंटर होता है, अगर पिछले एक ओवरफ्लो होता है।

नक्शा कैसे बढ़ता है?

स्रोत कोड में आप लाइन पा सकते हैं:

  // Maximum average load of a bucket that triggers growth is 6.5. 

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

मानचित्र तत्व का पता लेना।

एक और दिलचस्प बिंदु - भाषा का उपयोग करने की शुरुआत में मैं इस तरह करना चाहता था:

 package main import ( "fmt" ) func main() { m := make(map[int]int) m[1] = 10 a := &m[1] fmt.Println(m[1], *a) } 

लेकिन गो कहते हैं: "मैं [1] का पता नहीं लगा सकता"। डेटा निकासी प्रक्रिया में मूल्य के पते को लेना असंभव क्यों है इसकी व्याख्या। कल्पना करें कि हमने मूल्य का पता ले लिया, और फिर मेपा बढ़ी, नई मेमोरी आवंटित की गई, डेटा को खाली कर दिया गया, पुराने को हटा दिया गया, सूचक गलत हो गया, इसलिए इस तरह के संचालन निषिद्ध हैं।

जेनरिक के बिना नक्शा कैसे लागू किया जाता है?

न तो एक खाली इंटरफ़ेस, और न ही कोड पीढ़ी का इससे कोई लेना-देना है, पूरी बात इसे संकलन समय पर प्रतिस्थापित करना है। गौर करें कि गो से परिचित कार्य क्या हैं:

 v := m["k"] → func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer v, ok := m["k"] → func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) m["k"] = 9001 → func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer delete(m, "k") → func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) 

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

 type mapType struct { key *_type elem *_type ...} type _type struct { size uintptr alg *typeAlg ...} type typeAlg struct { hash func(unsafe.Pointer, uintptr) uintptr equal func(unsafe.Pointer, unsafe.Pointer) bool...} 

MapType कुंजी और मान के डिस्क्रिप्टर (_type) को संग्रहीत करता है। एक प्रकार के डिस्क्रिप्टर के लिए, हैश, आकार, और इसी तरह की तुलना के संचालन (टाइपअल्ग) को परिभाषित किया गया है, इसलिए हम हमेशा जानते हैं कि उनका उत्पादन कैसे किया जाए।

यह कैसे काम करता है इसके बारे में थोड़ा और। जब हम v = m [k] लिखते हैं (कुंजी k से v का मान प्राप्त करने की कोशिश कर रहे हैं), संकलक कुछ इस तरह उत्पन्न करता है:

 kPointer := unsafe.Pointer(&k) vPointer := mapaccess1(typeOf(m), m, kPointer) v = *(*typeOfvalue)vPointer 

यही है, हम एक पॉइंटर को एक कुंजी में ले जाते हैं, मैप टाइप संरचना, जिसमें से हमें पता चलता है कि किस कुंजी और मान के कौन से डिस्क्रिप्टर हैं, पॉइंटर अपने आप को हैंप (यानी, मैप) करता है और इसे सभी को मैपेकैसे 1 में पास कर देता है, जो वैल्यू के लिए एक पॉइंटर लौटाएगा। हमने पॉइंटर को वांछित प्रकार, डेरेफेरेंस में डाला और मूल्य प्राप्त किया।

आइए अब रनटाइम से खोज कोड देखें (जो पढ़ने के लिए थोड़ा अनुकूलित है):

 func lookup(t *mapType, m *mapHeader, key unsafe.Pointer) unsafe.Pointer { 

फ़ंक्शन मैप में कुंजी की खोज करता है और एक पॉइंटर को संबंधित मान पर लौटाता है, दलीलें पहले से ही हमारे लिए परिचित हैं - यह मैप टाइप है, जो कुंजी प्रकारों और मूल्यों के डिस्क्रिप्टर को स्टोर करता है, मैप ही (मैपहेडर) और मेमोरी को पॉइंटर जो कि स्टोर करता है। हम उस मेमोरी को पॉइंटर लौटाते हैं जो वैल्यू को स्टोर करता है।

  if m == nil || m.count == 0 { return zero } 

इसके बाद, हम जाँचते हैं कि क्या मैप हेडर का पॉइंटर शून्य नहीं है, अगर वहाँ 0 एलिमेंट हैं और एक शून्य मान लौटाते हैं, यदि ऐसा है।

  hash := t.key.hash(key, m.seed) // hash := hashfn(key) bucket := hash & (1<<m.logB-1) // bucket := hash % nbuckets extra := byte(hash >> 56) // extra := top 8 bits of hash b := (*bucket)(add(m.buckets, bucket*t.bucketsize)) // b := &m.buckets[bucket] 

हम कुंजी हैश की गणना करते हैं (हम जानते हैं कि किसी प्रकार के विवरणक से दी गई कुंजी की गणना कैसे करें)। फिर हम यह समझने की कोशिश करते हैं कि आपको किस "बाल्टी" में जाने और देखने की ज़रूरत है ("बाल्टियों की संख्या से विभाजित होने की शेष", गणनाएं बस थोड़ी तेज हैं)। फिर हम अतिरिक्त हैश की गणना करते हैं (हम हैश के 8 सबसे महत्वपूर्ण बिट्स लेते हैं) और मेमोरी (पता अंकगणित) में "बाल्टी" की स्थिति निर्धारित करते हैं।

  for { for i := 0; i < 8; i++ { if b.extra[i] != extra { // check 8 extra hash bits continue } k := add(b, dataOffset+i*t.key.size) // pointer to ki in bucket if t.key.equal(key, k) { // return pointer to vi return add(b, dataOffset+8*t.key.size+i*t.value.size) } } b = b.overflow if b == nil { return zero } } 

खोजें, यदि आप देखते हैं, तो यह जटिल नहीं है: हम "बाल्टियों" की जंजीरों से गुजरते हैं, अगले एक पर चलते हैं, अगर आपको यह नहीं मिला। "बाल्टी" में खोज अतिरिक्त हैश की त्वरित तुलना के साथ शुरू होती है (यही कारण है कि ये e0 ... प्रत्येक की शुरुआत में e7 त्वरित तुलना के लिए जोड़ी का "मिनी" हैश हैं)। यदि यह मेल नहीं खाता है, तो आगे बढ़ें, यदि यह होता है, तो हम अधिक सावधानी से जांच करते हैं - हम यह निर्धारित करते हैं कि मेमोरी में झूठ के लिए खोजे जाने का संदेह कहां है, यह तुलना करें कि क्या अनुरोध किया गया था। यदि बराबर है, तो स्मृति में मान की स्थिति निर्धारित करें और वापस लौटें। जैसा कि आप देख सकते हैं, अलौकिक कुछ भी नहीं।

निष्कर्ष

मानचित्रों का उपयोग करें, लेकिन यह जानें और समझें कि वे कैसे काम करते हैं! आप कुछ सूक्ष्मताओं को समझकर रेक से बच सकते हैं - आप मूल्य का पता क्यों नहीं लगा सकते, क्यों सब कुछ आरम्भ के बिना घोषणा के दौरान गिर जाता है, क्यों अग्रिम में मेमोरी आवंटित करना बेहतर होता है यदि तत्वों की संख्या ज्ञात है (हम निकासी से बचेंगे) और बहुत कुछ।

---

संदर्भ:

"गो मैप इन एक्शन", एंड्रयू गेरैंड
"कैसे रनटाइम कुशलता से नक्शे को लागू करता है", डेव चेनी
"अंडरस्टैंडिंग टाइप इन गो", विलियम कैनेडी
नक्शा कार्यान्वयन के अंदर, कीथ रान्डेल
मैप सोर्स कोड, गो रनटाइम
गोलंग युक्ति
प्रभावी जाओ
गोफर के चित्र