Maîtriser les cartes en Go : tout ce que vous devez savoir

Une carte (également connue sous le nom de tableau associatif, table de hachage, carte de hachage, jeu de hachage, dict) est une structure de données essentielle pour résoudre différents problèmes algorithmiques au cours du travail quotidien, lors de concours de programmation ou lors d'entretiens d'embauche. Par conséquent, il est essentiel de comprendre quelles fonctionnalités les cartes vous offrent en tant que développeur : les opérations qu'elles prennent en charge, la complexité temporelle et spatiale des différentes opérations et comment utiliser cette structure dans le code. Grâce à ces connaissances et une certaine expérience pratique, vous serez en mesure de détecter les cas où vous devrez appliquer une carte pour résoudre votre problème. L'article que vous lisez actuellement fournit un guide complet sur l'utilisation des cartes. Nous commencerons par un bref aperçu de la structure des données cartographiques en général, puis approfondirons la mise en œuvre des cartes dans le langage de programmation Go et discuterons des stratégies d'utilisation des cartes dans du code concurrent.

Carte pour les débutants

Tableau associatif

Commençons par discuter d'un concept important qui se cache derrière toutes les structures de données implémentées dans divers langages de programmation : le type de données abstrait. Il s'agit d'un modèle mathématique utilisé pour décrire un type de données en termes d'opérations prises en charge par le type de données, du comportement de ces opérations et des valeurs possibles qui peuvent leur être transmises ou reçues. Il existe également un type de données abstrait pour une carte, appelé tableau associatif.

Un tableau associatif est un type de données abstrait utilisé pour stocker une collection de paires clé-valeur de telle manière que chaque clé n'apparaisse qu'une seule fois dans la collection, ou en d'autres termes, il n'y a qu'une seule valeur pour chaque clé dans la collection. . Il prend en charge les opérations get , set et delete .

Imaginons que nous ayons une implémentation d'un tableau associatif capable de stocker des paires clé et valeur, où clé et valeur sont des chaînes, dans le langage de programmation Go, et regardons à quoi ressemblent les opérations.

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

Définir une clé qui a déjà été définie est une opération valide, mais dans ce cas, une nouvelle valeur sera associée à l'ancienne clé et il sera impossible de récupérer la valeur précédente. Il peut être supprimé ou masqué, en fonction de l'implémentation du tableau associatif.

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

C'est très bien, mais vous vous demandez peut-être comment implémenter un tableau associatif dans la vraie vie. En fait, il n’y a pas de limites à la mise en œuvre. Vous pouvez le mettre en œuvre de toutes les manières imaginables ; il vous suffit de prendre en charge les opérations requises pour ce type de données abstrait. Cependant, il existe plusieurs approches les plus courantes : la carte de hachage et l'arbre de recherche binaire. Les différences entre eux résident dans leurs complexités temporelles et spatiales et, bien sûr, dans les algorithmes de stockage et de récupération des clés et des valeurs. À l'avenir, nous nous concentrerons sur les implémentations de cartes de hachage, mais il convient de noter qu'un arbre de recherche binaire peut également être utilisé pour implémenter un tableau associatif.

Carte de hachage

Nous avons découvert qu'une table de hachage est une structure de données qui implémente des opérations de tableau associatives : définir une valeur pour une clé, récupérer une valeur par clé et supprimer une valeur associée à une clé. Mais comment fonctionne réellement une carte de hachage sous le capot ? Découvrons-le.

L’idée centrale ici est cachée derrière le mot « hash ». Une carte de hachage utilise une fonction de hachage pour calculer l'index de l'endroit dans le tableau où la valeur sera stockée en passant la clé à la fonction de hachage. Essayons d'implémenter une simple carte de hachage à l'aide du langage de programmation Go pour voir comment la fonction de hachage et le tableau fonctionnent ensemble pour créer une carte de hachage.

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

Il s’agit en fait d’une manière simplifiée du fonctionnement d’une véritable carte de hachage. Vous remarquerez peut-être que notre implémentation peut être interrompue dans certains cas. Si vous ne l'avez pas remarqué, prenez un peu de temps pour réfléchir aux problèmes potentiels avant de continuer votre lecture.

Collisions

Avez-vous réussi à comprendre quel était le problème dans la mise en œuvre précédente ? C'est une situation où deux chaînes différentes peuvent produire le même hachage. Justement, nous n'avons que len(array) valeurs de hachage possibles mais un nombre infini de clés différentes, et par le principe du casier , nous pouvons trouver deux clés différentes qui généreront le même hachage, et cela signifie qu'elles correspondront à la même position dans le tableau.

Qu'allons-nous en faire ? Nous devons trouver un moyen de gérer cette situation. Heureusement, des personnes intelligentes ont déjà résolu ce problème et mis en œuvre plusieurs solutions bien connues, alors utilisons-les au lieu de réinventer la roue.

• Chaînage séparé.

  Dans cette approche, au lieu de stocker les valeurs directement dans le tableau, nous stockerons une liste chaînée dans le tableau pour chaque index. Lorsque nous ajoutons une nouvelle valeur à la carte, nous chercherons d’abord s’il existe un élément avec la même clé. Si tel est le cas, mettez simplement à jour la valeur ; sinon, ajoutez un nouvel élément à la liste chaînée.

  
  

• Adressage ouvert

  L'adressage ouvert est une autre approche de la résolution des collisions. Nous allons maintenant stocker une paire clé et valeur dans chaque position du tableau. Si nous essayons d'ajouter une nouvelle valeur et rencontrons une situation dans laquelle il existe déjà une valeur à cette position, nous commençons à utiliser le sondage. Le sondage peut être linéaire, quadratique, en utilisant une autre fonction de hachage, ou même aléatoire. En sondage linéaire, vous commencez à incrémenter l'index de un jusqu'à ce que vous trouviez de l'espace libre dans votre tableau sous-jacent. Le même processus se produit lorsque vous essayez de récupérer une valeur du tableau et que vous êtes confronté à une situation dans laquelle la clé dans la position du tableau ne correspond pas à la clé de recherche.

Examinons l'implémentation de l'approche de chaînage séparé car elle est très similaire à l'approche implémentée dans Go. Mais avant d’examiner le schéma, voyons à quoi ressemblera notre carte de hachage.

 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

Complexité

Cela pourrait être un sujet avancé pour les personnes non familiarisées avec le concept de complexité algorithmique. Si vous vous reconnaissez dans cette description, alors suivez ce lien et découvrez ce concept.

La complexité temporelle et spatiale est très importante lorsque nous raisonnons sur les algorithmes et les structures de données, car elles affectent directement les performances de notre code. Essayons de comprendre la complexité de l'implémentation proposée dans le chapitre précédent.

Pour ajouter une nouvelle paire clé-valeur à une carte de hachage, nous devons calculer le hachage, trouver la liste chaînée située à l'index et parcourir la liste chaînée pour trouver notre clé. La première chose qui peut affecter la complexité temporelle est la taille de la clé ; nous supposons que la taille moyenne de la clé est petite et que la complexité temporelle de la fonction de hachage dépend linéairement de la taille de la clé. Dans ce cas, nous pouvons supposer que la complexité temporelle moyenne pour calculer le hachage de clé est O(1) . Ensuite, nous devons parcourir tous les éléments de la liste chaînée. Le nombre d'éléments dépend du nombre de collisions qui se produisent et, dans le pire des cas, il sera O(n) lorsque tous les éléments correspondent au même hachage. Ainsi, la complexité temporelle totale de l'opération d'ajout est O(1) + O(n) = O(n) à la fois pire et moyenne.

Nous pouvons réduire la complexité temporelle moyenne en implémentant un redimensionnement du tableau sous-jacent basé sur une heuristique appelée facteur de charge. Il s'agit simplement du nombre de clés dans la carte de hachage divisé par le nombre d'emplacements dans le tableau sous-jacent. Si cette valeur dépasse un certain seuil, nous pourrions redimensionner le tableau sous-jacent et copier toutes les valeurs dans le nouveau tableau. Après cela, chaque liste chaînée sera en moyenne limitée en taille. Dans ce cas, nous pouvons trouver une valeur de facteur de charge de telle sorte que la complexité temporelle moyenne soit O(1) dans la plupart des cas. Nous n’entrerons pas dans le calcul ici, mais il est important de le comprendre.

Ainsi, la carte de hachage fournit les contraintes de complexité temporelle et spatiale suivantes :

Complexité temporelle : O(1) en moyenne pour toutes les opérations.

Complexité spatiale : O(n) car nous stockons une entité de liste chaînée pour chaque clé.

Carte dans Go

Armés de connaissances sur la théorie de la mise en œuvre d'une carte de hachage, examinons quel type de cartes intégré le langage de programmation Go nous fournit. Il existe plusieurs façons de créer une carte dans 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. }

Le type de carte intégré Go implémente également les trois opérations requises par un tableau associatif et une fonctionnalité supplémentaire pour itérer sur les éléments de la carte :

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

Tout type comparable peut être une clé dans les cartes Go. Les types comparables incluent les types booléens, numériques, chaînes, pointeurs, canaux et interfaces, ainsi que les structures ou les tableaux qui contiennent uniquement des types comparables. De plus, il n’existe pratiquement aucune restriction sur les types pouvant être utilisés comme valeurs dans une carte. Il peut s'agir de types simples comme des entiers et des chaînes, ou de types complexes comme des tranches, d'autres cartes ou même des fonctions.

Plongez en profondeur dans Go Maps

Nous allons maintenant examiner l’implémentation des cartes en explorant le code source des cartes. Cela nous aidera à mieux comprendre comment les cartes sont mises en œuvre en interne. Le code source de la carte de Go peut être trouvé ici .

Une carte dans Go est une implémentation de la carte de hachage évoquée précédemment. Dans notre exemple précédent, nous avons utilisé une liste chaînée pour la résolution des collisions. Go utilise une approche différente ; au lieu d'une liste chaînée, il existe des compartiments - d'autres sous-tableaux à chaque index de tableau sous-jacent. Donc, essentiellement, le tableau sous-jacent est un sous-tableau bidimensionnel. Chaque compartiment contient jusqu'à 8 paires clé-valeur. Si plus de 8 clés sont hachées dans un compartiment, nous enchaînons les compartiments supplémentaires pour en sortir un - le compartiment de débordement. Les bits de poids faible du hachage sont utilisés pour sélectionner un compartiment. Chaque compartiment contient quelques bits de poids fort de chaque hachage pour distinguer les entrées au sein d'un seul compartiment. Lorsque la carte s'agrandit, nous allouons un nouveau tableau de buckets deux fois plus grand. Les compartiments sont copiés de manière incrémentielle de l'ancien tableau de compartiments vers le nouveau tableau de compartiments.

Les principales structures représentant la carte sont appelées hmap et bmap . Nous ignorons certains champs d'assistance dans la structure pour plus de simplicité. Ils n'ont pas d'importance pour comprendre l'idée de l'algorithme :

 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 est le nombre d’éléments actuellement stockés sur la carte. buckets est le tableau sous-jacent dans lequel nous stockons les nouveaux éléments, et oldbuckets est le tableau dans lequel nous avons stocké les éléments avant le redimensionnement de la carte. Au lieu de déplacer les éléments de la carte au moment du redimensionnement, Go le fait progressivement. buckets et oldbuckets sont des pointeurs qui pointent vers la structure bmap , qui stocke tophash - un tableau du premier octet de hachage pour chaque clé stockée dans le bucket - suivi des clés MapBucketCount et des valeurs MapBucketCount , avec un pointeur de débordement à la fin. MapBucketCount est une valeur spécifique à l'architecture, pas plus de 8 selon la documentation. Pour mieux comprendre à quoi ressemble une carte en mémoire, voici une image.

Pour trouver la valeur associée à une clé, nous devons d’abord calculer le hachage, que nous utiliserons pour déterminer le bucket où se trouve notre clé. Pour cela, Go utilise différentes fonctions de hachage en fonction de l'architecture et du type à hacher. Après avoir calculé le hachage, Go utilise plusieurs derniers bits pour calculer l'index où pourrait se trouver notre clé. Go stocke également le premier octet du hachage dans le tableau tophash, et en utilisant le hachage de la clé, vous pouvez facilement localiser l'index de clé possible dans le compartiment en utilisant tophash . Après cela, nous devons également comparer la clé recherchée avec la clé stockée dans le bucket car il peut également y avoir des collisions entre le premier octet du hachage. Ce processus est représenté dans l'image.

Concurrence : carte contre sync.Map

Carte simultanée

Nous avons envisagé l'implémentation interne d'une carte, mais Go est un langage conçu pour développer du code hautement concurrent. Comment allons-nous travailler avec une carte dans les cas où deux ou plusieurs goroutines effectuent simultanément des opérations sur la carte ? Considérons deux cas : deux goroutines exécutées simultanément lisent certaines valeurs d'une carte précédemment initialisée, et lorsque les goroutines effectuent des opérations d'écriture.

Dans le cas de deux goroutines exécutées simultanément pour lire certaines valeurs d'une carte partagée, nous ne rencontrons pas de problèmes car notre état interne de la carte ne change pas pendant l'opération de lecture. Par conséquent, nous pouvons lire simultanément en toute sécurité.

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

D'un autre côté, lorsque nous effectuons des écritures simultanées, la carte peut changer d'état pendant l'opération d'écriture. Comme nous l'avons déjà examiné dans la section précédente, l'opération d'écriture n'est pas atomique. Cela signifie qu'il peut y avoir d'autres opérations entre les étapes de modification de la carte, et si nous essayons de lire ou d'écrire pendant un autre processus d'écriture, nous pouvons nous retrouver face à une carte dans un état incorrect. Go est suffisamment intelligent pour détecter si vous essayez d'effectuer des écritures simultanées sur une carte et générera une fatal error: concurrent map writes .

Pour résoudre ce problème, nous devons utiliser un Mutex. Un Mutex est une primitive de synchronisation qui empêche la modification ou l'accès à l'état par plusieurs threads d'exécution à la fois. Il prend en charge deux opérations, le verrouillage et le déverrouillage, qui sont exécutées de manière atomique et donc sécurisées. En effet, on peut utiliser RWMutex, qui permet le verrouillage en lecture par plusieurs lecteurs mais un seul en écriture. Cela peut nous aider à optimiser les performances dans les cas où il y a beaucoup de lectures. Examinons l'implémentation d'une carte simultanément sécurisée.

 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

Il existe une autre implémentation d'une carte simultanément sécurisée dans le package standard : sync.Map. Mais quand doit-on utiliser sync.Map ou une carte avec un Mutex ? Il est temps de le comprendre. Selon la documentation, le type Map est optimisé pour deux cas d'utilisation courants :

1. Lorsque l'entrée d'une clé donnée n'est écrite qu'une seule fois mais lue plusieurs fois, comme dans les caches qui ne font que croître

2. Lorsque plusieurs goroutines lisent, écrivent et écrasent des entrées pour des ensembles de clés disjoints. Dans ces deux cas, l'utilisation d'une carte peut réduire considérablement les conflits de verrouillage par rapport à une carte Go associée à un Mutex ou RWMutex distinct.

   
   

Pour mieux comprendre et comprendre pourquoi sync.Map fonctionne mieux dans ces cas plutôt qu'une carte avec Mutex, nous devrions examiner le code source de 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 conserve deux représentations des données cartographiques : read et dirty . Lire la carte ( read ) : il s'agit du magasin de données principal de la Map et est destiné à un accès en lecture simultané. Il est représenté par un atomic.Pointer vers une structure readOnly , garantissant des lectures atomiques et sans verrouillage de l'instantané de la carte. Lorsqu'une clé est recherchée, elle vérifie d'abord la carte read . Si la clé n'est pas trouvée et que la carte est marquée comme amended (indiquant qu'il y a de nouvelles clés dans la carte dirty pas encore dans la carte read ), il revient à vérifier la carte dirty sous un verrou mutex ( mu ). Dirty Map ( dirty ) : Cette carte stocke les entrées en cours de modification et les nouvelles entrées non encore visibles dans la carte read . L'accès à cette carte nécessite de maintenir le verrou mutex pour garantir un accès exclusif. Lors d'une opération d'écriture, si la clé ne se trouve pas dans la carte read ou doit être mise à jour, l'opération se poursuit sur la carte dirty . Si la carte dirty est nil , elle est initialisée en faisant une copie superficielle de la carte read , en excluant les entrées qui ne sont plus valides. Après un certain seuil de « ratés » (recherches échouées qui ont nécessité de revenir à la carte dirty ), la carte dirty est promue comme la nouvelle carte read , et une nouvelle carte dirty est préparée si nécessaire.

Différences par rapport à une Go Map intégrée avec Mutex

Nous pouvons maintenant comprendre quelle est la différence entre une carte intégrée avec un Mutex et sync.Map :

1. Conflit de verrouillage :
   • sync.Map : conçu pour minimiser les conflits de verrouillage. Pour la plupart des opérations de lecture, aucun verrou n'est nécessaire en raison du pointeur read atomique. Les écritures et les suppressions qui n'affectent qu'une petite partie de la carte minimisent également la durée du verrouillage, car elles verrouillent uniquement la carte dirty .
   • Carte intégrée avec Mutex : chaque accès (lecture ou écriture) nécessite l'acquisition du mutex, ce qui peut devenir un goulot d'étranglement dans les scénarios à forte concurrence.
2. Surcharge mémoire et complexité :
   • sync.Map : conserve deux versions de la carte et peut être plus gourmand en mémoire. La logique de gestion de ces versions ajoute de la complexité.
   • Carte intégrée avec Mutex : Plus simple et utilise moins de mémoire que sync.Map car elle ne conserve qu'une seule version de la carte.
3. Spécificité du cas d'utilisation :
   • sync.Map : optimisé pour les cas d'utilisation où les clés sont principalement lues et peu fréquemment mises à jour ou où de nombreuses opérations se produisent sur des ensembles de clés disjoints.
   • Carte intégrée avec Mutex : à usage général, simple à utiliser, mais peut ne pas fonctionner aussi bien dans des scénarios spécifiques à haute concurrence en raison de conflits de verrouillage universel.

En résumé, sync.Map est spécialisé dans les scénarios qui peuvent tirer parti de ses optimisations de concurrence pour réduire les conflits de verrouillage, au prix d'une complexité et d'une utilisation de la mémoire accrues. En revanche, une carte Go standard avec un mutex est une solution plus simple et plus générale mais peut souffrir de problèmes de performances dans des environnements hautement concurrents.

Emballer

Tout au long de cet article, nous avons exploré les subtilités de l'utilisation des structures de données cartographiques, en nous concentrant particulièrement sur leur implémentation et leur utilisation dans le langage de programmation Go. En commençant par le concept de base d'un tableau associatif, nous avons approfondi la mécanique des cartes de hachage, discutant de leurs procédures opérationnelles, de leurs complexités temporelles et spatiales, ainsi que de différentes approches telles que le chaînage séparé et l'adressage ouvert pour gérer les collisions.

Dans le domaine de Go, nous avons étudié comment les cartes sont utilisées et intégrées au langage, en examinant les structures sous-jacentes telles que hmap et bmap . Cette exploration comprenait des exemples de code pratiques, démontrant comment initialiser, manipuler et utiliser efficacement des cartes dans les applications Go. De plus, nous avons souligné les pièges potentiels de la concurrence lors de l'utilisation de cartes et introduit sync.Map pour les scénarios nécessitant un accès simultané, ce qui réduit les conflits de verrouillage et optimise les performances.

Comprendre ces aspects des structures de données cartographiques améliore non seulement votre boîte à outils de codage, mais vous prépare également à relever les défis de programmation courants avec plus d'efficacité et de confiance. Que vous développiez des applications simples ou des systèmes complexes qui nécessitent des performances optimales dans des environnements simultanés, savoir comment et quand utiliser différents types de cartes est inestimable. Alors que vous continuez à développer votre expertise en programmation, continuez à expérimenter ces structures et leurs différentes implémentations pour exploiter pleinement leur potentiel dans vos projets.