मैप (जिसे एसोसिएटिव एरे, हैश टेबल, हैश मैप, हैश सेट, डिक्ट के रूप में भी जाना जाता है) दिन-प्रतिदिन के काम, प्रोग्रामिंग प्रतियोगिताओं या नौकरी के साक्षात्कार के दौरान विभिन्न एल्गोरिदम समस्याओं को हल करने के लिए एक आवश्यक डेटा संरचना है। इसलिए, यह समझना आवश्यक है कि डेवलपर के रूप में मैप्स आपको कौन सी सुविधाएँ प्रदान करते हैं: उनके द्वारा समर्थित ऑपरेशन, विभिन्न ऑपरेशनों की समय और स्थान जटिलता, और कोड में इस संरचना का उपयोग कैसे करें। इस ज्ञान और कुछ व्यावहारिक अनुभव का उपयोग करके, आप उन मामलों का पता लगाने में सक्षम होंगे जब आपको अपनी समस्या को हल करने के लिए मैप को लागू करने की आवश्यकता होगी। आप जिस लेख को अभी पढ़ रहे हैं, वह मैप्स के उपयोग के लिए एक व्यापक मार्गदर्शिका प्रदान करता है। हम सामान्य रूप से मैप डेटा संरचना के संक्षिप्त अवलोकन के साथ शुरू करेंगे और फिर गो प्रोग्रामिंग भाषा में मैप्स के कार्यान्वयन में गहराई से उतरेंगे और समवर्ती कोड में मैप्स का उपयोग करने की रणनीतियों पर चर्चा करेंगे।
आइए एक महत्वपूर्ण अवधारणा पर चर्चा करके शुरू करें जो विभिन्न प्रोग्रामिंग भाषाओं में कार्यान्वित सभी डेटा संरचनाओं के पीछे निहित है: अमूर्त डेटा प्रकार। यह एक गणितीय मॉडल है जिसका उपयोग डेटा प्रकार द्वारा समर्थित संचालन, इन संचालनों के व्यवहार और संभावित मानों के संदर्भ में डेटा प्रकार का वर्णन करने के लिए किया जाता है जिन्हें उनसे पारित या प्राप्त किया जा सकता है। मैप के लिए एक अमूर्त डेटा प्रकार भी है, जिसे एसोसिएटिव ऐरे के रूप में जाना जाता है।
एसोसिएटिव ऐरे एक अमूर्त डेटा प्रकार है जिसका उपयोग कुंजी और मान युग्मों के संग्रह को इस तरह से संग्रहीत करने के लिए किया जाता है कि प्रत्येक कुंजी संग्रह में केवल एक बार दिखाई देती है, या दूसरे शब्दों में, संग्रह में प्रत्येक कुंजी के लिए केवल एक मान होता है। यह get
, set
, और delete
संचालन का समर्थन करता है।
आइए कल्पना करें कि हमारे पास एक एसोसिएटिव ऐरे का कार्यान्वयन है जो कुंजी और मान युग्मों को संग्रहीत कर सकता है, जहां कुंजी और मान दोनों स्ट्रिंग हैं, गो प्रोग्रामिंग भाषा में, और देखें कि परिचालन कैसा दिखता है।
package main import ( "fmt" ) // type AssociativeArray implementation somewhere here func main() { // Initialize a new associative array. associativeArray := NewAssociativeArray() // Set the value for the key "Alice". associativeArray.Set("Alice", "apple") // Attempt to retrieve and print the value associated with "Alice". valueForAlice, found := associativeArray.Get("Alice") if found { fmt.Println(valueForAlice) // Output: "apple" } else { fmt.Println("No value found for Alice.") } // Delete the entry associated with "Alice". associativeArray.Delete("Alice") // Attempt to retrieve the value for "Alice" after deletion to check error handling. valueForAlice, found = associativeArray.Get("Alice") if !found { fmt.Println("No value found for Alice. (Deleted)") } // Attempt to retrieve the value for "Bob" which was never set. valueForBob, found := associativeArray.Get("Bob") if !found { fmt.Println("No value found for Bob. (Never set)") } }
पहले से सेट की गई कुंजी को सेट करना एक वैध ऑपरेशन है, लेकिन इस मामले में, पुरानी कुंजी के साथ एक नया मान संबद्ध होगा, और पिछले मान को पुनः प्राप्त करना असंभव होगा। एसोसिएटिव एरे के कार्यान्वयन के आधार पर इसे हटाया या छायांकित किया जा सकता है।
package main import ( "fmt" ) // type AssociativeArray implementation somewhere here func main() { // Initialize a new associative array. associativeArray := NewAssociativeArray() // Set value associated with "Alice" key associativeArray.Set("Alice", "apple") // Get value associated with "Alice" key valueForAlice := associativeArray.Get("Alice") fmt.Println(valueForAlice) // This line will print "apple" // Set new value associated with "Alice" key associativeArray.Set("Alice", "orange") // Get new value associated with "Alice" key valueForAlice = associativeArray.Get("Alice") fmt.Println(valueForAlice) // This line will print "orange" }
यह बहुत बढ़िया है, लेकिन आप पूछ सकते हैं कि वास्तविक जीवन में एसोसिएटिव ऐरे को कैसे लागू किया जाए। वास्तव में, कार्यान्वयन की कोई सीमा नहीं है। आप इसे किसी भी तरह से लागू कर सकते हैं जिसकी आप कल्पना कर सकते हैं; आपको केवल इस अमूर्त डेटा प्रकार के लिए आवश्यक संचालन का समर्थन करने की आवश्यकता है। हालाँकि, कई दृष्टिकोण हैं जो सबसे आम हैं: हैश मैप और बाइनरी सर्च ट्री। उनके बीच का अंतर उनके समय और स्थान की जटिलताओं में निहित है और निश्चित रूप से, कुंजियों और मूल्यों को संग्रहीत करने और पुनर्प्राप्त करने के लिए एल्गोरिदम में निहित है। आगे बढ़ते हुए, हम हैश मैप कार्यान्वयन पर ध्यान केंद्रित करेंगे, लेकिन यह ध्यान देने योग्य है कि बाइनरी सर्च ट्री का उपयोग एसोसिएटिव ऐरे को लागू करने के लिए भी किया जा सकता है।
हमने पाया कि हैश मैप एक डेटा संरचना है जो एसोसिएटिव एरे ऑपरेशन को लागू करती है: कुंजी के लिए मान सेट करना, कुंजी द्वारा मान प्राप्त करना और कुंजी से जुड़े मान को हटाना। लेकिन हैश मैप वास्तव में कैसे काम करता है? आइए जानें।
यहाँ मुख्य विचार "हैश" शब्द के पीछे छिपा है। हैश मैप, हैश फ़ंक्शन को कुंजी पास करके सरणी में उस स्थान के सूचकांक की गणना करने के लिए हैश फ़ंक्शन का उपयोग करता है जहाँ मान संग्रहीत किया जाएगा। आइए गो प्रोग्रामिंग भाषा का उपयोग करके एक सरल हैश मैप को लागू करने का प्रयास करें ताकि यह देखा जा सके कि हैश फ़ंक्शन और सरणी एक साथ मिलकर हैश मैप बनाने के लिए कैसे काम करते हैं।
package main import "fmt" func main() { // Define an array to hold string data array := make([]string, 10) // Hash function that returns an integer based on the key and array length hash := func(key string, length int) int { calculatedHash := 0 for _, char := range key { calculatedHash += int(char) } return calculatedHash % length } // Set operation: store a value associated with a key index := hash("Alice", len(array)) array[index] = "apple" // Get operation: retrieve the value associated with a key index = hash("Alice", len(array)) fmt.Println(array[index]) // Should print "apple" // Delete operation: remove the value associated with a key index = hash("Alice", len(array)) array[index] = "" // Setting it to empty string, assuming nil is not an option // Check if the deletion was successful index = hash("Alice", len(array)) if array[index] == "" { fmt.Println("Value deleted successfully.") } else { fmt.Println("Value still exists:", array[index]) } }
यह वास्तव में एक सरलीकृत तरीका है कि वास्तविक हैश मैप कैसे काम करता है। आप देख सकते हैं कि हमारा कार्यान्वयन कुछ मामलों में टूट सकता है। यदि आपने इसे नोटिस नहीं किया है, तो पढ़ना जारी रखने से पहले संभावित मुद्दों के बारे में सोचने के लिए थोड़ा समय लें।
क्या आप यह पता लगाने में सफल रहे कि पिछले कार्यान्वयन में समस्या क्या है? यह एक ऐसी स्थिति है जहाँ दो अलग-अलग स्ट्रिंग एक ही हैश उत्पन्न कर सकती हैं। बिल्कुल, हमारे पास केवल len(array)
संभावित हैश मान हैं लेकिन विभिन्न कुंजियों की अनंत संख्या है, और पिजनहोल सिद्धांत द्वारा, हम दो अलग-अलग कुंजियाँ पा सकते हैं जो एक ही हैश उत्पन्न करेंगी, और इसका मतलब है कि वे सरणी में एक ही स्थिति के अनुरूप होंगी।
हम इसके साथ क्या करेंगे? हमें इस स्थिति से निपटने का कोई तरीका खोजने की ज़रूरत है। सौभाग्य से, स्मार्ट लोगों ने पहले ही इस समस्या को हल कर लिया है और कई जाने-माने समाधानों को लागू किया है, इसलिए आइए हम पहिया को फिर से आविष्कार करने के बजाय बस उनका उपयोग करें।
पृथक् श्रृंखलाबद्धता.
इस दृष्टिकोण में, मानों को सीधे सरणी में संग्रहीत करने के बजाय, हम प्रत्येक इंडेक्स के लिए सरणी में एक लिंक्ड सूची संग्रहीत करेंगे। जब हम मानचित्र में एक नया मान जोड़ते हैं, तो हम सबसे पहले यह देखने के लिए खोज करेंगे कि क्या समान कुंजी वाला कोई आइटम है। यदि है, तो बस मान अपडेट करें; अन्यथा, लिंक्ड सूची में एक नया आइटम जोड़ें।
खुला संबोधन
ओपन एड्रेसिंग टकराव समाधान का एक और तरीका है। अब हम प्रत्येक सरणी स्थिति में एक कुंजी और मान जोड़ी संग्रहीत करेंगे। यदि हम एक नया मान जोड़ने का प्रयास करते हैं और ऐसी स्थिति का सामना करते हैं जहाँ इस स्थिति में पहले से ही एक मान है, तो हम जांच का उपयोग करना शुरू करते हैं। जांच रैखिक, द्विघात, किसी अन्य हैशिंग फ़ंक्शन का उपयोग करके या यादृच्छिक भी हो सकती है। रैखिक जांच में, आप तब तक इंडेक्स को एक से बढ़ाना शुरू करते हैं जब तक कि आपको अपने अंतर्निहित सरणी में खाली स्थान न मिल जाए। यही प्रक्रिया तब होती है जब आप सरणी से कोई मान प्राप्त करने का प्रयास करते हैं और ऐसी स्थिति का सामना करते हैं जहाँ सरणी स्थिति में कुंजी खोज कुंजी के अनुरूप नहीं होती है।
आइए अलग-अलग चेनिंग दृष्टिकोण के कार्यान्वयन पर नज़र डालें क्योंकि यह गो में लागू किए गए दृष्टिकोण के बहुत समान है। लेकिन स्कीमा की जाँच करने से पहले, आइए देखें कि हमारा हैश मैप कैसा दिखेगा।
package main import ( "fmt" "hash/fnv" ) // Entry represents a key-value pair in the linked list type Entry struct { Key string Value string Next *Entry } // HashMap represents the hash table structure type HashMap struct { Buckets []*Entry Size int } // NewHashMap creates a new hash map with a given size func NewHashMap(size int) *HashMap { return &HashMap{ Buckets: make([]*Entry, size), Size: size, } } // HashFunction computes the bucket index for a given key func (h *HashMap) HashFunction(key string) int { hasher := fnv.New32() hasher.Write([]byte(key)) return int(hasher.Sum32()) % h.Size } // Insert adds a new key-value pair to the hash map func (h *HashMap) Set(key, value string) { index := h.HashFunction(key) entry := &Entry{Key: key, Value: value} if h.Buckets[index] == nil { h.Buckets[index] = entry } else { current := h.Buckets[index] for current.Next != nil { current = current.Next } current.Next = entry } } // Search finds the value for a given key in the hash map func (h *HashMap) Get(key string) (string, bool) { index := h.HashFunction(key) current := h.Buckets[index] for current != nil { if current.Key == key { return current.Value, true } current = current.Next } return "", false } // Delete removes an entry from the hash map based on the key func (h *HashMap) Delete(key string) { index := h.HashFunction(key) if h.Buckets[index] != nil { if h.Buckets[index].Key == key { h.Buckets[index] = h.Buckets[index].Next } else { current := h.Buckets[index] for current.Next != nil { if current.Next.Key == key { current.Next = current.Next.Next break } current = current.Next } } } } func main() { hm := NewHashMap(10) hm.Set("name", "John") hm.Set("age", "30") value, exists := hm.Get("name") if exists { fmt.Println("Found:", value) } else { fmt.Println("Not found") } hm.Delete("name") value, exists = hm.Get("name") if exists { fmt.Println("Found:", value) } else { fmt.Println("Not found") } } // OUTPUT: // Found: John // Not found
यह उन लोगों के लिए एक उन्नत विषय हो सकता है जो एल्गोरिदमिक जटिलता की अवधारणा से परिचित नहीं हैं। यदि आप इस विवरण में खुद को पहचानते हैं, तो इस लिंक का अनुसरण करें और इस अवधारणा के बारे में जानें।
जब हम एल्गोरिदम और डेटा संरचनाओं के बारे में तर्क करते हैं तो समय और स्थान जटिलता वास्तव में महत्वपूर्ण होती है क्योंकि वे सीधे हमारे कोड के प्रदर्शन को प्रभावित करते हैं। आइए पिछले अध्याय में दिए गए कार्यान्वयन की जटिलता को समझने की कोशिश करें।
हैश मैप में एक नया कुंजी-मूल्य जोड़ा जोड़ने के लिए, हमें हैश की गणना करने, इंडेक्स पर स्थित लिंक्ड सूची को खोजने और अपनी कुंजी खोजने के लिए लिंक्ड सूची से गुजरने की आवश्यकता है। पहली चीज जो समय जटिलता को प्रभावित कर सकती है वह है कुंजी का आकार; हम मानते हैं कि औसत कुंजी का आकार छोटा है और हैश फ़ंक्शन की समय जटिलता कुंजी के आकार पर रैखिक रूप से निर्भर करती है। इस मामले में, हम मान सकते हैं कि कुंजी हैश की गणना के लिए औसत समय जटिलता O(1)
है। इसके बाद, हमें लिंक्ड सूची में सभी आइटम से गुजरना होगा। आइटम की संख्या इस बात पर निर्भर करती है कि कितने टकराव होते हैं, और सबसे खराब स्थिति में, यह O(n)
होगा जब सभी आइटम एक ही हैश के अनुरूप हों। इसलिए, जोड़ ऑपरेशन के लिए कुल समय जटिलता O(1) + O(n) = O(n)
है
हम लोड फैक्टर नामक एक अनुमान के आधार पर अंतर्निहित सरणी के आकार बदलने को लागू करके औसत समय जटिलता को कम कर सकते हैं। यह बस हैश मैप में कुंजियों की संख्या को अंतर्निहित सरणी में स्लॉट की संख्या से विभाजित किया जाता है। यदि यह मान एक निश्चित सीमा से अधिक है, तो हम अंतर्निहित सरणी का आकार बदल सकते हैं और सभी मानों को नई सरणी में कॉपी कर सकते हैं। उसके बाद, प्रत्येक लिंक की गई सूची औसतन आकार में सीमित होगी। इस मामले में, हम लोड फैक्टर मान इस तरह से पा सकते हैं कि अधिकांश मामलों के लिए औसत समय जटिलता O(1)
होगी। हम यहाँ गणना में नहीं जाएँगे, लेकिन इसे समझना महत्वपूर्ण है।
इस प्रकार, हैश मैप निम्नलिखित समय और स्थान जटिलता प्रतिबंध प्रदान करता है:
समय जटिलता: सभी कार्यों के लिए औसतन O(1)
।
स्थान जटिलता: O(n)
क्योंकि हम प्रत्येक कुंजी के लिए एक लिंक्ड सूची इकाई संग्रहीत करते हैं।
हैश मैप को लागू करने के सिद्धांत के बारे में जानकारी के साथ, आइए देखें कि गो प्रोग्रामिंग भाषा हमारे लिए मैप्स के लिए कौन से बिल्ट-इन प्रकार प्रदान करती है। गो में मैप बनाने के कई तरीके हैं:
package main func main() { // Using the make Function: This is the most common way to create a map. // You specify the type of the keys and values. m1 := make(map[string]int) // Create a map with string keys and integer values. // You can also optionally set the size of the underlying array using a second argument if // you know how many items you will store in the map before creation. m2 := make(map[string]int, 10) // Using Map Literals: This method is similar to array or slice literals and is // useful for initializing a map with some values. m3 := map[string]int{"one": 1, "two": 2} // Creates and initializes a map. // Nil Map: A map can also be declared without initialization. Such a map // is nil and has no keys, nor can it be added to. var m4 map[string]int // m4 is nil and you cannot add keys to it without initializing it first. // To add keys to a nil map, it must first be initialized using the make function. // m3["hello"] = 1 // Would panic. Map m3 is not nil here and will not cause a panic, this comment should refer to m4 or another nil map. m4 = make(map[string]int) // Now m4 is initialized and ready for use. }
गो बिल्ट-इन मैप प्रकार एसोसिएटिव ऐरे द्वारा अपेक्षित सभी तीन ऑपरेशनों को क्रियान्वित करता है तथा मैप आइटमों पर पुनरावृत्ति के लिए अतिरिक्त सुविधा भी प्रदान करता है:
package main import "fmt" func main() { m := make(map[string]int) // Adding or updating an element. m["one"] = 1 // Retrieving an element and checking if a key exists. value, ok := m["four"] if ok { fmt.Println("Value exists in map:", value) } else { fmt.Println("Value doesn't exist.") } // Deleting an element. delete(m, "one") // You can iterate over a map using a for loop along with the range keyword. // This gives you access to each key and value in the map. // You shouldn't rely on the order of items; even if you run the for loop several times // in sequence, you can get a different order of items. It's a property of hash tables // in general. Items in the hash table do not have a particular order. for key, value := range m { fmt.Println(key, value) } }
कोई भी तुलनीय प्रकार गो मैप्स में कुंजी हो सकता है। तुलनीय प्रकारों में बूलियन, संख्यात्मक, स्ट्रिंग, पॉइंटर, चैनल और इंटरफ़ेस प्रकार, साथ ही स्ट्रक्चर या एरे शामिल हैं जिनमें केवल तुलनीय प्रकार होते हैं। साथ ही, मैप में मानों के रूप में उपयोग किए जा सकने वाले प्रकारों पर वस्तुतः कोई प्रतिबंध नहीं है। वे पूर्णांक और स्ट्रिंग जैसे सरल प्रकारों से लेकर स्लाइस, अन्य मैप या यहां तक कि फ़ंक्शन जैसे जटिल प्रकारों तक कुछ भी हो सकते हैं।
अब हम मैप सोर्स कोड की खोज करके मैप्स के कार्यान्वयन की जांच करेंगे। इससे हमें यह समझने में मदद मिलेगी कि मैप्स को आंतरिक रूप से कैसे लागू किया जाता है। गो के मैप का सोर्स कोड यहाँ पाया जा सकता है।
गो में मैप पहले चर्चित हैश मैप का कार्यान्वयन है। हमारे पिछले उदाहरण में, हमने टकराव समाधान के लिए एक लिंक्ड सूची का उपयोग किया था। गो एक अलग दृष्टिकोण का उपयोग करता है; एक लिंक्ड सूची के बजाय, बकेट हैं - प्रत्येक अंतर्निहित सरणी इंडेक्स पर अन्य उप-सरणी। इसलिए अनिवार्य रूप से, अंतर्निहित सरणी एक दो-आयामी उप-सरणी है। प्रत्येक बकेट में 8 कुंजी-मूल्य जोड़े तक होते हैं। यदि 8 से अधिक कुंजियाँ एक बकेट में हैश होती हैं, तो हम अतिरिक्त बकेट को एक से बाहर निकलने के लिए चेन करते हैं - ओवरफ़्लो बकेट। हैश के निम्न-क्रम बिट्स का उपयोग बकेट का चयन करने के लिए किया जाता है। प्रत्येक बकेट में प्रत्येक हैश के कुछ उच्च-क्रम बिट्स होते हैं ताकि एक ही बकेट के भीतर प्रविष्टियों को अलग किया जा सके। जब मैप बढ़ता है, तो हम बकेट की एक नई सरणी को दोगुना बड़ा आवंटित करते हैं। बकेट को पुराने बकेट सरणी से नए बकेट सरणी में वृद्धिशील रूप से कॉपी किया जाता है।
मानचित्र का प्रतिनिधित्व करने वाली मुख्य संरचनाओं को hmap और bmap कहा जाता है। हम सरलता के लिए संरचना में कुछ सहायक फ़ील्ड छोड़ देते हैं। एल्गोरिदम के विचार को समझने के लिए वे मायने नहीं रखते:
type hmap struct { count int // # of live cells == size of map. Must be first (used by len() builtin) 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 // some other fields... } // A bucket for a Go map. type bmap struct { // tophash generally contains the top byte of the hash value // for each key in this bucket. If tophash[0] < minTopHash, // tophash[0] is a bucket evacuation state instead. tophash [abi.MapBucketCount]uint8 // Followed by bucketCnt keys and then bucketCnt elems. // Followed by an overflow pointer. }
count
वर्तमान में मानचित्र में संग्रहीत वस्तुओं की संख्या है। buckets
अंतर्निहित सरणी है जहाँ हम नए आइटम संग्रहीत करते हैं, और oldbuckets
वह सरणी है जहाँ हमने मानचित्र का आकार बदलने से पहले आइटम संग्रहीत किए थे। आकार बदलने के समय मानचित्र आइटम को स्थानांतरित करने के बजाय, गो इसे धीरे-धीरे करता है। buckets
और oldbuckets
ऐसे पॉइंटर्स हैं जो bmap
स्ट्रक्चर की ओर इशारा करते हैं, जो tophash
संग्रहीत करता है - बकेट में संग्रहीत प्रत्येक कुंजी के लिए हैश के पहले बाइट की एक सरणी - उसके बाद MapBucketCount
कुंजियाँ और MapBucketCount
मान, अंत में एक ओवरफ़्लो पॉइंटर के साथ। MapBucketCount
एक आर्किटेक्चर-विशिष्ट मान है, जो दस्तावेज़ के अनुसार 8 से अधिक नहीं है। मेमोरी में मैप कैसा दिखता है, इसे बेहतर ढंग से समझने के लिए, यहाँ एक तस्वीर है।
किसी कुंजी से जुड़े मूल्य को खोजने के लिए, हमें सबसे पहले हैश की गणना करनी होगी, जिसका उपयोग हम उस बकेट को निर्धारित करने के लिए करेंगे जहाँ हमारी कुंजी स्थित है। इसके लिए, Go आर्किटेक्चर और हैश किए जाने वाले प्रकार के आधार पर विभिन्न हैश फ़ंक्शन का उपयोग करता है। हैश की गणना करने के बाद, Go उस इंडेक्स की गणना करने के लिए कई अंतिम बिट्स का उपयोग करता है जहाँ हमारी कुंजी स्थित हो सकती है। Go हैश के पहले बाइट को टॉपशैश सरणी में भी संग्रहीत करता है, और कुंजी के हैश का उपयोग करके, आप tophash
उपयोग करके बकेट में संभावित कुंजी इंडेक्स को आसानी से ढूँढ सकते हैं। उसके बाद, हमें खोजी गई कुंजी की तुलना बकेट में संग्रहीत कुंजी से भी करनी होगी क्योंकि हैश के पहले बाइट के बीच टकराव भी हो सकता है। इस प्रक्रिया को चित्र में दर्शाया गया है।
हमने मैप के आंतरिक कार्यान्वयन पर विचार किया है, लेकिन गो एक ऐसी भाषा है जिसे अत्यधिक समवर्ती कोड विकसित करने के लिए डिज़ाइन किया गया है। हम ऐसे मामलों में मैप के साथ कैसे काम करेंगे जहाँ दो या अधिक गोरूटीन एक साथ मैप पर ऑपरेशन करते हैं? आइए दो मामलों पर विचार करें: एक साथ चलने वाले दो गोरूटीन पहले से आरंभ किए गए मैप से कुछ मान पढ़ते हैं, और जब गोरूटीन लेखन ऑपरेशन करते हैं।
किसी साझा मानचित्र से कुछ मान पढ़ने के लिए दो गोरूटीन एक साथ चलने की स्थिति में, हमें समस्याओं का सामना नहीं करना पड़ता क्योंकि पढ़ने के संचालन के दौरान मानचित्र की हमारी आंतरिक स्थिति नहीं बदलती है। इसलिए, हम सुरक्षित रूप से एक साथ पढ़ सकते हैं।
package main import ( "fmt" "sync" ) func main() { var wg sync.WaitGroup m := make(map[string]int) m["a"] = 1 m["b"] = 2 readMap := func(key string) { value, ok := m[key] if ok { fmt.Println("Read:", key, value) } else { fmt.Println("Key not found:", key) } wg.Done() } wg.Add(2) go readMap("a") go readMap("b") wg.Wait() }
दूसरी ओर, जब हम समवर्ती लेखन करते हैं, तो लेखन ऑपरेशन के दौरान मानचित्र स्थिति बदल सकता है। जैसा कि हमने पिछले अनुभाग में पहले ही जांच की है, लेखन ऑपरेशन परमाणु नहीं है। इसका मतलब है कि मानचित्र संशोधन के चरणों के बीच अन्य ऑपरेशन हो सकते हैं, और यदि हम किसी अन्य लेखन प्रक्रिया के दौरान पढ़ने या लिखने का प्रयास करते हैं, तो हम गलत स्थिति में मानचित्र का सामना कर सकते हैं। यदि आप मानचित्र पर समवर्ती लेखन करने का प्रयास करते हैं, तो Go यह पता लगाने के लिए पर्याप्त स्मार्ट है और एक fatal error: concurrent map writes
।
इस समस्या से निपटने के लिए, हमें म्यूटेक्स का उपयोग करने की आवश्यकता है। म्यूटेक्स एक सिंक्रोनाइज़ेशन प्रिमिटिव है जो स्टेट को एक साथ कई थ्रेड्स द्वारा संशोधित या एक्सेस किए जाने से रोकता है। यह दो ऑपरेशन, लॉक और अनलॉक का समर्थन करता है, जिन्हें परमाणु रूप से निष्पादित किया जाता है और इसलिए सुरक्षित हैं। वास्तव में, हम RWMutex का उपयोग कर सकते हैं, जो कई पाठकों द्वारा पढ़ने के लिए लॉकिंग की अनुमति देता है लेकिन लिखने के लिए केवल एक। यह हमें उन मामलों में प्रदर्शन को अनुकूलित करने में मदद कर सकता है जहां बहुत सारे रीड हैं। आइए समवर्ती सुरक्षित मानचित्र के लिए कार्यान्वयन पर नज़र डालें।
package main import ( "fmt" "sync" ) // ConcurrentMap wraps a Go map with a sync.RWMutex to manage concurrent access with optimized read performance type ConcurrentMap struct { sync.RWMutex items map[string]interface{} } // NewConcurrentMap creates a new concurrent map func NewConcurrentMap() *ConcurrentMap { return &ConcurrentMap{ items: make(map[string]interface{}), } } // Set adds or updates an element in the map func (m *ConcurrentMap) Set(key string, value interface{}) { m.Lock() defer m.Unlock() m.items[key] = value } // Get retrieves an element from the map func (m *ConcurrentMap) Get(key string) (interface{}, bool) { m.RLock() defer m.RUnlock() value, exists := m.items[key] return value, exists } // Delete removes an element from the map func (m *ConcurrentMap) Delete(key string) { m.Lock() defer m.Unlock() delete(m.items, key) } // Items returns a copy of all items in the map for safe iteration func (m *ConcurrentMap) Items() map[string]interface{} { m.RLock() defer m.RUnlock() itemsCopy := make(map[string]interface{}) for key, value := range m.items { itemsCopy[key] = value } return itemsCopy } func main() { cmap := NewConcurrentMap() cmap.Set("name", "John Doe") cmap.Set("age", 30) if name, ok := cmap.Get("name"); ok { fmt.Println("Name:", name) } if age, ok := cmap.Get("age"); ok { fmt.Println("Age:", age) } items := cmap.Items() fmt.Println("All items:", items) }
मानक पैकेज में समवर्ती सुरक्षित मैप का एक और कार्यान्वयन है: sync.Map. लेकिन हमें sync.Map या Mutex वाले मैप का उपयोग कब करना चाहिए? यह पता लगाने का समय आ गया है। दस्तावेज़ के अनुसार, Map प्रकार दो सामान्य उपयोग मामलों के लिए अनुकूलित है:
जब किसी दिए गए कुंजी के लिए प्रविष्टि केवल एक बार लिखी जाती है, लेकिन कई बार पढ़ी जाती है, जैसा कि कैश में होता है जो केवल बढ़ता है
जब कई गोरूटीन कुंजी के असंबद्ध सेटों के लिए प्रविष्टियों को पढ़ते, लिखते और अधिलेखित करते हैं। इन दो मामलों में, मैप का उपयोग एक अलग म्यूटेक्स या RWMutex के साथ जोड़े गए गो मैप की तुलना में लॉक विवाद को काफी कम कर सकता है।
इन मामलों में म्यूटेक्स वाले मानचित्र की तुलना में sync.Map बेहतर क्यों काम करता है, इसे बेहतर ढंग से समझने और समझने के लिए हमें sync.Map के स्रोत कोड की जांच करनी चाहिए।
type Map struct { mu Mutex read atomic.Pointer[readOnly] dirty map[any]*entry // some other fields... } // readOnly is an immutable struct stored atomically in the Map.read field. type readOnly struct { m map[any]*entry amended bool // true if the dirty map contains some key not in m. } // An entry is a slot in the map corresponding to a particular key. type entry struct { p atomic.Pointer[any] }
Map
मैप डेटा के दो प्रतिनिधित्व बनाए रखता है: read
और dirty
। रीड मैप ( read
): यह Map
के लिए प्राथमिक डेटा स्टोर है और समवर्ती रीड एक्सेस के लिए है। इसे readOnly
स्ट्रक्चर के लिए एक atomic.Pointer
द्वारा दर्शाया जाता है, जो मैप के स्नैपशॉट के एटोमिक और लॉक-फ्री रीड को सुनिश्चित करता है। जब किसी कुंजी को देखा जाता है, तो यह सबसे पहले read
मैप की जांच करता है। यदि कुंजी नहीं मिलती है और मैप को amended
के रूप में चिह्नित किया जाता है (यह दर्शाता है कि dirty
मैप में नई कुंजियाँ हैं जो अभी read
मैप में नहीं हैं), तो यह म्यूटेक्स लॉक ( mu
) के तहत dirty
मैप की जांच करने के लिए वापस आ जाता है। dirty
मैप ( dirty
): यह मैप संशोधन के तहत प्रविष्टियों और read
मैप में अभी तक दिखाई नहीं देने वाली नई प्रविष्टियों read
संग्रहीत करता है। इस मैप तक पहुंच के लिए अनन्य पहुंच सुनिश्चित करने के लिए dirty
लॉक को read
करना आवश्यक है nil
"मिस" (असफल लुकअप जिसके लिए dirty
मानचित्र पर वापस जाना आवश्यक था) की एक निश्चित सीमा के बाद, dirty
मानचित्र को नया read
मानचित्र बना दिया जाता है, और यदि आवश्यक हो तो एक नया dirty
मानचित्र तैयार किया जाता है।
अब हम यह समझ सकते हैं कि म्यूटेक्स और सिंक.मैप वाले अंतर्निर्मित मानचित्र के बीच क्या अंतर है:
sync.Map
: लॉक विवाद को कम करने के लिए डिज़ाइन किया गया। अधिकांश रीड ऑपरेशन के लिए, एटॉमिक read
पॉइंटर के कारण लॉक की आवश्यकता नहीं होती है। मैप के केवल एक छोटे हिस्से को प्रभावित करने वाले राइट और डिलीट भी लॉक अवधि को कम करते हैं क्योंकि वे केवल dirty
मैप को लॉक करते हैं।sync.Map
: मैप के दो संस्करण बनाए रखता है और अधिक मेमोरी-गहन हो सकता है। इन संस्करणों को प्रबंधित करने का तर्क जटिलता को बढ़ाता है।sync.Map
की तुलना में सरल और कम मेमोरी का उपयोग करता है क्योंकि यह मानचित्र का केवल एक संस्करण बनाए रखता है।sync.Map
: ऐसे उपयोग मामलों के लिए अनुकूलित जहां कुंजियाँ अधिकतर पढ़ी जाती हैं और अक्सर अद्यतन नहीं की जाती हैं या जहां कई ऑपरेशन कुंजियों के असंबद्ध सेटों पर होते हैं।
संक्षेप में, sync.Map
उन परिदृश्यों के लिए विशेषीकृत है जो जटिलता और मेमोरी उपयोग में वृद्धि की कीमत पर लॉक विवाद को कम करने के लिए इसके समवर्ती अनुकूलन का लाभ उठा सकते हैं। इसके विपरीत, म्यूटेक्स वाला एक मानक गो मैप एक सरल और अधिक सामान्य समाधान है, लेकिन अत्यधिक समवर्ती वातावरण में प्रदर्शन संबंधी समस्याओं से ग्रस्त हो सकता है।
इस लेख में, हमने मैप डेटा संरचनाओं के उपयोग की जटिलताओं का पता लगाया है, विशेष रूप से गो प्रोग्रामिंग भाषा में उनके कार्यान्वयन और उपयोग पर ध्यान केंद्रित किया है। एसोसिएटिव एरे की मूल अवधारणा से शुरू करते हुए, हमने हैश मैप्स के यांत्रिकी में गहराई से जाना, उनकी परिचालन प्रक्रियाओं, समय और स्थान की जटिलताओं और टकरावों को संभालने के लिए अलग-अलग चेनिंग और ओपन एड्रेसिंग जैसे विभिन्न तरीकों पर चर्चा की।
गो के क्षेत्र में, हमने जांच की कि मैप्स का उपयोग कैसे किया जाता है और भाषा में कैसे बनाया जाता है, hmap
और bmap
जैसी अंतर्निहित संरचनाओं की जांच की। इस अन्वेषण में व्यावहारिक कोड उदाहरण शामिल थे, जो यह प्रदर्शित करते थे कि गो अनुप्रयोगों में मैप्स को कैसे आरंभ, हेरफेर और प्रभावी ढंग से उपयोग किया जाए। इसके अतिरिक्त, हमने मैप्स का उपयोग करते समय समवर्तीता के संभावित नुकसानों पर प्रकाश डाला और समवर्ती पहुँच की आवश्यकता वाले परिदृश्यों के लिए sync.Map
पेश किया, जो लॉक विवाद को कम करता है और प्रदर्शन को अनुकूलित करता है।
मानचित्र डेटा संरचनाओं के इन पहलुओं को समझना न केवल आपके कोडिंग टूलकिट को बढ़ाता है बल्कि आपको सामान्य प्रोग्रामिंग चुनौतियों से अधिक दक्षता और आत्मविश्वास के साथ निपटने के लिए भी तैयार करता है। चाहे आप सरल अनुप्रयोग विकसित कर रहे हों या जटिल सिस्टम जिन्हें समवर्ती वातावरण में इष्टतम प्रदर्शन की आवश्यकता होती है, विभिन्न प्रकार के मानचित्रों का उपयोग कैसे और कब करना है, इसका ज्ञान अमूल्य है। जैसे-जैसे आप अपनी प्रोग्रामिंग विशेषज्ञता का निर्माण करना जारी रखते हैं, अपनी परियोजनाओं में उनकी क्षमता का पूरी तरह से दोहन करने के लिए इन संरचनाओं और उनके विभिन्न कार्यान्वयनों के साथ प्रयोग करते रहें।