Explication de l'implémentation de la carte Golang

Golang est un langage de programmation émergent, et sa carte est implémentée sur la base de tables de hachage. Dans cet article, nous verrons comment la carte est implémentée dans Golang. Plus précisément, nous présenterons le concept de tables de hachage, la structure et l'optimisation des performances des cartes Golang.

Le concept de table de hachage

Une table de hachage est une structure de données qui stocke les données dans des paires clé-valeur. Il mappe les clés à un index de tableau via une fonction de hachage, rendant l'accès aux données de la table de hachage plus efficace.

La fonction de hachage calcule la valeur qui lui est transmise dans une petite valeur de longueur fixe qui identifie de manière unique la clé (c'est ce qu'on appelle un code de hachage). Ce code de hachage est utilisé comme index du tableau.

Il y a quelques problèmes avec les fonctions de hachage. L'une est la collision de hachage, c'est-à-dire que différentes clés sont mappées sur le même index de tableau, ce qui doit être résolu en résolvant la collision de hachage. Un autre type de problème est l'inadéquation de la fonction de hachage, qui peut ne pas calculer avec précision le code de hachage de la valeur, ce qui entraîne une répartition inégale des données dans la table de hachage.

La structure de Golang map

Dans Golang, la carte est une structure et sa structure de données sous-jacente est une table de hachage. Plus précisément, la carte se compose des trois champs suivants :

type hmap struct {
    count int                                 
    flags uint32                              
    B     uint8                               
    hash0 uint32                              
    buckets unsafe.Pointer // 指向一个桶数组
    oldbuckets unsafe.Pointer // 用于扩容时的桶数组
    nevacuate uintptr // 当前将要被载入到oldbuckets的指针位置
    extra *mapextra
}

Parmi eux, le nombre représente le nombre d'éléments dans la carte ; les drapeaux sont utilisés pour enregistrer l'état de la carte, y compris s'il faut supprimer, itérer, etc. ; longueur du tableau de compartiments, qui est de 2 à la puissance Bth ; hash0 enregistre la graine de hachage, qui est utilisée pour le calcul de la fonction de hachage.

buckets est un pointeur qui pointe vers un tableau de buckets. Le format du tableau bucket est le suivant :

type bmap struct {
    tophash [bucketCnt]uint8
    data    [1]struct{ key, value interface{} }
}

Parmi eux, tophash est un tableau d'une longueur de bucketCnt. Chaque élément représente un élément dans bmap, et sa valeur est un entier utilisé pour localiser la paire clé-valeur dans le. données. data est un tableau de longueur 1 contenant une paire clé-valeur. Le format de la paire clé-valeur est le suivant :

type iface struct {
    tab  *itab
    data unsafe.Pointer
}

type itab struct {
    inter  *interfacetype
    _type  *_type
    link   *itab
    bad    int32
    inhash int32 // 是否在哈希表中
    funcbucket uintptr
    __hash uintptr // 哈希函数（方法）
    __eq   uintptr // 判断是否相等的函数（方法）
}

Parmi eux, le champ de données est un pointeur vers la structure iface. La structure iface contient un pointeur vers la paire clé-valeur stockée et un pointeur vers les informations de type.

Optimisation des performances de la carte Golang

L'optimisation des performances mise en œuvre par la carte Golang est principalement divisée en deux aspects suivants :

1. Extension du tableau de seaux

Lorsque le nombre d'éléments dans la carte dépasse la capacité du tableau de seaux, le tableau de compartiments doit être étendu. La façon de développer consiste à ajouter un nouveau tableau de compartiments. Lors du prochain accès à la carte, toutes les paires clé-valeur seront recalculées et déplacées une par une vers le nouveau tableau de compartiments. Ce processus est appelé resuçage.

Dans le processus d'expansion du bucket array, Golang utilise une technologie appelée hachage aléatoire. Cette technologie ajuste la graine de hachage afin que les paires clé-valeur puissent être réparties plus uniformément dans le nouveau tableau de compartiments lors du rehachage, réduisant ainsi les collisions de hachage.

2. Verrouillage de biais intégré

Golang utilise un mécanisme de verrouillage appelé verrouillage de biais dans la carte. Le verrouillage biaisé est une technique d'optimisation lorsque le verrou n'est accessible que par une routine unique, il utilisera l'ID de thread de cette goroutine pour verrouiller. De cette façon, lorsque cette routine go doit déverrouiller ou reverrouiller le verrou, il n'est pas nécessaire de changer de thread car aucune autre routine go n'accédera au verrou.

Résumé

La structure de données sous-jacente de la carte dans Golang est une table de hachage. Son tableau de compartiments utilise une technologie de hachage aléatoire pour ressasser les paires clé-valeur et utilise un mécanisme de verrouillage biaisé pour le verrouillage et le déverrouillage. Ces détails d'implémentation permettent à la carte dans Golang de très bien fonctionner dans certaines opérations courantes de structure de données.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!