গো-তে মানচিত্র আয়ত্ত করা: আপনার যা জানা দরকার

একটি মানচিত্র (এছাড়াও একটি অ্যাসোসিয়েটিভ অ্যারে, হ্যাশ টেবিল, হ্যাশ ম্যাপ, হ্যাশ সেট, ডিক্ট নামেও পরিচিত) হল প্রতিদিনের কাজের সময়, প্রোগ্রামিং প্রতিযোগিতায় বা চাকরির সাক্ষাত্কারের সময় বিভিন্ন অ্যালগরিদমিক সমস্যা সমাধানের জন্য একটি অপরিহার্য ডেটা কাঠামো। তাই, বিকাশকারী হিসাবে মানচিত্র আপনাকে কোন বৈশিষ্ট্যগুলি প্রদান করে তা বোঝা অত্যাবশ্যক: তাদের দ্বারা সমর্থিত ক্রিয়াকলাপ, বিভিন্ন অপারেশনের সময় এবং স্থান জটিলতা এবং কোডে এই কাঠামোটি কীভাবে ব্যবহার করা যায়। এই জ্ঞান এবং কিছু বাস্তব অভিজ্ঞতা ব্যবহার করে, আপনি যখন আপনার সমস্যা সমাধানের জন্য একটি মানচিত্র প্রয়োগ করতে হবে তখন আপনি কেস সনাক্ত করতে সক্ষম হবেন। আপনি বর্তমানে যে নিবন্ধটি পড়ছেন সেটি মানচিত্রের ব্যবহারের জন্য একটি বিস্তৃত নির্দেশিকা প্রদান করে। আমরা সাধারণভাবে মানচিত্রের ডেটা কাঠামোর একটি সংক্ষিপ্ত ওভারভিউ দিয়ে শুরু করব এবং তারপরে Go প্রোগ্রামিং ভাষায় মানচিত্রের বাস্তবায়নে গভীরভাবে ডুব দেব এবং সমসাময়িক কোডে মানচিত্র ব্যবহার করার কৌশল নিয়ে আলোচনা করব।

নতুনদের জন্য মানচিত্র

সহযোগী অ্যারে

চলুন শুরু করা যাক একটি গুরুত্বপূর্ণ ধারণা নিয়ে আলোচনা করে যা বিভিন্ন প্রোগ্রামিং ভাষায় বাস্তবায়িত সমস্ত ডেটা কাঠামোর পিছনে রয়েছে: বিমূর্ত ডেটা টাইপ। এটি একটি গাণিতিক মডেল যা ডেটা টাইপ দ্বারা সমর্থিত ক্রিয়াকলাপের পরিপ্রেক্ষিতে একটি ডেটা টাইপ বর্ণনা করতে ব্যবহৃত হয়, এই ক্রিয়াকলাপগুলির আচরণ এবং সম্ভাব্য মানগুলি যা তাদের কাছে পাস করা বা প্রাপ্ত হতে পারে। একটি মানচিত্রের জন্য একটি বিমূর্ত ডেটা টাইপও রয়েছে, যা একটি সহযোগী অ্যারে হিসাবে পরিচিত।

একটি অ্যাসোসিয়েটিভ অ্যারে হল একটি বিমূর্ত ডেটা টাইপ যা কী এবং মান জোড়ার সংগ্রহকে এমনভাবে সংরক্ষণ করতে ব্যবহৃত হয় যাতে প্রতিটি কী সংগ্রহে একবারই প্রদর্শিত হয়, বা অন্য কথায়, সংগ্রহে প্রতিটি কীর জন্য শুধুমাত্র একটি মান থাকে . এটি 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" }

এটা চমৎকার, কিন্তু আপনি জিজ্ঞাসা করতে পারেন কিভাবে বাস্তব জীবনে একটি সহযোগী অ্যারে বাস্তবায়ন করতে হয়। আসলে, বাস্তবায়নের কোন সীমা নেই। আপনি কল্পনা করতে পারেন যে কোনো উপায়ে এটি বাস্তবায়ন করতে পারেন; আপনাকে শুধুমাত্র এই বিমূর্ত ডেটা টাইপের জন্য প্রয়োজনীয় ক্রিয়াকলাপ সমর্থন করতে হবে। যাইহোক, বেশ কিছু পদ্ধতি আছে যা সবচেয়ে সাধারণ: হ্যাশ ম্যাপ এবং বাইনারি সার্চ ট্রি। তাদের মধ্যে পার্থক্য তাদের সময় এবং স্থান জটিলতা এবং, অবশ্যই, কী এবং মান সংরক্ষণ এবং পুনরুদ্ধার করার জন্য অ্যালগরিদমগুলির মধ্যে রয়েছে। এগিয়ে চলুন, আমরা হ্যাশ মানচিত্র বাস্তবায়নে মনোনিবেশ করব, তবে এটি লক্ষণীয় যে একটি বাইনারি অনুসন্ধান গাছ একটি সহযোগী অ্যারে বাস্তবায়নের জন্য ব্যবহার করা যেতে পারে।

হ্যাশ মানচিত্র

আমরা খুঁজে পেয়েছি যে হ্যাশ ম্যাপ হল একটি ডেটা স্ট্রাকচার যা অ্যাসোসিয়েটিভ অ্যারে ক্রিয়াকলাপগুলিকে প্রয়োগ করে: একটি কী এর জন্য একটি মান সেট করা, কী দ্বারা একটি মান পুনরুদ্ধার করা এবং একটি কী এর সাথে যুক্ত একটি মান মুছে ফেলা। কিন্তু কিভাবে একটি হ্যাশ মানচিত্র আসলে ফণা অধীনে কাজ করে? খুঁজে বের কর.

এখানে মূল ধারণাটি "হ্যাশ" শব্দের পিছনে লুকিয়ে আছে। হ্যাশ ম্যাপ হ্যাশ ফাংশন ব্যবহার করে হ্যাশ ফাংশনের কী পাস করে অ্যারেতে থাকা স্থানের সূচক গণনা করে যেখানে মান সংরক্ষণ করা হবে। একটি হ্যাশ মানচিত্র তৈরি করতে হ্যাশ ফাংশন এবং অ্যারে কীভাবে কাজ করে তা দেখতে Go প্রোগ্রামিং ভাষা ব্যবহার করে একটি সাধারণ হ্যাশ মানচিত্র প্রয়োগ করার চেষ্টা করা যাক।

 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) সম্ভাব্য হ্যাশ মান আছে কিন্তু অসীম সংখ্যক বিভিন্ন কী আছে, এবং pigeonhole নীতি অনুসারে, আমরা দুটি ভিন্ন কী খুঁজে পেতে পারি যা একই হ্যাশ তৈরি করবে, এবং এর মানে হল যে তারা একই অবস্থানের সাথে সঙ্গতিপূর্ণ হবে অ্যারের মধ্যে

আমরা এটা দিয়ে কি করব? এই পরিস্থিতি সামাল দেওয়ার জন্য আমাদের কিছু উপায় খুঁজে বের করতে হবে। সৌভাগ্যবশত, স্মার্ট লোকেরা ইতিমধ্যেই এই সমস্যার সমাধান করেছে এবং বেশ কিছু সুপরিচিত সমাধান বাস্তবায়ন করেছে, তাই আসুন চাকাটি পুনরায় উদ্ভাবনের পরিবর্তে সেগুলি ব্যবহার করি।

• আলাদা চেইনিং।

  এই পদ্ধতিতে, সরাসরি অ্যারেতে মান সংরক্ষণ করার পরিবর্তে, আমরা প্রতিটি সূচকের জন্য অ্যারেতে একটি লিঙ্কযুক্ত তালিকা সংরক্ষণ করব। যখন আমরা মানচিত্রে একটি নতুন মান যোগ করি, আমরা প্রথমে অনুসন্ধান করব যে একই কী সহ একটি আইটেম আছে কিনা। যদি থাকে, তাহলে শুধু মান আপডেট করুন; অন্যথায়, লিঙ্ক করা তালিকায় একটি নতুন আইটেম যোগ করুন।

  
  

• ঠিকানা খুলুন

  ওপেন অ্যাড্রেসিং সংঘর্ষের সমাধানের আরেকটি পদ্ধতি। এখন আমরা প্রতিটি অ্যারের অবস্থানে একটি কী এবং মান জোড়া সংরক্ষণ করব। যদি আমরা একটি নতুন মান যোগ করার চেষ্টা করি এবং এমন একটি পরিস্থিতির সম্মুখীন হই যেখানে এই অবস্থানে ইতিমধ্যে একটি মান রয়েছে, আমরা অনুসন্ধান ব্যবহার শুরু করি। প্রোবিং অন্য হ্যাশিং ফাংশন ব্যবহার করে রৈখিক, চতুর্মুখী হতে পারে, এমনকি র্যান্ডমও হতে পারে। লিনিয়ার প্রোবিং-এ, আপনি আপনার অন্তর্নিহিত অ্যারেতে ফাঁকা স্থান না পাওয়া পর্যন্ত সূচকটি এক দ্বারা বৃদ্ধি করতে শুরু করেন। একই প্রক্রিয়াটি ঘটে যখন আপনি অ্যারে থেকে একটি মান পুনরুদ্ধার করার চেষ্টা করেন এবং এমন পরিস্থিতির মুখোমুখি হন যেখানে অ্যারের অবস্থানের কীটি অনুসন্ধান কীটির সাথে সামঞ্জস্যপূর্ণ নয়।

আসুন আলাদা চেইনিং পদ্ধতির বাস্তবায়নের দিকে তাকাই কারণ এটি Go-তে প্রয়োগ করা পদ্ধতির সাথে খুব মিল। কিন্তু স্কিমা পরীক্ষা করার আগে, আমাদের হ্যাশ মানচিত্র দেখতে কেমন হবে তা দেখা যাক।

 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) কারণ আমরা প্রতিটি কী-এর জন্য একটি লিঙ্কযুক্ত তালিকা সত্তা সংরক্ষণ করি।

Go এ মানচিত্র

একটি হ্যাশ মানচিত্র বাস্তবায়নের তত্ত্ব সম্পর্কে জ্ঞানের সাথে সজ্জিত, আসুন আমরা দেখি যে Go প্রোগ্রামিং ভাষা আমাদের জন্য কী ধরনের বিল্ট-ইন মানচিত্র সরবরাহ করে। Go এ একটি মানচিত্র তৈরি করার বিভিন্ন উপায় রয়েছে:

 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. }

Go বিল্ট-ইন ম্যাপ টাইপ একটি সহযোগী অ্যারের জন্য প্রয়োজনীয় তিনটি ক্রিয়াকলাপ এবং মানচিত্র আইটেমগুলির উপর পুনরাবৃত্তি করার জন্য অতিরিক্ত বৈশিষ্ট্যগুলিও প্রয়োগ করে:

 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) } }

তুলনীয় যেকোন প্রকার Go মানচিত্রে একটি কী হতে পারে। তুলনীয় প্রকারের মধ্যে বুলিয়ান, নিউমেরিক, স্ট্রিং, পয়েন্টার, চ্যানেল এবং ইন্টারফেসের প্রকারগুলি, সেইসাথে স্ট্রাক্ট বা অ্যারেগুলি অন্তর্ভুক্ত যা শুধুমাত্র তুলনামূলক প্রকারগুলি ধারণ করে। এছাড়াও, মানচিত্রের মান হিসাবে ব্যবহার করা যেতে পারে এমন ধরণের উপর কার্যত কোন বিধিনিষেধ নেই। এগুলি পূর্ণসংখ্যা এবং স্ট্রিংগুলির মতো সাধারণ ধরণের থেকে শুরু করে জটিল ধরণের যেমন স্লাইস, অন্যান্য মানচিত্র বা এমনকি ফাংশন পর্যন্ত হতে পারে।

Go Maps-এ গভীরভাবে ডুব দিন

এখন আমরা মানচিত্রের উৎস কোড অন্বেষণ করে মানচিত্রের বাস্তবায়ন পরীক্ষা করব। এটি আমাদের আরও ভালভাবে বুঝতে সাহায্য করবে কিভাবে মানচিত্রগুলি অভ্যন্তরীণভাবে প্রয়োগ করা হয়। Go এর মানচিত্রের উত্স কোডটি এখানে পাওয়া যাবে।

গো-তে একটি মানচিত্র হল আগে আলোচিত হ্যাশ মানচিত্রের একটি বাস্তবায়ন। আমাদের পূর্ববর্তী উদাহরণে, আমরা সংঘর্ষের রেজোলিউশনের জন্য একটি লিঙ্কযুক্ত তালিকা ব্যবহার করেছি। Go একটি ভিন্ন পদ্ধতি ব্যবহার করে; লিঙ্কযুক্ত তালিকার পরিবর্তে, প্রতিটি অন্তর্নিহিত অ্যারে সূচকে বালতি - অন্যান্য সাব্যারে রয়েছে। তাই মূলত, অন্তর্নিহিত অ্যারে একটি দ্বি-মাত্রিক সাব্যারে। প্রতিটি বালতিতে 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 হল অ্যারে যেখানে আমরা মানচিত্রের আকার পরিবর্তন করার আগে আইটেমগুলি সংরক্ষণ করি৷ আকার পরিবর্তন করার সময় মানচিত্রের আইটেমগুলি সরানোর পরিবর্তে, Go ধীরে ধীরে এটি করে। buckets এবং oldbuckets হল পয়েন্টার যা bmap স্ট্রাকটকে নির্দেশ করে, যা tophash সঞ্চয় করে - বালতিতে সংরক্ষিত প্রতিটি কী-এর জন্য হ্যাশের প্রথম বাইটের একটি অ্যারে - এর পরে MapBucketCount কী এবং MapBucketCount মান, শেষে একটি ওভারফ্লো পয়েন্টার সহ। MapBucketCount একটি আর্কিটেকচার-নির্দিষ্ট মান, ডকুমেন্টেশন অনুযায়ী 8 এর বেশি নয়। মেমরিতে একটি মানচিত্র কেমন দেখায় তা আরও ভালভাবে বোঝার জন্য, এখানে একটি ছবি রয়েছে।

একটি কী-এর সাথে যুক্ত মান খুঁজে বের করার জন্য, আমাদের প্রথমে হ্যাশ গণনা করতে হবে, যা আমরা বালতিটি নির্ধারণ করতে ব্যবহার করব যেখানে আমাদের কী অবস্থিত। এর জন্য, গো আর্কিটেকচার এবং যে ধরণের হ্যাশ করা দরকার তার উপর নির্ভর করে বিভিন্ন হ্যাশ ফাংশন ব্যবহার করে। হ্যাশ গণনা করার পরে, আমাদের কীটি কোথায় অবস্থিত হতে পারে তা সূচকটি গণনা করতে Go বেশ কয়েকটি শেষ বিট ব্যবহার করে। Go টফ্যাশ অ্যারেতে হ্যাশের প্রথম বাইটও সঞ্চয় করে এবং কী-এর হ্যাশ ব্যবহার করে, আপনি সহজেই tophash ব্যবহার করে বালতিতে সম্ভাব্য কী সূচকটি সনাক্ত করতে পারেন। এর পরে, আমাদের অনুসন্ধান করা কীটিকে বালতিতে সংরক্ষিত কীটির সাথে তুলনা করতে হবে কারণ হ্যাশের প্রথম বাইটের মধ্যে সংঘর্ষও হতে পারে। এই প্রক্রিয়াটি ছবিতে উপস্থাপন করা হয়েছে।

সঙ্গতি: মানচিত্র বনাম সিঙ্ক.ম্যাপ

সমবর্তী মানচিত্র

আমরা একটি মানচিত্রের অভ্যন্তরীণ বাস্তবায়ন বিবেচনা করেছি, তবে Go হল একটি ভাষা যা অত্যন্ত সমসাময়িক কোড বিকাশের জন্য ডিজাইন করা হয়েছে। যেখানে দুই বা ততোধিক গোরুটিন একই সাথে মানচিত্রে ক্রিয়াকলাপ সম্পাদন করে এমন ক্ষেত্রে আমরা কীভাবে একটি মানচিত্রের সাথে কাজ করব? আসুন দুটি ক্ষেত্রে বিবেচনা করা যাক: দুটি গোরুটিন একই সাথে চলমান একটি পূর্বের আরম্ভ করা মানচিত্র থেকে কিছু মান পড়ে এবং যখন গরউটিনগুলি লেখার ক্রিয়াকলাপ সম্পাদন করে।

একটি ভাগ করা মানচিত্র থেকে কিছু মান পড়ার জন্য দুটি গোরুটিন একসাথে চলার ক্ষেত্রে, আমরা সমস্যার সম্মুখীন হই না কারণ পঠিত ক্রিয়াকলাপের সময় আমাদের মানচিত্রের অভ্যন্তরীণ অবস্থা পরিবর্তিত হয় না। অতএব, আমরা নিরাপদে একসাথে পড়তে পারি।

 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() }

অন্যদিকে, যখন আমরা সমসাময়িক লেখাগুলি সম্পাদন করি, তখন মানচিত্রটি লেখার ক্রিয়াকলাপের সময় অবস্থা পরিবর্তন করতে পারে। যেমনটি আমরা ইতিমধ্যে পূর্ববর্তী বিভাগে পরীক্ষা করেছি, লেখার ক্রিয়াকলাপটি পারমাণবিক নয়। এর মানে হল যে মানচিত্র পরিবর্তনের ধাপগুলির মধ্যে অন্যান্য ক্রিয়াকলাপ হতে পারে, এবং যদি আমরা অন্য লেখার প্রক্রিয়া চলাকালীন পড়তে বা লেখার চেষ্টা করি, আমরা একটি ভুল অবস্থায় একটি মানচিত্রের মুখোমুখি হতে পারি। আপনি যদি একটি মানচিত্রে সমসাময়িক লেখাগুলি সম্পাদন করার চেষ্টা করেন এবং একটি fatal error: concurrent map writes ।

এই সমস্যাটি পরিচালনা করতে, আমাদের একটি Mutex ব্যবহার করতে হবে। একটি মিউটেক্স হল একটি সিঙ্ক্রোনাইজেশন আদিম যা রাজ্যকে একবারে একাধিক থ্রেড এক্সিকিউশন দ্বারা পরিবর্তন করা বা অ্যাক্সেস করা থেকে বাধা দেয়। এটি দুটি অপারেশন সমর্থন করে, লক এবং আনলক, যা পারমাণবিকভাবে কার্যকর করা হয় এবং তাই নিরাপদ। প্রকৃতপক্ষে, আমরা 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। কিন্তু কখন আমাদের সিঙ্ক. ম্যাপ বা মিউটেক্সের সাথে একটি মানচিত্র ব্যবহার করা উচিত? এটা খুঁজে বের করার সময়. ডকুমেন্টেশন অনুযায়ী, মানচিত্রের ধরন দুটি সাধারণ ব্যবহারের ক্ষেত্রে অপ্টিমাইজ করা হয়েছে:

1. যখন একটি প্রদত্ত কী-র জন্য এন্ট্রি শুধুমাত্র একবার লেখা হয় কিন্তু অনেকবার পড়া হয়, যেমন ক্যাশে শুধুমাত্র বৃদ্ধি পায়

2. যখন একাধিক গোরুটিন কীগুলির সংযোগ বিচ্ছিন্ন করার জন্য এন্ট্রিগুলিকে পড়তে, লিখতে এবং ওভাররাইট করে। এই দুটি ক্ষেত্রে, একটি মানচিত্রের ব্যবহার একটি পৃথক Mutex বা RWMutex এর সাথে যুক্ত একটি Go মানচিত্রের তুলনায় উল্লেখযোগ্যভাবে লক বিরোধ কমাতে পারে।

   
   

কেন sync.Map এই ক্ষেত্রে Mutex-এর সাথে একটি মানচিত্রের চেয়ে ভালভাবে কাজ করে তা বোঝার জন্য এবং একটি অনুভূতি তৈরি করতে, আমাদের 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 জন্য প্রাথমিক ডেটা স্টোর এবং সমসাময়িক পঠন অ্যাক্সেসের উদ্দেশ্যে। এটি একটি atomic.Pointer দ্বারা প্রতিনিধিত্ব করা হয়৷ একটি readOnly কাঠামোর দিকে নির্দেশ করে, যা মানচিত্রের স্ন্যাপশটের পরমাণু এবং লক-মুক্ত পাঠ নিশ্চিত করে৷ যখন একটি কী দেখা হয়, এটি প্রথমে read মানচিত্রটি পরীক্ষা করে। যদি চাবিটি খুঁজে না পাওয়া যায় এবং মানচিত্রটিকে amended হিসাবে চিহ্নিত করা হয় (ইঙ্গিত করে যে dirty মানচিত্রে নতুন কীগুলি এখনও read মানচিত্রে নেই), এটি একটি মিউটেক্স লক ( mu ) এর অধীনে dirty মানচিত্রটি পরীক্ষা করতে ফিরে আসে। নোংরা মানচিত্র ( dirty ): এই মানচিত্রটি পরিবর্তনের অধীনে এন্ট্রি সংরক্ষণ করে এবং read মানচিত্রে এখনও দৃশ্যমান নয় এমন নতুন এন্ট্রি। এই মানচিত্রে অ্যাক্সেসের জন্য একচেটিয়া অ্যাক্সেস নিশ্চিত করতে মিউটেক্স লক ধরে রাখা প্রয়োজন। একটি লেখার অপারেশনে, যদি কীটি read মানচিত্রে না থাকে বা আপডেট করার প্রয়োজন হয়, অপারেশনটি dirty মানচিত্রে এগিয়ে যায়। যদি dirty মানচিত্রটি nil হয় , তাহলে এটি আরম্ভ করা হয় read মানচিত্রের একটি অগভীর অনুলিপি তৈরি করে, এন্ট্রিগুলি বাদ দিয়ে আর বৈধ নয়৷ একটি নির্দিষ্ট থ্রেশহোল্ড "মিস" করার পরে (ব্যর্থ লুকআপ যা dirty মানচিত্রে ফিরে আসার প্রয়োজন ছিল), dirty মানচিত্রটিকে নতুন read মানচিত্র হিসাবে উন্নীত করা হয় এবং প্রয়োজনে একটি নতুন dirty মানচিত্র প্রস্তুত করা হয়।

Mutex এর সাথে একটি বিল্ট-ইন গো ম্যাপ থেকে পার্থক্য

এখন আমরা একটি Mutex এবং sync.Map সহ একটি অন্তর্নির্মিত মানচিত্রের মধ্যে পার্থক্য কী তা বের করতে পারি:

1. লক কনটেন্ট :
   • sync.Map : লক বিরোধ কমানোর জন্য ডিজাইন করা হয়েছে। বেশিরভাগ রিড অপারেশনের জন্য, পারমাণবিক read পয়েন্টারের কারণে কোনো লকের প্রয়োজন হয় না। মানচিত্রের শুধুমাত্র একটি ছোট অংশকে প্রভাবিত করে এমন লেখা এবং মুছে ফেলাগুলিও লকের সময়কাল কমিয়ে দেয় কারণ তারা শুধুমাত্র dirty মানচিত্রটিকে লক করে।
   • Mutex-এর সাথে অন্তর্নির্মিত মানচিত্র : প্রতিটি অ্যাক্সেস (পড়ুন বা লিখুন) মিউটেক্স অর্জন করতে হবে, যা উচ্চ-সঙ্গতিপূর্ণ পরিস্থিতিতে একটি বাধা হয়ে উঠতে পারে।
2. মেমরি ওভারহেড এবং জটিলতা :
   • sync.Map : মানচিত্রের দুটি সংস্করণ বজায় রাখে এবং আরও মেমরি-নিবিড় হতে পারে। এই সংস্করণগুলি পরিচালনা করার যুক্তি জটিলতা যোগ করে।
   • Mutex-এর সাথে অন্তর্নির্মিত মানচিত্র : sync.Map তুলনায় সহজ এবং কম মেমরি ব্যবহার করে। ম্যাপের শুধুমাত্র একটি সংস্করণ বজায় রাখে।
3. কেস নির্দিষ্টতা ব্যবহার করুন :
   • sync.Map : ব্যবহারের ক্ষেত্রে অপ্টিমাইজ করা হয়েছে যেখানে কীগুলি বেশিরভাগই পড়া হয় এবং ঘন ঘন আপডেট করা হয় না বা যেখানে অনেকগুলি ক্রিয়াকলাপ কীগুলির বিচ্ছিন্ন সেটগুলিতে ঘটে।
   • Mutex-এর সাথে অন্তর্নির্মিত মানচিত্র : সাধারণ-উদ্দেশ্য, ব্যবহার করা সহজ কিন্তু সার্বজনীন লক বিরোধের কারণে নির্দিষ্ট উচ্চ-সামরিক পরিস্থিতির অধীনে ভাল কাজ নাও করতে পারে।

সংক্ষেপে, sync.Map এমন পরিস্থিতির জন্য বিশেষায়িত যা লক কনটেন্টেশন কমাতে, বর্ধিত জটিলতা এবং মেমরি ব্যবহারের খরচে এর একযোগে অপ্টিমাইজেশানের সুবিধা নিতে পারে। বিপরীতে, একটি মিউটেক্স সহ একটি স্ট্যান্ডার্ড গো মানচিত্র একটি সহজ এবং আরও সাধারণ সমাধান কিন্তু অত্যন্ত সমসাময়িক পরিবেশে কর্মক্ষমতা সমস্যায় ভুগতে পারে।

মোড়ক উম্মচন

এই প্রবন্ধ জুড়ে, আমরা মানচিত্র ডেটা স্ট্রাকচার ব্যবহারের জটিলতাগুলি অন্বেষণ করেছি, বিশেষ করে Go প্রোগ্রামিং ভাষায় তাদের বাস্তবায়ন এবং ব্যবহারের উপর ফোকাস করে। একটি অ্যাসোসিয়েটিভ অ্যারের প্রাথমিক ধারণা দিয়ে শুরু করে, আমরা হ্যাশ মানচিত্রের মেকানিক্সের দিকে ঝাঁপিয়ে পড়েছি, তাদের অপারেশনাল পদ্ধতি, সময় এবং স্থান জটিলতা এবং সংঘর্ষগুলি পরিচালনা করার জন্য পৃথক চেইনিং এবং খোলা ঠিকানার মতো বিভিন্ন পদ্ধতি নিয়ে আলোচনা করেছি।

Go এর রাজ্যে, আমরা hmap এবং bmap এর মতো অন্তর্নিহিত কাঠামো পরীক্ষা করে কীভাবে মানচিত্রগুলিকে ভাষাতে ব্যবহার এবং তৈরি করা হয় তা তদন্ত করেছি। এই অন্বেষণে ব্যবহারিক কোডের উদাহরণ অন্তর্ভুক্ত করা হয়েছে, যা প্রদর্শন করে যে কীভাবে গো অ্যাপ্লিকেশনগুলিতে মানচিত্রগুলি শুরু করা যায়, ম্যানিপুলেট করা যায় এবং কার্যকরভাবে নিয়োগ করা যায়। অতিরিক্তভাবে, আমরা মানচিত্র ব্যবহার করার সময় একযোগে সম্ভাব্য অসুবিধাগুলি হাইলাইট করেছি এবং সমসাময়িক অ্যাক্সেসের প্রয়োজনের পরিস্থিতিগুলির জন্য sync.Map প্রবর্তন করেছি, যা লক বিরোধ কমায় এবং কর্মক্ষমতা অপ্টিমাইজ করে৷

মানচিত্র ডেটা স্ট্রাকচারের এই দিকগুলি বোঝা শুধুমাত্র আপনার কোডিং টুলকিটকে উন্নত করে না বরং আরও দক্ষতা এবং আত্মবিশ্বাসের সাথে সাধারণ প্রোগ্রামিং চ্যালেঞ্জ মোকাবেলা করার জন্য আপনাকে প্রস্তুত করে। আপনি সাধারণ অ্যাপ্লিকেশন বা জটিল সিস্টেমগুলি বিকাশ করছেন যা সমকালীন পরিবেশে সর্বোত্তম কর্মক্ষমতা প্রয়োজন, কীভাবে এবং কখন বিভিন্ন ধরণের মানচিত্র ব্যবহার করতে হবে তার জ্ঞান অমূল্য। আপনি আপনার প্রোগ্রামিং দক্ষতা তৈরি করা চালিয়ে যাওয়ার সাথে সাথে আপনার প্রকল্পগুলিতে তাদের সম্ভাবনাকে পুরোপুরি কাজে লাগাতে এই কাঠামোগুলি এবং তাদের বিভিন্ন বাস্তবায়নের সাথে পরীক্ষা চালিয়ে যান।