Làm chủ bản đồ trong Go: Mọi thứ bạn cần biết

Bản đồ (còn được gọi là mảng kết hợp, bảng băm, bản đồ băm, bộ băm, dict) là cấu trúc dữ liệu thiết yếu để giải quyết các vấn đề thuật toán khác nhau trong công việc hàng ngày, trong các cuộc thi lập trình hoặc trong các cuộc phỏng vấn xin việc. Do đó, điều cần thiết là phải hiểu những tính năng mà bản đồ cung cấp cho bạn với tư cách là nhà phát triển: các hoạt động được chúng hỗ trợ, độ phức tạp về thời gian và không gian của các hoạt động khác nhau và cách sử dụng cấu trúc này trong mã. Sử dụng kiến thức này và một số kinh nghiệm thực tế, bạn sẽ có thể phát hiện các trường hợp cần áp dụng bản đồ để giải quyết vấn đề của mình. Bài viết bạn đang đọc cung cấp hướng dẫn toàn diện về cách sử dụng bản đồ. Chúng ta sẽ bắt đầu với phần tổng quan ngắn gọn về cấu trúc dữ liệu bản đồ nói chung, sau đó đi sâu vào việc triển khai bản đồ bằng ngôn ngữ lập trình Go và thảo luận về các chiến lược sử dụng bản đồ trong mã đồng thời.

Bản đồ cho người mới bắt đầu

Mảng kết hợp

Hãy bắt đầu bằng cách thảo luận về một khái niệm quan trọng đằng sau tất cả các cấu trúc dữ liệu được triển khai bằng các ngôn ngữ lập trình khác nhau: kiểu dữ liệu trừu tượng. Đây là mô hình toán học được sử dụng để mô tả một kiểu dữ liệu về các hoạt động được hỗ trợ bởi kiểu dữ liệu, hành vi của các hoạt động này và các giá trị có thể được truyền đến hoặc nhận từ chúng. Ngoài ra còn có một kiểu dữ liệu trừu tượng cho bản đồ, được gọi là mảng kết hợp.

Mảng kết hợp là một kiểu dữ liệu trừu tượng được sử dụng để lưu trữ một tập hợp các cặp khóa và giá trị theo cách mà mỗi khóa chỉ xuất hiện một lần trong bộ sưu tập, hay nói cách khác, chỉ có một giá trị cho mỗi khóa trong bộ sưu tập . Nó hỗ trợ các hoạt động get , set và delete .

Hãy tưởng tượng rằng chúng ta triển khai một mảng kết hợp có thể lưu trữ các cặp khóa và giá trị, trong đó cả khóa và giá trị đều là chuỗi, trong ngôn ngữ lập trình Go và xem các thao tác trông như thế nào.

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

Đặt khóa đã được đặt trước đó là thao tác hợp lệ, nhưng trong trường hợp này, giá trị mới sẽ được liên kết với khóa cũ và sẽ không thể truy xuất giá trị trước đó. Nó có thể bị xóa hoặc bị che khuất, tùy thuộc vào việc triển khai mảng kết hợp.

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

Điều đó thật tuyệt, nhưng bạn có thể hỏi cách triển khai mảng kết hợp trong cuộc sống thực. Trên thực tế, không có giới hạn nào cho việc thực hiện. Bạn có thể triển khai nó theo bất kỳ cách nào bạn có thể tưởng tượng; bạn chỉ cần hỗ trợ các thao tác cần thiết cho kiểu dữ liệu trừu tượng này. Tuy nhiên, có một số cách tiếp cận phổ biến nhất: bản đồ băm và cây tìm kiếm nhị phân. Sự khác biệt giữa chúng nằm ở độ phức tạp về thời gian và không gian, cũng như các thuật toán lưu trữ và truy xuất khóa và giá trị. Trong tương lai, chúng tôi sẽ tập trung vào việc triển khai bản đồ băm, nhưng cần lưu ý rằng cây tìm kiếm nhị phân cũng có thể được sử dụng để triển khai mảng kết hợp.

Bản đồ băm

Chúng tôi phát hiện ra rằng bản đồ băm là cấu trúc dữ liệu thực hiện các hoạt động mảng kết hợp: đặt giá trị cho khóa, truy xuất giá trị theo khóa và xóa giá trị được liên kết với khóa. Nhưng bản đồ băm thực sự hoạt động như thế nào? Hãy cùng tìm hiểu.

Ý tưởng cốt lõi ở đây được ẩn sau từ "băm". Bản đồ băm sử dụng hàm băm để tính chỉ mục của vị trí trong mảng nơi giá trị sẽ được lưu trữ bằng cách chuyển khóa cho hàm băm. Hãy thử triển khai một bản đồ băm đơn giản bằng ngôn ngữ lập trình Go để xem hàm băm và mảng hoạt động cùng nhau như thế nào để xây dựng một bản đồ băm.

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

Đó thực sự là một cách đơn giản hóa cách hoạt động của bản đồ băm thực sự. Bạn có thể nhận thấy rằng việc triển khai của chúng tôi có thể gặp trục trặc trong một số trường hợp. Nếu bạn không để ý, hãy dành chút thời gian để suy nghĩ về các vấn đề tiềm ẩn trước khi tiếp tục đọc.

Sự va chạm

Bạn có tìm ra được vấn đề trong quá trình triển khai trước đó không? Đó là tình huống hai chuỗi khác nhau có thể mang lại cùng một hàm băm. Chính xác, chúng ta chỉ có các giá trị băm len(array) có thể có nhưng vô số khóa khác nhau và theo nguyên tắc chuồng bồ câu , chúng ta có thể tìm thấy hai khóa khác nhau sẽ tạo ra cùng một hàm băm và điều này có nghĩa là chúng sẽ tương ứng với cùng một vị trí trong mảng.

Chúng ta sẽ làm gì với nó? Chúng ta cần tìm cách nào đó để giải quyết tình trạng này. May mắn thay, những người thông minh đã giải quyết được vấn đề này và thực hiện một số giải pháp nổi tiếng, vì vậy chúng ta hãy sử dụng chúng thay vì phát minh lại cái bánh xe.

• Chuỗi riêng biệt.

  Theo cách tiếp cận này, thay vì lưu trữ các giá trị trực tiếp trong mảng, chúng ta sẽ lưu trữ một danh sách liên kết trong mảng cho mỗi chỉ mục. Khi chúng tôi thêm một giá trị mới vào bản đồ, trước tiên chúng tôi sẽ tìm kiếm xem có mục nào có cùng khóa không. Nếu có thì chỉ cần cập nhật giá trị; nếu không, hãy thêm một mục mới vào danh sách liên kết.

  
  

• Địa chỉ mở

  Địa chỉ mở là một cách tiếp cận khác để giải quyết xung đột. Bây giờ chúng ta sẽ lưu trữ một cặp khóa và giá trị ở mỗi vị trí mảng. Nếu chúng tôi cố gắng thêm một giá trị mới và gặp phải tình huống đã có giá trị ở vị trí này, chúng tôi sẽ bắt đầu sử dụng tính năng thăm dò. Việc thăm dò có thể là tuyến tính, bậc hai, bằng cách sử dụng hàm băm khác hoặc thậm chí ngẫu nhiên. Trong thăm dò tuyến tính, bạn bắt đầu tăng chỉ số lên một cho đến khi tìm thấy không gian trống trong mảng cơ bản của mình. Quá trình tương tự xảy ra khi bạn cố gắng truy xuất một giá trị từ mảng và gặp phải tình huống khóa ở vị trí mảng không tương ứng với khóa tìm kiếm.

Hãy xem xét việc triển khai phương pháp chuỗi riêng biệt vì nó rất giống với phương pháp được triển khai trong Go. Nhưng trước khi kiểm tra lược đồ, hãy xem bản đồ băm của chúng ta sẽ trông như thế nào.

 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

Độ phức tạp

Đây có thể là một chủ đề nâng cao dành cho những người không quen với khái niệm độ phức tạp của thuật toán. Nếu bạn nhận ra chính mình trong phần mô tả này, hãy theo liên kết này và tìm hiểu về khái niệm này.

Độ phức tạp về thời gian và không gian thực sự quan trọng khi chúng ta suy luận về các thuật toán và cấu trúc dữ liệu vì chúng ảnh hưởng trực tiếp đến hiệu suất mã của chúng ta. Hãy thử tìm hiểu mức độ phức tạp của việc triển khai được cung cấp trong chương trước.

Để thêm một cặp khóa-giá trị mới vào bản đồ băm, chúng ta cần tính toán hàm băm, tìm danh sách được liên kết nằm ở chỉ mục và chuyển qua danh sách được liên kết để tìm khóa của chúng ta. Điều đầu tiên có thể ảnh hưởng đến độ phức tạp về thời gian là kích thước khóa; chúng tôi giả định rằng kích thước khóa trung bình là nhỏ và độ phức tạp về thời gian của hàm băm phụ thuộc tuyến tính vào kích thước khóa. Trong trường hợp này, chúng ta có thể giả sử rằng độ phức tạp về thời gian trung bình để tính toán hàm băm khóa là O(1) . Tiếp theo, chúng ta cần duyệt qua tất cả các mục trong danh sách liên kết. Số lượng mục phụ thuộc vào số lượng xung đột xảy ra và trong trường hợp xấu nhất, nó sẽ là O(n) khi tất cả các mục tương ứng với cùng một hàm băm. Vì vậy, tổng độ phức tạp về thời gian cho thao tác thêm là O(1) + O(n) = O(n) cả tệ nhất và trung bình.

Chúng ta có thể giảm độ phức tạp về thời gian trung bình bằng cách triển khai thay đổi kích thước của mảng cơ bản dựa trên phương pháp phỏng đoán được gọi là hệ số tải. Nó chỉ đơn giản là số lượng khóa trong bản đồ băm chia cho số vị trí trong mảng bên dưới. Nếu giá trị này vượt quá một ngưỡng nhất định, chúng ta có thể thay đổi kích thước mảng cơ bản và sao chép tất cả các giá trị sang mảng mới. Sau đó, mọi danh sách liên kết sẽ bị giới hạn kích thước trung bình. Trong trường hợp này, chúng ta có thể tìm giá trị hệ số tải sao cho độ phức tạp thời gian trung bình sẽ là O(1) trong hầu hết các trường hợp. Chúng ta sẽ không đi vào tính toán ở đây, nhưng điều quan trọng là phải hiểu điều đó.

Do đó, bản đồ băm cung cấp các ràng buộc về độ phức tạp về thời gian và không gian sau đây:

Độ phức tạp về thời gian: trung bình là O(1) cho tất cả các hoạt động.

Độ phức tạp về không gian: O(n) vì chúng tôi lưu trữ một thực thể danh sách liên kết cho mỗi khóa.

Bản đồ trong Go

Được trang bị kiến thức về lý thuyết triển khai bản đồ băm, chúng ta hãy xem loại bản đồ tích hợp sẵn mà ngôn ngữ lập trình Go cung cấp cho chúng ta. Có một số cách để tạo bản đồ trong 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. }

Loại bản đồ tích hợp sẵn của Go cũng thực hiện cả ba thao tác được yêu cầu bởi một mảng kết hợp và tính năng bổ sung để lặp lại các mục bản đồ:

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

Bất kỳ loại nào có thể so sánh được đều có thể là chìa khóa trong bản đồ cờ vây. Các loại có thể so sánh bao gồm các loại boolean, số, chuỗi, con trỏ, kênh và giao diện, cũng như các cấu trúc hoặc mảng chỉ chứa các loại có thể so sánh được. Ngoài ra, hầu như không có hạn chế nào đối với các loại có thể được sử dụng làm giá trị trong bản đồ. Chúng có thể là bất cứ thứ gì từ các kiểu đơn giản như số nguyên và chuỗi đến các kiểu phức tạp như lát cắt, bản đồ khác hoặc thậm chí là các hàm.

Đi sâu vào Bản đồ cờ vây

Bây giờ chúng ta sẽ kiểm tra việc triển khai bản đồ bằng cách khám phá mã nguồn bản đồ. Điều này sẽ giúp chúng tôi hiểu rõ hơn về cách triển khai bản đồ trong nội bộ. Mã nguồn cho bản đồ của Go có thể được tìm thấy ở đây .

Bản đồ trong Go là cách triển khai bản đồ băm đã thảo luận trước đó. Trong ví dụ trước, chúng tôi đã sử dụng danh sách liên kết để giải quyết xung đột. Go sử dụng một cách tiếp cận khác; thay vì danh sách liên kết, có các nhóm - các mảng con khác tại mỗi chỉ mục mảng cơ bản. Vì vậy, về cơ bản, mảng cơ bản là mảng con hai chiều. Mỗi nhóm chứa tối đa 8 cặp khóa-giá trị. Nếu có nhiều hơn 8 phím được băm vào một nhóm, chúng tôi sẽ xâu chuỗi các nhóm bổ sung để thoát khỏi một nhóm - tràn. Các bit bậc thấp của hàm băm được sử dụng để chọn một nhóm. Mỗi nhóm chứa một vài bit bậc cao của mỗi hàm băm để phân biệt các mục trong một nhóm. Khi bản đồ phát triển, chúng tôi phân bổ một mảng nhóm mới lớn gấp đôi. Các nhóm được sao chép dần dần từ mảng nhóm cũ sang mảng nhóm mới.

Các cấu trúc chính biểu diễn bản đồ được gọi là hmap và bmap . Chúng tôi bỏ qua một số trường trợ giúp trong cấu trúc để đơn giản. Việc hiểu ý tưởng của thuật toán không quan trọng:

 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 là số lượng vật phẩm hiện được lưu trữ trên bản đồ. buckets là mảng cơ bản nơi chúng tôi lưu trữ các mục mới và oldbuckets là mảng nơi chúng tôi lưu trữ các mục trước khi bản đồ được thay đổi kích thước. Thay vì di chuyển các mục bản đồ tại thời điểm thay đổi kích thước, Go thực hiện việc đó dần dần. buckets và oldbuckets là các con trỏ trỏ đến cấu trúc bmap , lưu trữ tophash - một mảng byte băm đầu tiên cho mỗi khóa được lưu trữ trong nhóm - theo sau là các khóa MapBucketCount và các giá trị MapBucketCount , với một con trỏ tràn ở cuối. MapBucketCount là giá trị dành riêng cho kiến trúc, không quá 8 theo tài liệu. Để hiểu rõ hơn về bản đồ trông như thế nào trong bộ nhớ, đây là một bức ảnh.

Để tìm giá trị được liên kết với một khóa, trước tiên chúng ta cần tính toán hàm băm mà chúng ta sẽ sử dụng để xác định nhóm chứa khóa của chúng ta. Để làm điều này, Go sử dụng các hàm băm khác nhau tùy thuộc vào kiến trúc và loại cần băm. Sau khi tính toán hàm băm, Go sử dụng một số bit cuối cùng để tính chỉ mục nơi có thể đặt khóa của chúng tôi. Go cũng lưu trữ byte đầu tiên của hàm băm trong mảng tophash và bằng cách sử dụng hàm băm của khóa, bạn có thể dễ dàng xác định chỉ mục khóa có thể có trong nhóm bằng cách sử dụng tophash . Sau đó, chúng ta cũng cần so sánh khóa được tìm kiếm với khóa được lưu trong nhóm vì cũng có thể xảy ra xung đột giữa byte đầu tiên của hàm băm. Quá trình này được thể hiện trong hình ảnh.

Đồng thời: Bản đồ so với đồng bộ hóa.Map

Bản đồ đồng thời

Chúng tôi đã xem xét việc triển khai bản đồ nội bộ, nhưng Go là ngôn ngữ được thiết kế để phát triển mã có tính đồng thời cao. Chúng ta sẽ làm việc với bản đồ như thế nào trong trường hợp hai hoặc nhiều goroutines đồng thời thực hiện các thao tác trên bản đồ? Hãy xem xét hai trường hợp: hai goroutine chạy đồng thời đọc một số giá trị từ bản đồ được khởi tạo trước đó và khi goroutine thực hiện thao tác ghi.

Trong trường hợp hai goroutine chạy đồng thời để đọc một số giá trị từ bản đồ được chia sẻ, chúng tôi không gặp phải vấn đề gì vì trạng thái bên trong của bản đồ không thay đổi trong quá trình đọc. Vì vậy, chúng ta có thể đọc đồng thời một cách an toàn.

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

Mặt khác, khi chúng ta thực hiện ghi đồng thời, bản đồ có thể thay đổi trạng thái trong quá trình ghi. Như chúng ta đã xem xét ở phần trước, thao tác ghi không mang tính nguyên tử. Điều này có nghĩa là có thể có các thao tác khác giữa các bước sửa đổi bản đồ và nếu chúng ta cố đọc hoặc ghi trong một quá trình ghi khác, chúng ta có thể gặp phải bản đồ ở trạng thái không chính xác. Go đủ thông minh để phát hiện nếu bạn cố gắng thực hiện ghi đồng thời vào bản đồ và sẽ đưa ra một fatal error: concurrent map writes .

Để xử lý vấn đề này, chúng ta cần sử dụng Mutex. Mutex là một nguyên thủy đồng bộ hóa nhằm ngăn trạng thái bị sửa đổi hoặc truy cập bởi nhiều luồng thực thi cùng một lúc. Nó hỗ trợ hai thao tác, khóa và mở khóa, được thực thi nguyên tử và do đó an toàn. Trên thực tế, chúng ta có thể sử dụng RWMutex, cho phép khóa nhiều trình đọc nhưng chỉ một trình đọc ghi. Điều này có thể giúp chúng tôi tối ưu hóa hiệu suất trong trường hợp có nhiều lượt đọc. Hãy xem xét việc triển khai bản đồ an toàn đồng thời.

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

đồng bộ hóa.Map

Có thêm một cách triển khai bản đồ an toàn đồng thời trong gói tiêu chuẩn: sync.Map. Nhưng khi nào chúng ta nên sử dụng sync.Map hoặc bản đồ với Mutex? Đã đến lúc phải tìm ra nó. Theo tài liệu, loại Bản đồ được tối ưu hóa cho hai trường hợp sử dụng phổ biến:

1. Khi mục nhập của một khóa nhất định chỉ được ghi một lần nhưng được đọc nhiều lần, như trong bộ nhớ đệm chỉ tăng lên

2. Khi nhiều goroutine đọc, ghi và ghi đè các mục nhập cho các bộ khóa rời rạc. Trong hai trường hợp này, việc sử dụng Bản đồ có thể giảm đáng kể tình trạng tranh chấp khóa so với bản đồ Go được ghép nối với Mutex hoặc RWMutex riêng biệt.

   
   

Để hiểu rõ hơn và hình thành cảm giác tại sao sync.Map hoạt động tốt hơn trong những trường hợp này thay vì bản đồ với Mutex, chúng ta nên kiểm tra mã nguồn của 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 duy trì hai cách thể hiện dữ liệu bản đồ: read và dirty . Đọc bản đồ ( read ): Đây là kho lưu trữ dữ liệu chính cho Map và dành cho truy cập đọc đồng thời. Nó được biểu diễn bằng một atomic.Pointer trỏ tới cấu trúc readOnly , đảm bảo việc đọc ảnh chụp nhanh của bản đồ không bị khóa và nguyên tử. Khi một phím được tra cứu, đầu tiên nó sẽ kiểm tra bản đồ read . Nếu không tìm thấy khóa và bản đồ được đánh dấu là amended (cho biết rằng có các khóa mới trong bản đồ dirty chưa có trong bản đồ read ), nó sẽ quay lại kiểm tra bản đồ dirty dưới khóa mutex ( mu ). Bản đồ bẩn ( dirty ): Bản đồ này lưu trữ các mục đang được sửa đổi và các mục mới chưa hiển thị trên bản đồ read . Việc truy cập vào bản đồ này yêu cầu phải giữ khóa mutex để đảm bảo quyền truy cập độc quyền. Trong thao tác ghi, nếu khóa không có trong bản đồ read hoặc cần được cập nhật, thao tác sẽ tiếp tục trên bản đồ dirty . Nếu bản đồ dirty là nil , nó sẽ được khởi tạo bằng cách tạo một bản sao nông của bản đồ read , loại trừ các mục không còn hợp lệ. Sau một ngưỡng "lỡ" nhất định (tra cứu không thành công buộc phải quay lại bản đồ dirty ), bản đồ dirty sẽ được thăng hạng thành bản đồ read mới và bản đồ dirty mới sẽ được chuẩn bị nếu cần thiết.

Sự khác biệt so với Bản đồ đi tích hợp với Mutex

Bây giờ chúng ta có thể tìm ra sự khác biệt giữa bản đồ tích hợp với Mutex và sync.Map:

1. Khóa tranh chấp :
   • sync.Map : Được thiết kế để giảm thiểu tranh chấp khóa. Đối với hầu hết các thao tác đọc, không cần khóa vì con trỏ read nguyên tử. Việc ghi và xóa chỉ ảnh hưởng đến một phần nhỏ của bản đồ cũng giảm thiểu thời gian khóa vì chúng chỉ khóa bản đồ dirty .
   • Bản đồ tích hợp với Mutex : Mọi quyền truy cập (đọc hoặc ghi) đều yêu cầu phải có được mutex, điều này có thể trở thành nút cổ chai trong các tình huống có tính tương tranh cao.
2. Chi phí bộ nhớ và độ phức tạp :
   • sync.Map : Duy trì hai phiên bản của bản đồ và có thể tốn nhiều bộ nhớ hơn. Logic để quản lý các phiên bản này làm tăng thêm độ phức tạp.
   • Bản đồ tích hợp với Mutex : Đơn giản hơn và sử dụng ít bộ nhớ hơn so với sync.Map vì nó chỉ duy trì một phiên bản của bản đồ.
3. Tính đặc hiệu của trường hợp sử dụng :
   • sync.Map : Được tối ưu hóa cho các trường hợp sử dụng trong đó các khóa chủ yếu được đọc và không được cập nhật thường xuyên hoặc khi có nhiều thao tác xảy ra trên các bộ khóa rời rạc.
   • Bản đồ tích hợp với Mutex : Mục đích chung, dễ sử dụng nhưng có thể không hoạt động tốt trong các tình huống có tính đồng thời cao cụ thể do xung đột khóa chung.

Tóm lại, sync.Map chuyên dùng cho các tình huống có thể tận dụng tối ưu hóa đồng thời của nó để giảm xung đột khóa, với cái giá phải trả là độ phức tạp và mức sử dụng bộ nhớ tăng lên. Ngược lại, bản đồ Go tiêu chuẩn với mutex là một giải pháp đơn giản và tổng quát hơn nhưng có thể gặp phải các vấn đề về hiệu suất trong môi trường có tính đồng thời cao.

Kết thúc

Trong suốt bài viết này, chúng tôi đã khám phá sự phức tạp của việc sử dụng cấu trúc dữ liệu bản đồ, đặc biệt tập trung vào việc triển khai và sử dụng chúng trong ngôn ngữ lập trình Go. Bắt đầu với khái niệm cơ bản về mảng kết hợp, chúng tôi đã đi sâu vào cơ chế của bản đồ băm, thảo luận về quy trình hoạt động, độ phức tạp về thời gian và không gian cũng như các cách tiếp cận khác nhau như xâu chuỗi riêng biệt và địa chỉ mở để xử lý xung đột.

Trong lĩnh vực cờ vây, chúng tôi đã nghiên cứu cách sử dụng và tích hợp bản đồ vào ngôn ngữ, kiểm tra các cấu trúc cơ bản như hmap và bmap . Cuộc khám phá này bao gồm các ví dụ mã thực tế, trình bày cách khởi tạo, thao tác và sử dụng hiệu quả bản đồ trong các ứng dụng Go. Ngoài ra, chúng tôi đã nêu bật những cạm bẫy tiềm ẩn của tính đồng thời khi sử dụng bản đồ và giới thiệu sync.Map cho các trường hợp yêu cầu quyền truy cập đồng thời, giúp giảm xung đột khóa và tối ưu hóa hiệu suất.

Việc hiểu các khía cạnh này của cấu trúc dữ liệu bản đồ không chỉ nâng cao bộ công cụ mã hóa của bạn mà còn giúp bạn chuẩn bị để giải quyết các thách thức lập trình phổ biến với hiệu quả và sự tự tin cao hơn. Cho dù bạn đang phát triển các ứng dụng đơn giản hay các hệ thống phức tạp đòi hỏi hiệu suất tối ưu trong các môi trường đồng thời thì kiến thức về cách thức và thời điểm sử dụng các loại bản đồ khác nhau là vô giá. Khi bạn tiếp tục xây dựng kiến thức chuyên môn về lập trình của mình, hãy tiếp tục thử nghiệm các cấu trúc này và các cách triển khai khác nhau của chúng để khai thác tối đa tiềm năng của chúng trong các dự án của bạn.