principe de mise en œuvre de la carte Golang

Dans le processus d'apprentissage du Golang, la carte est une structure de données que nous utilisons souvent, qui peut être utilisée pour stocker des paires clé-valeur. Mais avez-vous déjà réfléchi à la façon dont la carte est implémentée ? Dans cet article, nous explorerons comment la carte est implémentée dans Golang.

Introduction au principe d'implémentation de map

map est en fait une table de hachage, et son principe d'implémentation est l'algorithme de hachage. Une table de hachage est une structure de données qui accède directement aux emplacements de stockage en mémoire en fonction des clés, c'est-à-dire qu'elle fournit un moyen de mapper les clés aux adresses mémoire. Dans une table de hachage, les mots-clés sont appelés « clés » et les adresses mémoire calculées par la fonction de hachage sont appelées « buckets ». Les buckets stockent les paires clé-valeur.

Dans Golang, la carte est implémentée en stockant des paires clé-valeur dans la zone mémoire du bucket. Chaque bucket a une structure d'en-tête utilisée pour décrire l'état du bucket. .

structure de données du bucket

Examinons d'abord la structure des données du bucket :

type bmap struct {
    tophash [bucketCnt]uint8
    // data 的类型在 map 被分配空间的时候由 map 的 key 和 value 类型决定
    // 如果 key 类型和 value 类型都是未知类型，那么 data 的类型是 byte
    // 因为 byte 可以用于存储任何类型，也就是说 data 可以存储任何类型的 key 和 value
    // 在存储 key 和 value 的时候，需要将 key 和 value 转换成 uintptr，然后再转换成 byte 存储到 data 中
    // 读取 key 和 value 的时候反向操作即可
    // 因此，map 中的 key 和 value 一般都是需要转换成 uintptr 类型的
    // 这里我们可以简单地理解为 data 存储了键值对的二进制数据
    // 第一个 bucket 中如果存不下某个 key-value，还需要在第二个 bucket 中存储
    // 所以，data 的长度可以为 1 或 2
    // 当 data 的长度为 1 或 2 时，存储的键值对的个数分别为 1 或 2
    // 因此，bucket 中最多只能存储 8 个键值对
    // 否则，就需要将键值对存储在 overflow 中
    // overflow 是一个指向单链表头部的指针数组
    // 如果某个桶存储的键值对数量超过了 8，那么就将多余的键值对存储到 overflow 中
    // overflow 中的第一个 bucket 中也是能够存储 8 个键值对的，如果第一个 bucket 中存不下的话
    // 那么还需要在第二个 bucket 中继续存储
    // 所以，overflow 数组的长度也可以为 1 或 2
    // 当 overflow 数组长度为 1 或 2 时，最多存储 8 个键值对的 overflow
    // 当 overflow 数组长度为 3 时，最多存储 24 个键值对的 overflow
    // 也就是说，如果 map 中存储的键值对数量很多的话，那么可能会有很多个 overflow 桶
    // 而 overflow 数组是动态分配的，因此它的长度是不定的，只有在运行时才能确定
    data unsafe.Pointer
    // overflow 是一个指针数组，用于存储除当前桶以外的其它桶
    // 如果某个桶的键值对数量超过了 8，那么它会将多余的键值对存储到 overflow 中
    // overflow 数组中的每个元素都是一个 bucket 指针
    // 这些 bucket 指针构成了一个链表，也就是所谓的 overflow 链表
    overflow *[]*bmap
    // 这里存储的是这个 bucket 当前存储的键值对的个数
    count int16
    // flags 存储了 bucket 的标志
    // 一个 bucket 可能会有如下三种状态：
    // 1. empty，表示这个 bucket 没有存储任何键值对
    // 2. iterator，表示这个 bucket 正在被访问，不能再被其它操作使用
    // 3. deleted，表示这个 bucket 存储的键值对已经被删除了
    // 注意，该标志位只有在 GC 达到一定阈值后才会被置为 true，而且并不是立即删除键值对，而是在下一次 GC 的时候才会内存回收
    flags uint8
    // Bmap 的类型标记
    // Bmap 用来标识存储于上文中 data 指针中的数据类型
    // 如果 data 中存储的是 int，那么 Bmap 的值为 hmap.BmapInt
    // 如果 data 中存储的是 string，那么 Bmap 的值为 hmap.BmapString
    // 如果 data 中存储的是 interface{}，那么 Bmap 的值为 hmap.BmapInterface
    // 如果 data 中存储其他类型，那么 Bmap 的值为 hmap.BmapOther
    BmapType uint16
    // 与该 bucket 相关联的 key 的类型
    tophash0 uint8
}

D'après la définition ci-dessus, nous pouvons voir que le stockage du bucket est ce qui suit les informations sont obtenues :

• tophash : utilisé pour filtrer rapidement les clés sans correspondance ;
• data : données qui stockent les paires clé-valeur ;
# 🎜 🎜#overflow : Un tableau de pointeurs qui stocke la liste chaînée de débordement
• count : Stocke le nombre de paires clé-valeur stockées dans le compartiment actuel, jusqu'à 8 ; flags : stocke certaines informations d'état du bucket ;
• BmapType : stocke le type de données stockées dans data ;
• tophash0 : le type de clé associée au bucket.
• Principe de mise en œuvre

Étant donné que les données stockées dans la carte sont des paires clé-valeur et que les valeurs clés des paires clé-valeur ne sont pas répétables et peut être comparé, nous pouvons utiliser une fonction de hachage pour convertir la valeur clé en une valeur de hachage unique, puis utiliser la valeur de hachage comme index correspondant à la valeur clé et stocker la valeur sur cet index.

Dans Golang, chaque carte possède une table de hachage. Cette table de hachage est en fait un espace de stockage continu pouvant stocker plusieurs buckets. Chaque bucket est une structure de type bucket.

Alors, comment est déterminée la taille de la table de hachage ? Il s'agit d'une mémoire allouée dynamiquement lors de la création de la carte, et la taille par défaut utilisée lors de la première allocation de l'espace est de 8 compartiments. Si le nombre de compartiments n'est pas suffisant lors de l'ajout d'éléments pour la première fois, la taille de la table de hachage sera étendue et la position d'index de chaque élément dans la table de hachage sera recalculée.

Dans Golang, la fonction principale de la fonction de hachage est de hacher la valeur de la clé, ce qui rend plus pratique la localisation d'un bucket dans la table de hachage, accélérant ainsi la recherche de la valeur correspondant à la clé valeur. . Dans Golang, la fonction de hachage est implémentée à l'aide de l'algorithme MurmurHash3.

Étant donné que la fonction de hachage mappe la clé sur un entier, différentes valeurs de clé peuvent être mappées sur le même index. Cette situation est appelée collision de hachage. Lorsqu'un conflit de hachage se produit, Golang utilise la méthode de liste chaînée pour le résoudre, en stockant les paires clé-valeur sur le même index dans la liste chaînée de l'index. Ces paires clé-valeur sont appelées débordement.

Summary

Le principe d'implémentation de la carte de Golang repose principalement sur des tables de hachage et des fonctions de hachage. Une fonction de hachage est utilisée pour hacher la valeur clé, en la mappant à un compartiment dans une table de hachage, accélérant ainsi l'opération de recherche de valeur. La table de hachage se compose de plusieurs compartiments, chaque compartiment est représenté par une structure de type compartiment, qui stocke les informations sur les paires clé-valeur. Lorsqu'il existe plusieurs paires clé-valeur à la même position d'index dans la table de hachage, la méthode de liste chaînée est utilisée pour stocker le débordement. La carte dans Golang est en fait une table de hachage dynamique, qui peut ajuster dynamiquement la taille de la table de hachage. Lors de l'utilisation de cartes, il faut veiller à éviter les collisions de hachage et à inclure des types de tailles incomparables comme clés.

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!